CS473: Fundamental Algorithms (Fall 2011)

Schedule and Lecture Notes

Date Topics Reading
Tuesday,
August 23
1: Administrivia, overview, motivation, graph basics, DFS
(notes and handout versions)
Chapter 0, section 1.1 and 1.2 from textbook, Jeff Erickson's notes on induction/proofs
Thursday,
August 25
2: DFS in Directed Graphs, Strong Connected Components, DAGs
(notes and handout versions)
Slides annotated during lecture
Chapter 3 of book
Tuesday,
August 30
3: BFS, Single-source Shortest Paths
(notes and handout versions)
Slides annotated during lecture
Chapter 3 of book
Thursday,
September 1
4: Shortest Paths with Negative Edge Lengths
(notes and handout versions)
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes
Tuesday,
September 6
5: Reductions, Recursion, Divide and Conquer
(notes and handout versions)
Chapter 5, Jeff Erickson's notes on recurrences
Thursday,
September 8
6: Recurrences, Closest Pair, Quick Sort and Quick Selection Jeff Erickson's notes on recurrences
Tuesday,
September 13
Catch up lecture
 
Thursday,
September 15
7: Exponentiation, Binary Search, Intro to Dynamic Programming
(notes and handout versions)
 
Tuesday,
September 20
8: Catchup lecture
 
Thursday,
September 22
9: Review session: Lecture
(notes and handout versions)
 
Monday,
September 26
Midterm 1: 7-9pm in 1404 SC Topics
Tuesday,
September 27
Dynamic Programming: Longest Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions)
Dynamic Programming: Independent Sets in Trees, Edit Distance
(notes and handout versions)

Thursday,
September 29
10: Dynamic Programming: Shortest Paths, Knapsack
(notes and handout versions)
 
Tuesday,
October 4
11: Greedy Algorithms: Examples and Proof Techniques
(notes and handout versions)
 
Thursday,
October 6
12: Greedy Algorithms for Minimum Spanning Tree
(notes and handout versions)
 
Tuesday,
October 11
13: Introduction to Randomized Algorithms
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
October 13
14: Randomized Quick Sort and Selection
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Friday, Octaber 14 Drop Deadline  
Tuesday,
October 18
15: Hash Tables
(notes and handout versions)
Lecture Notes, Jeff Erickson's notes
Thursday,
October 20
16: Introduction to Network Flows
(notes and handout versions)
 
Tuesday,
October 25
17: Ford-Fulkerson Algorithm for Maximum Flow and Minimum Cut
(notes and handout versions)
 
Thursday,
October 27
18: Applications of Network Flow: Disjoint Paths and Bipartite Matchings
(notes and handout versions)
 
Tuesday,
November 1
19: More Applications of Network Flow
(notes and handout versions)
Even more notes
 
Thursday,
November 3
20: Polynomial time Reductions
(notes and handout versions)
 
Tuesday,
November 8
Midterm 2: 7-9pm in SC 1404 Review session slides Topics
Thursday,
November 10
21: SAT and Definition of NP
(notes and handout versions)
 
Tuesday,
November 15
22: NP-Completeness, Circuit Sat and Cook-Levin Theorem
(notes and handout versions)
 
Thursday,
November 17
23: More NP-Complete Problems
(notes and handout versions)
 
November 19-November 27 Spring, UnSpring break , Thanksgiving Vacation
Tuesday,
November 29
24: P, NP, co-NP, Self Reductions
(notes and handout versions)
 
Thursday,
December 1
Catch up lecture  
Tuesday,
December 6
25: Heuristics, Closing thoughts
(notes and handout versions)
Chapter 9
Friday,
December 9
Final Exam: 1:30-4:30 p.m.
 




Acknowledgments: Lecture notes are based on notes of Jeff Erickson, Sariel Har-Peled, Chandra Chekuri 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.
Last modified: Tue Nov 8 16:38:22 CST 2011