Date  Topics  Reading 

Tuesday, January 18  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, January 20  2: DFS in Directed Graphs,
Strong Connected Components, DAGs
(notes and handout versions) 
Chapter 3 of book 
Tuesday, January 25  3: BFS, Singlesource Shortest Paths
(notes and handout versions) 
Chapter 3 of book 
Thursday, January 27  4: Shortest Paths with Negative Edge
Lengths
(notes and handout versions) 
Chapter 3 of Dasgupta etal book, Jeff Erickson's notes 
Tuesday, February 1  5: Reductions, Recursion, Divide and
Conquer
(notes and handout versions) 
Chapter 5, Jeff Erickson's notes on recurrences 
Thursday, February 3  6: Recurrences, Closest Pair, Quick Sort and Quick Selection  Jeff Erickson's notes on recurrences 
Tuesday, February 8  Catch up lecture  
Thursday, February 10  7: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and handout versions) 

Tuesday, February 15  8: Dynamic Programming: Longest
Increasing Subsequence, Weighted Interval Scheduling
(notes and handout versions) 

Thursday, February 17  9: Dynamic Programming: Independent
Sets in Trees, Edit Distance
(notes and handout versions) 

Tuesday, February 22 
10:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and handout versions) 

Thursday, February 24  Midterm 1: 79pm in LMS 141  Topics 
Tuesday, March 1 
11: Greedy Algorithms: Examples and Proof
Techniques
(notes and handout versions) 

Thursday, March 3 
12: Greedy Algorithms for Minimum
Spanning Tree
(notes and handout versions) 

Tuesday, March 8  13: Introduction to Randomized Algorithms
(notes and handout versions) 
Lecture Notes, Jeff Erickson's notes 
Thursday, March 10  14: Randomized Quick Sort and Selection
(notes and handout versions)  Lecture Notes, Jeff Erickson's notes 
Friday, March 11  Drop Deadline  
Tuesday, March 15  15: Hash Tables
(notes and handout versions) 
Lecture Notes, Jeff Erickson's notes 
Thursday, March 17  16: Introduction to Network Flows
(notes and handout versions) 

Tuesday, March 1928  Spring break  
Tuesday, March 29 
17: FordFulkerson Algorithm for Maximum Flow
and Minimum Cut
(notes and handout versions) 

Thursday, March 31  18: Applications of Network Flow: Disjoint Paths
and Bipartite Matchings
(notes and handout versions) 

Tuesday, April 5  19: More Applications of Network Flow
(notes and handout versions) Even more notes 

Thursday, April 7  20: Polynomial time Reductions
(notes and handout versions) 

Tuesday, April 12  Midterm 2: 79pm in SC 1404  Topics (Updated) 
Thursday, April 14 
21: SAT and Definition of NP
(notes and handout versions) 

Tuesday, April 19 
22: NPCompleteness, Circuit Sat and CookLevin
Theorem
(notes and handout versions) 

Thursday, April 21  23:
More NPComplete Problems
(notes and handout versions) 

Tuesday, April 26 
24: P, NP, coNP, Self Reductions
(notes and handout versions) 

Thursday, April 28  Catch up lecture  
Tuesday, May 3 
25: Heuristics, Closing thoughts
(notes and handout versions) 
Chapter 9 
Wednesday, May 11  Final Exam: 1:304:30 