Algorithm Design II, Fall 2012
Taught by Rasmus Pagh. Teaching assistant: Morten Stöckel.
See also the official course description.
|
Algorithm Design II, Fall 2012Taught 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.
| Date | Topic | Literature | Exercises |
| 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 |