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)

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%].