## 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 |

- SAT instances
- Traveling salesman instances
- Social and information network datasets
- Wikipedia links
- Amazon co-purchasing data
- Movie database
- Movie ratings data
- Algorithms 4 data sets
- Twitter streaming API
- Primes smaller than a million