TSP

CS450: Advanced Algorithms (Spring 2023)


Credits 8
Lecturers Alessandro Chiesa and Michael Kapralov
Schedule Lectures: Tuesdays 11-13 in SG1 and Wednesdays 12-14 in CO3.
Exercises: Fridays 10-13 in CM1105 and INF1.

A first graduate course in algorithms, this course assumes minimal background but moves rapidly. The objective is to learn the main techniques of algorithm design and analysis while building a repertory of basic algorithmic solutions to problems in many domains.

This is a course for Master students. Lectures will be in English.

For more details see the official coursebook.

Important dates

Topics

A preliminary list of topics:

Reading

The detailed schedule, lecture notes, and additional links to material is on the course moodle.

Mid-term and Final Exam

You can use a single hand-written A4-page on which you can write anything on both sides. (No magnifying glasses allowed!)

Grading

Grades will be based on two homeworks [30%], the midterm [30%], and the final exam [40%].

Syllabus

Subject Date Time Description Location
Lecture 1 2023-02-21 11:00 - 13:00 When and why does GREEDY work? SG1
Lecture 2 2023-02-22 12:00 - 14:00 Matroid Intersection and Bipartite Matchings CO3
Lecture 3 2023-02-28 11:00 - 13:00 Matchings, Intro to Linear Programming SG1
Lecture 4 2023-03-01 12:00 - 14:00 Linear Programming: Extreme Points CO3
Lecture 5 2023-03-07 11:00 - 13:00 Linear Programming: Duality SG1
Lecture 6 2023-03-08 12:00 - 14:00 Hungarian Method and Weighted Vertex Cover CO3
2023-03-14 11:00 - 13:00 Cancelled
Lecture 7 2023-03-15 12:00 - 14:00 Approximation Algorithms CO3
Lecture 8 2023-03-21 11:00 - 13:00 Approximation Algorithms using LPs SG1
Lecture 9 2023-03-22 12:00 - 14:00 Solving LPs using Multiplicative Weights CO3
Lecture 10 2023-03-28 11:00 - 13:00 Hedging for LPs and Intro to Randomized Algorithms SG1
Lecture 11 2023-03-29 12:00 - 14:00 Randomized Algorithms (Karger's Min-Cut Algorithm) CO3
Midterm Exam 2023-03-31 10:00 - 13:00
Lecture 12 2023-04-04 11:00 - 13:00 Sampling and Concentration Inequalities SG1
Lecture 13 2023-04-05 12:00 - 14:00 Graph Sparsification CO3
Lecture 14 2023-04-18 11:00 - 13:00 Graph Sparsification SG1
Lecture 15 2023-04-19 12:00 - 14:00 Hashing CO3
Lecture 16 2023-04-25 11:00 - 13:00 Streaming Algorithms SG1
Lecture 17 2023-04-26 12:00 - 14:00 Distinct elements, AMS sketch CO3
Lecture 18 2023-05-02 11:00 - 13:00 Distinct elements, AMS sketch SG1
Lecture 19 2023-05-03 12:00 - 14:00 Locality Sensitive Hashing CO3
Lecture 20 2023-05-09 11:00 - 13:00 Streaming Algorithms SG1
Lecture 21 2023-05-10 12:00 - 14:00 Submodularity and Minimization CO3
Lecture 22 2023-05-16 11:00 - 13:00 Submodularity and Minimization SG1
Lecture 23 2023-05-17 12:00 - 14:00 Submodularity and Maximization CO3
Lecture 24 2023-05-23 11:00 - 13:00 Introduction to Spectral Graph Theory SG1
Lecture 25 2023-05-24 12:00 - 14:00 Online Algorithms CO3
Lecture 26 2023-05-30 11:00 - 13:00 Spectral Graph Theory and Connectivity SG1
Lecture 27 2023-05-31 12:00 - 14:00 CO3