The lecture notes are available on Learn, where they will be added throughout the term. The specific examples covered in each lecture will vary per section. References to the corresponding sections in the course textbook are included in parentheses
- Introduction
- Overview of the course, first examples (CLRS §1-2)
- Analyzing algorithms
- Model of computation, worst-case time complexity, Big-O notations (CLRS §3)
- Solving recurrences
- Recursion trees, Master theorem (CLRS §4.4-4.5)
- Divide and Conquer I
- Fast multiplication (CLRS §4)
- Divide and Conquer II
- Closest pair of points (CLRS §4,33.4)
- Greedy Algorithms I
- Scheduling problems (CLRS §16)
- Greedy Algorithms II
- Minimizing lateness. Exchange proofs (CLRS §16)
- Dynamic Programming I
- Making change, weighted interval scheduling (CLRS §15)
- Dynamic Programming II
- Longest common subsequences, edit distance (CLRS §15)
- Dynamic Programming III
- Other examples (CLRS §15)
- Introduction to Graph Algorithms
- Breadth-first search, testing bipartiteness (CLRS §22)
- Depth first search I
- Undirected graphs: detecting cycles (CLRS §22)
- Depth first search II
- Directed graphs (CLRS §22)
- Greedy algorithms in graphs I
- Minimum spanning trees (CLRS §23)
- Greedy algorithms in graphs II
- Shortest paths, Dijkstra's algorithm (CLRS §24)
- Dynamic programming for shortest paths
- Bellman-Ford algorithm, Floyd-Warshall algorithm (CLRS §24,25)
- Exhaustive search techniques
- Backtracking, branch-and-bound
- Introduction to P
- Polynomial-time algorithms, reductions (CLRS §34)
- NP and NP-completeness
- Definition, certificates (CLRS §34)
- NP-completeness on graphs
- Clique, vertex cover, Independent set, Hamiltonian cycle (CLRS §34)
- More NP-completeness
- More examples (CLRS §34)
- Approximation algorithms
- Euclidean TSP, Vertex cover, subset sum (CLRS §35)
- Bonus lecture I
- Undecidability or other topics
- Bonus lecture II
- (Instructor's choice)