Reading list
| topic | lecture notes | read by |
| introduction: stable matching | Lec_01.pdf | 9/2/05 |
| notion of algorithm, insertion sort, correctness using loop invariant, running time, asymptotic notation, merge sort, correctness using loop invariant and induction, running time using substitution method | Lec_02.pdf | 9/20/05 |
| recursion tree method, quicksort, its correctness, intuition for average running time, and worst case running time; randomized quicksort | Lec_03.pdf | 9/23/05 |
| lower bound on sorting using comparisons, countingsort and radixsort | Lec_04.pdf | 10/5/05 |
| bucketsort | CLRS Sec 8.4 | 10/7/05 |
| graph traversals, BFS and DFS, and their properties | Lec_05.pdf | 10/26/05 |
| topological sort | Lec_06.pdf | 10/28/05 |
| minimum spanning tree and the Prim's algorithm | Lec_07.pdf | 11/4/05 |
| PageRank algorithm of Google | brin&page.pdf copyright Elsevier original | 11/9/05 |
| flow networks, Ford-Fulkerson, maximum matching in bipartite graph | Lec_08.pdf | 11/18/05 |
| Dijkstra's shortest path algorithm | Lec_09.pdf | 12/1/05 |
| negative edge lengths and shortest paths in directed acyclic graphs by a greedy algorithm | Lec_10.pdf | 12/4/05 |
| Bellman-Ford for shortest paths in arbitrary directed graphs with possibly negative edge lengths | Lec_11.pdf | 12/11/05 |