Date 
Topics 
Reading 
Tuesday, August 24 
Administrivia, overview, motivation, graph basics, DFS 
Chapters 13 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, Singlesource 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: 79pm, 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 
FordFulkerson 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: 79pm, 1404 Siebel 
Topics 
Tuesday, November 9 
Polynomial time Reductions 
Chapter 8 
Thursday, November 11 
SAT and Definition of NP 
Chapter 8 
Tuesday, November 16 
NPCompleteness, Circuit Sat and CookLevin Theorem 
Chapter 8 
Thursday, November 18 
More NPComplete Problems 
Chapter 8 
Tue/Thu, November 23, 25 
Thanksgiving Break 

Tuesday, November 30 
P, NP, coNP, 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.304.30pm in 1404 Siebel (1302 is overflow room) 
