CS450: Algorithms II (Autumn 2023)
| Credits | 8 | |
| Lecturer | Ola Svensson | |
| Schedule | Lectures: Thursdays 8-10 in CM13 and Fridays 8-10 in CO3.
Exercises: Fridays 10-12 in CM012, CM1120 and CM1221. Office hours: Thursdays 15-16 in BC02, BC03, BC04 |
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
- Mid-term exam: Nov 3
- Final exam: during exam session (exact date TBD)
Topics
A preliminary list of topics:- When and why do greedy algorithms work? Matroids and matroid intersection.
- Convex programming for discrete optimization: linear programming (extreme point structure, duality) and semidefinite programming.
- Approximation algorithms (tradeoff between time and solution quality).
- Simplex method, ellipsoid method, gradient descent, and multiplicative weight update method.
- Submodular function optimization: polynomial-time minimization and approximate maximization.
- Online algorithms (tradeoff between knowledge about future and solution quality).
- Streaming algorithms (tradeoff between knowledge about future and solution quality).
- Randomized algorithms (hashing, power of two choices, Karger's min-cut algorithm).
- Spectral graph theory (random walks, Cheeger's inequality)