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