This page contains the order of topics contained in lectures, listed as a sequence of modules. Please note that modules may vary considerably in length and difficulty; please see the schedule for details on timing.
Lecture materials are posted on LEARN in various formats, for your convenience. The slides and audio have been joined together into videos; there are also written transcripts of the audio.
Please see the resources page for additional relevant material, including a document outlining coverage of the material by the (optional) textbook.
Module 1: Introduction
Topics: Introduction, course goals, types of problems, exhaustive search
Module 2: Comparing problems and solutions
Topics: Comparing problems, models of computation, pseudocode, asymptotic notation, analyzing algorithms, analyzing exhaustive search
Module 3: Greedy approach
Topics: Scheduling activities, making change, fractional knapsack, single-source cheapest paths, spanning tree
Module 4: Divide-and-conquer
Topics: Binary search, sorting, solving recurrence relations, maximum subtotal, matrix multiplication
Module 5: Dynamic programming
Topics: Matrix-chain multiplication, longest common subsequence, all-pairs cheapest paths
Module 6: Hardness of problems
Topics: Complexity, polynomial time, lower bounds, decision trees, adversary lower bounds, reductions, NP-completeness
Module 7: Compromising on speed
Topics: Search trees, backtracking, branch and bound, fixed-parameter algorithms, Las Vegas algorithms
Module 8: Compromising on correctness
Topics: Approximation algorithms, Monte Carlo algorithms, heuristics