Date  Topics  Reading 

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

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

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

Discussion 5  
Tuesday, February 19 
Review session:
Lecture
(notes and handout versions) 

 
Midterm 1: 7:00 PM to 9:00 PM 1EVRT 151 7:00 PM to 9:00 PM 1LMS 151 
Topics 
Thursday, February 21 
10:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and handout versions) 

Discussion 6  
Tuesday, February 26 
11: Greedy Algorithms: Examples and Proof
Techniques
(notes and handout versions) 

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

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

Discussion 9  
March 16  March 24 
Spring break 

Tuesday, March 26 
17:
FordFulkerson Algorithm for Maximum Flow and
Minimum Cut (notes and handout versions). 

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

Discussion 10  
Tuesday, April 2 
Midterm 2: 7:00 PM to 9:00 PM 1NOYES 217 7:00 PM to 9:00 PM 1MH 103 
Review session slides Topics 
Thursday, April 4 
19: More Applications of Network Flow
(notes and handout versions) Even more notes 

Discussion 11  
Tuesday, April 9 
20: Polynomial time Reductions
(notes and handout versions) 

Thursday, April 11 
21: SAT and Definition of NP
(notes and handout versions) 

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

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

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

Thursday, April 25 
Catch up lecture  
Discussion 14  
25: Linear programming
(notes and handout versions) 
Chapter 9  
Discussion 15  
Final exam  Topics: final topics  
May 3, 7pm10pm 
1DKH 114 David Kinley Hall, Room 114. 
Proof 
Conflict to final exam  you need permission from instructors to take it!  
May 6, 7pm10pm 
1EB 160 English Building, Room 160. 
Proof 
Date  Topics  Reading 

26: Heuristics, Closing thoughts
(notes and handout versions) 