VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.

263-4500-00L 9 Credits BSC , DR , MSC , WBZ D-ITET , D-INFK , D-MATH

You're viewing possible stale or outdated data. Please check the latest semester for more up-to-date information.

Advanced Algorithms

Lecturers & Examiners: Dr. Mohsen Ghaffari

VVZ CR 2.5

Last Updated: 2026-02-05 15:35:54

Abstract

This is a graduate-level course on algorithm design (and analysis). It covers a range of topics and techniques in approximation algorithms, sketching and streaming algorithms, and online algorithms.

Objective

This course familiarizes the students with some of the main tools and techniques in modern subareas of algorithm design.

Content

The lectures will cover a range of topics, tentatively including the following: graph sparsifications while preserving cuts or distances, various approximation algorithms techniques and concepts, metric embeddings and probabilistic tree embeddings, online algorithms, multiplicative weight updates, streaming algorithms, sketching algorithms, and derandomization.

Resources

Lecture Notes

https://people.inf.ethz.ch/gmohsen/AA20/

Learning Materials (Links)

Main link
Information

General Information

Language: English
Levels: BSC , DR , MSC , WBZ
Frequency: Yearly recurring

Examination

Type: session examination
Mode: written 180 minutes
Aids: open book: you are permitted to consult any books, handouts, and personal notes. The use of electronic devices is not allowed.

This course has a final exam (3 hours, open book, 60% of the finalgrade) plus two graded homework (20% each). The two mandatory graded homework (compulsory continuous performance assessments) will be released throughout the semester, in specific dates that will be announced. Each graded homework will have a deadline two weeks after the release. The solutions must be typeset in LaTeX (or similar).These solutions will be graded and the grade for each GHW accounts for 20% of the final grade.

Course Components

Type	Title	Time & Place	Hours
lecture	Advanced Algorithms The lecturers will communicate the exact lesson times of ONLINE courses.	Wed 09:00-12:00 (ON LI NE)	3 h weekly
exercise	Advanced Algorithms The lecturers will communicate the exact lesson times of ONLINE courses.	Fri 10:00-12:00 (ON LI NE)	2 h weekly
independent project	Advanced Algorithms	No time listed	3 h weekly

Offered In

Mathematics Bachelor
- Electives
  - Auswahl: Theoretical Computer Science
Computer Science Master
- Master Studies (Programme Regulations 2020)
  - Majors
    - Major in Machine Intelligence
      - Elective Courses
    - Major in Theoretical Computer Science
      - Core Courses
  - Minors
    - Minor in Theoretical Computer Science
- Master Studies (Programme Regulations 2009)
  - Focus Courses
    - Focus Courses in Theoretical Computer Science
      - Focus Elective Courses Theoretical Computer Science
    - Focus Courses General Studies
      - Focus Elective Courses General Studies
Mathematics Master
- Electives (For the Master's degree in Applied Mathematics the following additional condition (not manifest in myStudies) must be obeyed: At least 15 of the required 28 credits from core courses and electives must be acquired in areas of applied mathematics and further application-oriented fields.)
  - Electives: Applied Mathematics and Further Application-Oriented Fields (¬)
    - Auswahl: Theoretical Computer Science, Discrete Mathematics
CAS in Computer Science
- Focus Courses and Electives
Doctoral Dep. of Information Technology and Electrical Engineering (More Information at: )
- Doctoral and Post-Doctoral Courses (A minimum of 12 ECTS credit points must be obtained during doctoral studies. The courses on offer below are only a small selection out of a much larger available number of courses. Please discuss your course selection with your PhD supervisor.)
Data Science Master
- Core Courses
  - Data Management
Cyber Security Master
- Minor
  - Theoretical Computer Science
    - Elective Courses