
CS 161 - Design and Analysis of Algorithms
Prof. Tim Roughgarden
Course Description
Course Overview: Introduction to fundamental techniques for designing and analyzing algorithms, including asymptotic analysis; divide-and-conquer algorithms and recurrences; greedy algorithms; data structures; dynamic programming; graph algorithms; and randomized algorithms. Required textbook: Kleinberg and Tardos, Algorithm Design, 2005. We will be covering most of Chapters 4–6, some parts of Chapter 13, and a couple of topics not in the book. Prerequisites: Introduction to proofs, and discrete mathematics and probability (e.g., CS 103 and Stat116). If you have not taken a probability course, you should expect to do some independent reading during the course on topics including random variables, expectation, conditioning, and basic combinatorics.
1. INTRODUCTION (1/4/2011)
 Why are you here?
 Administrivia
 Gauss's Trick
2. BASIC DIVIDE & CONQUER (1/6/2011)
3. THE MASTER METHOD (1/11/2011)
4. LINEAR-TIME MEDIAN (1/13/2011)
We apologize for the poor audio quality in this video.
 Median of Medians
 Recap
 Rough Recurrence
 Key Lemma (Part 1)
 Key Lemma (Part 2)
5. GRAPH SEARCH & DIJKSTRA's ALGORITHM (1/18/2011)
 Graph Primitives
6. CONNECTIVITY IN DIRECTED GRAPHS (1/20/2011)
 Example (Part 1)
 Example (Part 2)
 Proof of Key Lemma
7. Introduction to Greedy Algorithms (1/25/2011)
 Course Roadmap
 A Scheduling Problem
 Correctness Proof
8. Minimum Spanning Trees (1/27/2011)
 Introduction
 Prim's Algorithm
 The Cut Property
9. Kruskal's Algorithm and Union-Find (2/1/2011)
 Kruskal's Algorithm
 Naive Running Time
 Union by Rank
 Path Compression
10. Path Compression and Clustering (2/3/2011)
 Union-Find Review
 Path Compression
 Rank Blocks
 Clustering
 A Greedy Algorithm
11. Introduction to Randomized Algorithms (2/8/2011)
 The Min Cut Problem
 Probability Review
 Final Comments
12. QuickSort (2/10/2011)
 Counting Comparisons
 Crux of Proof
 Final Calculations
13. Hashing (2/15/2011)
 Running Time
 Universal Hashing
 A Universal Family
 Bloom Filters
14. Balanced Search Trees and Skip Lists (2/17/2011)
 Deleting from a BST
 Red-Black Trees
 Rotations
15. Introduction to Dynamic Programming (2/22/2011)
 The Knapsack Problem
16. Sequence Alignment (2/24/2011)
 Sequence Alignment
 Optimal Substructure
 On Negative Cycles
17. Shortest Paths: Bellman-Ford and Floyd-Warshall (3/1/2011)
 Space Optimization
18. NP-Complete Problems (3/3/2011)
 Reductions
 Completeness
 NP-Completeness
 Does P=NP?
19. Approximation Algorithms (3/8/2011)
 Final Exam Info
 Accuracy Analysis
20. The Wider World of Algorithms (3/10/2011)
 Bipartite Matching
 Stable Matching
 Maximum Flow
 Linear Programming