CS473: Fundamental Algorithms (Fall 2010)

Schedule and Lecture Notes

Videos of lectures are available here

Date Topics Reading
Tuesday, August 24 Administrivia, overview, motivation, graph basics, DFS Chapters 1-3 from textbook, Jeff Erickson's notes on induction/proofs
Thursday, August 26 DFS in Directed Graphs, Strong Connected Components, DAGs Chapter 3 of text book and Chapter 3 of Dasgupta etal book.
Tuesday, August 31 BFS, Single-source Shortest Paths Chapter 3 of text book and Chapter 3 of Dasgupta etal book.
Thursday, September 2 Shortest Paths with Negative Edge Lengths Chapter 3 of Dasgupta etal book, Jeff Erickson's notes
Tuesday, September 7 Reductions, Recursion, Divide and Conquer Chapter 5, Jeff Erickson's notes on recurrences
Thursday, September 9 Recurrences, Closest Pair, Quick Sort and Quick Selection Chapter 5, Jeff Erickson's notes on recurrences
Tuesday, September 14 Catch up lecture  
Thursday, September 16 Exponentiation, Binary Search, Intro to Dynamic Programming Chapter 6
Tuesday, September 21 Dynamic Programming: Longest Increasing Subsequence, Weighted Interval Scheduling Chapter 6
Thursday, September 23 Dynamic Programming: Independent Sets in Trees, Edit Distance Chapter 6
Tuesday, September 28 Dynamic Programming: Shortest Paths, Knapsack Chapter 6
Thursday, September 30 Midterm 1: 7-9pm, 151 Everitt Lab Topics
Tuesday, October 5 Greedy Algorithms: Examples and Proof Techniques Chapter 4
Thursday, October 7 Greedy Algorithms for Minimum Spanning Tree Chapter 4
Tuesday, October 12 Introduction to Randomized Algorithms Lecture Notes, Jeff Erickson's notes, Chapter 13
Thursday, October 14 Randomized Quick Sort and Selection Lecture Notes, Jeff Erickson's notes, Chapter 13
Friday, October 15 Drop Deadline  
Tuesday, October 19 Hash Tables Lecture Notes, Jeff Erickson's notes
Thursday, October 21 Introduction to Network Flows Chapter 7
Tuesday, October 26 Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut Chapter 7
Thursday, October 28 Applications of Network Flow: Disjoint Paths and Bipartite Matchings Chapter 7
Tuesday, November 2 More Applications of Network Flow Chapter 7
Thursday, November 4 Midterm 2: 7-9pm, 1404 Siebel Topics
Tuesday, November 9 Polynomial time Reductions Chapter 8
Thursday, November 11 SAT and Definition of NP Chapter 8
Tuesday, November 16 NP-Completeness, Circuit Sat and Cook-Levin Theorem Chapter 8
Thursday, November 18 More NP-Complete Problems Chapter 8
Tue/Thu, November 23, 25 Thanksgiving Break  
Tuesday, November 30 P, NP, co-NP, Self Reductions Chapter 8
Thursday, December 2 Catch up lecture  
Tuesday, December 7 Heuristics, Closing thoughts Chapter 9 in Dasgupta etal book
Tuesday, December 14 Final Exam: 1.30-4.30pm in 1404 Siebel (1302 is overflow room)  

Acknowledgments: Lecture notes are based on notes of Jeff Erickson, Sariel Har-Peled, and the slides of Mahesh Viswanathan and the books by Kleinberg and Tardos, and by Dasgupta, Papadimitrioiu and Vazirani. The slides and notes are typeset using LaTeX and the beamer package.