In the following, "CLRS" indicates readings from
Introduction to Algorithms,
Second edition, by Cormen, Leiserson, Rivest, and Stein.
- Motivating Algorithms
- Review of asymptotic notation and recurrences
(CLRS: Skim Chapters 1-5, Appendices A-C.
You can ignore starred sections.)
- Lower bounds for sorting, counting sort, radix sort (CLRS: Sections 8.1-8.3)
- Median finding (CLRS: Chapter 9)
- Review of red-black trees (CLRS: Chapters 12 and 13)
- Augmenting data structures (CLRS: Chapter 14)
- Dynamic programming (CLRS: Chapter 15)
- Greedy algorithms (CLRS: Sections 16.1-16.3)
- Amortized analysis: aggregate analysis, accounting method, potential method, dynamic tables.
(CLRS: Chapter 17)
- Disjoint set data structure (CLRS: Sections 21.1-21.3, 22.1)
- Graph representation; Breadth-first search; depth-first search; topological sort;
strongly connected components (CLRS: Chapter 22)
- Minimum spanning trees (CLRS: Chapter 23)
- Single-source shortest paths: Bellman-Ford, dag, Dijkstra's algorithm, difference constraints
(CLRS: Chapter 24)
- All-pairs shortest paths: matrix multiplication, Floyd-Warshall algorithm.
(CLRS: Chapter 25)
- Network flow: Ford-Fulkerson, Edmonds-Karp, bipartite matching
(CLRS: Sections 26.1-26.3)
Back to CS 25 home page
Last modified: Wednesday, September 24, 2008