Algorithm Design II, Fall 2012

Taught by Rasmus Pagh. Teaching assistant: Morten Stöckel.

See also the official course description.


Lectures are Wednesdays 10.00-11.50 in room 3A18. Exercises follow in the same room after a lunch break. In the schedule, KT refers to the textbook by Kleinberg and Tardos.

Also available is a comprehensive set of lecture slides by Kevin Wayne.

Announcements and discussions are located on Piazza. Registered students should have received an invitation.

DateTopicLiteratureExercises
24/10Intro (slides); Guest lecture on exponential time algorithms (using selected slides by Wayne)KT 10.1, Note by Thore Husfeldtpdf
31/10Approximation algorithms (slides)KT 11.1, 11.4 (p. 620-623), 11.6, 11.8pdf
7/11Randomized algorithms (slides, example)KT 13.1, 13.2, 13.3, 13.5pdf
14/11Project kick-off (slides)
21/11Algorithms for data streams (notes)McGregor12 section 1.1, 1.2, 2.1, [BJKST02, sec. 1+2],
Optional: Background survey sect. 0.4, 0.5
28/11Algorithms for Massive Data (notes)[Sanders03], [Vitter08, sections 3, 5.2], [LinDyer10 sec. 4.3, 5.2]
5/12Randomized algorithms, cont. (slides)KT 13.6, 13.9, 13.10, and Pagh06

Data sets

Source code

Other resources