Introduction
Oftentimes algorithmic theory is wrongfully deemed to be irrelevant to practitioners who are thought to resort only to simple ad-hoc heuristics when dealing with their computational problems. The objective of this class is to counter this notion by exposing students to sophisticated algorithmic techniques that are used in the real world, as well as more realistic models of computation that have been developed in recent years.
Assumed Knowledge
This course assumes basic knowledge in algorithm analysis, linear algebra, and probability.
Assessment
- Assignments — 60%
- Project — 40%
Schedule
| Date | Topic | Further reading |
|---|---|---|
| Mar 3 | Introduction to Linear Programming: Simplex and Duality | [1, Ch 1 & 2] | Ma 10 | Deriving the Simplex algorithm | [1, Ch 3 & 4] |
| Mar 17 | Introduction to Integer Programming: Integral LPs | [2, Ch 3] |
| Mar 24 | IP techniques: Branch and Bound, and Cutting Plane | [2, Ch 7] |
| Mar 31 | Approximation algorithms for covering problems | [3, Ch 2 & 13] |
| Apr 7 | Local search algorithms | [4, Ch 12] |
| Apr 14 | Cryptography: RSA algorithm | [5, Ch 1] |
| Apr 21 | Project Milestone 1 | |
| May 5 | Pagerank algorithm (Taso Viglas invited lecture) | |
| May 12 | External memory algorithm: Persistent B-trees | [6, Ch 1,2,4] |
| May 19 | Cache-oblivious algorithms | [7,8] |
| May 26 | Steaming algorithms: Sampling | [9] |
| June 2 | Steaming algorithms: Majority and Median | [9] |
References:
- [1] Linear Optimization by Bertsimas and Tsitsiklis
- [2] Integer Programming by Wolsey
- [3] Approximation algorithms by Vazirani
- [4] Algorithm Design by Kleinberg and Tardos
- [5] Algorithms by Dasgupta, Papadimitriou and Vazirani
- [6] External Memory Geometric Data Structures by Arge
- [7] Cache-Oblivious Algorithms and Data Structures by Demaine
- [8] Cache-Oblivious Algorithms by Kumar
- [9] Data stream algorithms by Chakrabarti