CS

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)



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.



5. GRAPH SEARCH & DIJKSTRA's ALGORITHM (1/18/2011)



6. CONNECTIVITY IN DIRECTED GRAPHS (1/20/2011)



7. Introduction to Greedy Algorithms (1/25/2011)



8. Minimum Spanning Trees (1/27/2011)



9. Kruskal's Algorithm and Union-Find (2/1/2011)



10. Path Compression and Clustering (2/3/2011)



11. Introduction to Randomized Algorithms (2/8/2011)



12. QuickSort (2/10/2011)



13. Hashing (2/15/2011)



14. Balanced Search Trees and Skip Lists (2/17/2011)



15. Introduction to Dynamic Programming (2/22/2011)



16. Sequence Alignment (2/24/2011)



17. Shortest Paths: Bellman-Ford and Floyd-Warshall (3/1/2011)



18. NP-Complete Problems (3/3/2011)



19. Approximation Algorithms (3/8/2011)



20. The Wider World of Algorithms (3/10/2011)



Resources