| Week | Date | Topics and Reading |
| 6 | February 5 | Graph representations, BFS, DFS, DAGs [Cormen et al., Sect. 22.1-4]. It is also a good idea to skim [Cormen et al., Chap. 1 and Appendices B.4-5] as background material. |
| February 8 | Topological sorting, strongly connected components, simple union-find, greedy algorithms, minimum spanning trees, Kruskals algorithm [Cormen et al., Sect. 22.4-5, 21.1-2, 23.1-2]. A more elaborate discussion of greedy algorithms can be found in [Cormen et al., Chap. 16]. | |
| 7 | February 12 | Prims algorithm, shortest paths, Dijkstras algorithm, Bellman-Fords algorithm, algorithm for DAGs [Cormen et al., Sect. 23.2, 24.1-3, 24.5]. |
| February 15 | All pairs shortest paths, matrix multiplication like algorithm, Floyd-Warshalls algorithm, transitive closure, flow networks [Cormen et al., Sect. 25.1-2, 26.1]. | |
| 8 | February 19 | Max flow, Ford-Fulkerson algorithm, Edmond-Karp algorithm, maximum bipartite matching, priority queues, heaps [Cormen et al., Sect. 26.2-3, Chap. 6]. |
| February 22 | Linear time building of heaps, HeapSort, amortized analysis [Cormen et al., Sect. 6.2-3, Chap. 17]. | |
| 9 | February 26 | Cancelled (lectures moved) |
| March 1 | Cancelled (lectures moved) | |
| 10 | March 5 | Binomial heaps, Fibonacci heaps [Cormen et al., Chap. 18 and 19. Note that in these chapters, the very detailed level and elaborate code of the textbook almost obscure the ideas behind the data structures. Read the ideas, not the code.]. |
| March 8 | Advanced data structure for union-find (alias disjoint sets) [Cormen et al., Sect. 21.3-4]. | |
| 11 | March 12 | Dynamic programming, lower bound for comparison based sorting [Cormen et al., Sect. 15.2-4, 8.1. Note that the sections on dynamic programming are very wordy on the subject of when dynamic programming is applicable - read those part lightly.] |
| March 15 | CountingSort, RadixSort, BucketSort (all three briefly done). Selection in worstcase linear time [Cormen et al., Sect. 8.2-4 and 9.3]. | |
| 12 | March 19 | Randomized algorithms, randomized QuickSort (briefly), hashing, universal hashing, perfect hashing [Cormen et al., Sect. 5.1, 5.3, 7.3 and Chap. 11 (11.4 should only be skimmed)]. |
| March 22 | Strings: sorting (RadixQuickSort), searching (tries, ternary trees), pattern matching (KMP algorithm) [Bentley and Sedgewick (handout), Cormen et al., Sect. 32.1, 32.4] |
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms, second edition, MIT Press, 2001, ISBN 0-262-03293-7.The book has several websites. The one at MIT Press contains a bug list.
Additional material: