Reading list
| topic | location in CLRS | read by |
| introduction | [1] | 1/18 |
| insertion sort and loop invariant | [2.1] | 1/18 |
| analysis of running time of insertion sort | [2.2] | 2/8 |
| asymptotic notation and some math background | [3] | 2/8 |
| mergesort; proof of correctness of the merge procedure using loop invariant; proof of correctness of mergesort using induction; analysis of O(n log n) worst-case running time of mergesort using recurrence | [2.3] | 2/10 |
| recursive equations arising in analysis of divide and conquer algorithms and methods for solving them: substitution, recursion-tree and master method. | [4.1,4.2,4.3] | 2/22 |
| quicksort; poof of correctness of partition function; proof of O(n2) running time of quicksort, and intuition for average case O(n log n); randomized quicksort | [7 except for 7.4.2] | 3/1 |
| counting sort and radix sort | [8.2, 8.3] | 3/1 |
| proof that any comparison sort has running time Omega(n log n) in the worst-case | [8.1] | 3/12 |
| bucket sort and proof that its expected running time is O(n) when each element is equally likely to land into each bucket independently of other elements; use of indicator random variables in algorithm analysis | [8.4] | 3/12 |
| dynamic programming technique for solving optimization problems and assembly-line scheduling as an example of the technique | [15.1] | 3/23 |
| matrix chain multiplication | [15.2] | 4/4 |
| longest common subsequence | [15.4] | 4/4 |
| graph representation | [22.1] | 4/19 |
| breadth-first search | [22.2] | 4/19 |
| depth-first search | [22.3] | 4/22 |
| topological sort | [22.4] | 4/30 |
| minimum spanning tree algorithm of Kruskal | [23] | 4/30 |
| Dijkstra's single source shortest path algorithm | [24.2. 24.3] | 4/30 |