CS473 - Fundamental Algorithms - Fall 2009

Schedule and Lecture Notes

Date Topics Reading
Tuesday, August 25 Administrivia, overview, motivation, potpourri Chapters 1-3 from text book, Jeff Erickson's notes on recurrences
Thursday, August 27 Recursion, Divide and Conquer, Sorting, Multiplication, Recurrences Chapter 5, Jeff's notes on recurrences
Tuesday, September 1 Recurrences, Closest Pair, Quick Sort and Quick Selection Chapter 5
Thursday, September 4 Finish quick selection. Exponentiation, binary search. Graph basics Chapter 5, Chapter 3
Tuesday, September 8 Depth First Search, Strong Components, DAGs Chapter 3 of text book and Chapter 3 of Dasgupta etal book.
Thursday, September 10 BFS, Application to Bipartite Graphs, Single-Source Shortest Paths Chapter 3 of text book and Chapter 3 of Dasgupta etal book.
Tuesday, September 15 Shortest Paths with Negative Lengths, Bellman-Ford algorithm Chapter 3 of Dasgupta etal book
Thursday, September 17 Continue last lecture  
Tuesday, September 22 Greedy Algorithms: Examples and Proof Techniques Chapter 4
Thursday, September 24 Greedy Algorithms of Minimum Spanning Trees. Implementation Issues Chapter 4
Tuesday, September 29 Catch up lecture  
Thursday, October 1 Midterm 1: 7-9pm Noyes Hall 217  
Tuesday, October 6 Introduction to Dynamic Programming Chapter 6
Thursday, October 8 Weighted Interval Scheduling and Longest Increasing Subsequence Chapter 6 and lecture notes
Tuesday, October 13 Dynamic Programming: Max Weight Indep Set in Trees, Edit Distance Chapter 6 and lecture notes
Thursday, October 15 Dynamic Programming: All-Pairs Shortest Paths, Knapsack, TSP Chapter 6 and lecture notes
Monday, October 19 Drop Deadline  
Tuesday, October 20 Introduction to Network Flows Chapter 7
Thursday, October 22 Ford-Fulkerson for Maximum Flow and Minimum Cut Chapter 7
Tuesday, October 27 Network Flow Applications: Disjoint Paths and Bipartite Matching Chapter 7
Thursday, October 29 More Network Flow Applications Chapter 7
Tuesday, November 3 Introduction to Linear Programming Lecture notes, Dasgupta etal book
Thursday, November 5 Midterm 2: 7-9pm Siebel 1105 and 1109  
Tuesday, November 10 Polynomial-time Reductions Chapter 8
Thursday, November 12 The SAT problem and Definition of NP Chapter 8
Tuesday, November 17 NP-Completeness, Circuit Sat and Cook-Levin Theorem Chapter 8
Thursday, November 19 More NP-Complete Problems Chapter 8
Tue/Thu, November 24, 26 Thanksgiving Break  
Tuesday, December 1 P, NP, co-NP, Self Reductions Chapter 8
Thursday, December 3 Flavor of Approximation Algorithms Lecture notes and Chapter 11
Tuesday, December 8 Heuristic methods, closing thoughts Chapter 9 in Dasgupta etal book
Thursday, December 17 Final Exam: 1.30-4.30pm, 1404 Siebel  


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.