CS450: Algorithms II (Autumn 2023)

Credits 
8 

Lecturer 
Ola Svensson 

Schedule 
Lectures: Thursdays 810 in CM13 and Fridays 810 in CO3.
Exercises: Fridays 1012 in CM012, CM1120 and CM1221.
Office hours: Thursdays 1516 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
 Midterm 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: polynomialtime 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 mincut 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.
Midterm and Final Exam
You can use a single
handwritten A4page 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%].