Week 1
Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.
Week 2
Kruskal's MST algorithm and applications to clustering; advanced union-find (optional); Huffman codes.
Week 3
Dynamic programming: introduction, the knapsack problem, sequence alignment, and optimal binary search trees.
Week 4
The Bellman-Ford algorithm; all-pairs shortest paths.
Week 5
NP-complete problems and exact algorithms for them.
Week 6
Approximation and local search algorithms for NP-complete problems; the wider world of algorithms.
Final Exam
Final exam (1 attempt per 24 hours)