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.
|24/10||Intro (slides); Guest lecture on exponential time algorithms (using selected slides by Wayne)||KT 10.1, Note by Thore Husfeldt|
|31/10||Approximation algorithms (slides)||KT 11.1, 11.4 (p. 620-623), 11.6, 11.8|
|7/11||Randomized algorithms (slides, example)||KT 13.1, 13.2, 13.3, 13.5|
|14/11||Project kick-off (slides)|
|21/11||Algorithms 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/11||Algorithms for Massive Data (notes)||[Sanders03], [Vitter08, sections 3, 5.2], [LinDyer10 sec. 4.3, 5.2]|
|5/12||Randomized algorithms, cont. (slides)||KT 13.6, 13.9, 13.10, and Pagh06|