
Date 
Topics 
Additional reading 

Tuesday,
January 20 
1: Administrivia, overview, motivation, graph
basics, DFS
(notes and
handout versions)

Jeff Erickson's notes on
induction/proofs 

Thursday,
January 22 
2: DFS in Directed Graphs and DAGs
(notes and
handout versions)


Discussion 1 


Tuesday,
January 27 
3:
Strong connected components
(notes and
handout versions)



Thursday,
January 29 
4:
BFS, Singlesource Shortest Paths
(notes and
handout versions)

Jeff Erickson's notes

Discussion 2 


Tuesday,
February 3 
5:
Shortest Paths with Negative Edge
Lengths
(notes and
handout versions)

Jeff Erickson's notes
on recurrences 

Thursday,
February 5 
6: Reductions, Recursion, Divide and
Conquer
(notes and
handout versions) 
Jeff Erickson's notes
on recurrences 
Discussion 3 


Tuesday,
February 10 
7: Recurrences, Closest Pair, Quick Sort and Quick
Selection
(notes and
handout versions) 


Thursday,
February 12 
8: Exponentiation, Binary Search, Intro
to Dynamic Programming
(notes and
handout versions) 

Discussion 4 


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



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


Discussion 5 


Tuesday,
February 24

Review session:
Lecture
(notes and
handout versions)


 
Midterm 1:
7:00 PM to 9:00 PM ARMRY 101

Topics 

Thursday,
February 26 
11:
Dynamic Programming: Shortest
Paths, Knapsack
(notes and
handout versions)


Discussion 6 


Tuesday,
March 3 
12: Greedy Algorithms: Examples and Proof
Techniques
(notes and
handout versions)



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


Discussion 7 


Tuesday,
March 10 
14: Introduction to Randomized Algorithms
(notes and
handout versions)

Lecture Notes, Jeff Erickson's notes 

Thursday,
March 12

15: Randomized Quick Sort and Selection
(notes and
handout versions)

Lecture Notes,
Jeff Erickson's notes


Friday, March 13 
Drop Deadline 

Discussion 8 


Tuesday,
March 17

16: Hash Tables
(notes and
handout versions)

Lecture Notes, Jeff Erickson's
notes


Thursday,
March 19 
17: Introduction to Network Flows
(notes and handout versions)


Discussion 9 


March 21  29 
Spring break
UnThanksgiving Vacation




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



Thursday,
April 2 
19: Applications of Network Flow: Disjoint
Paths and Bipartite Matchings
(notes and
handout versions)


Discussion 10 


Tuesday,
April 7

Midterm 2:
7:00 PM to 9:00 PM Armory 101

Review session slides
Topics


Thursday,
April 9

20: More Applications of Network Flow
(notes and
handout versions)
Even more notes


Discussion 11 


Tuesday,
April 14 
21: Polynomial time Reductions
(notes and
handout versions)



Thursday,
April 16

22: SAT and Definition of NP
(notes and
handout versions)


Discussion 12 


Tuesday,
April 21 
23: NPCompleteness, Circuit Sat and CookLevin
Theorem
(notes and
handout versions)



Thursday,
April 23

24:
More NPComplete Problems
(notes and
handout versions)


Discussion 13 


Tuesday,
April 28 
25: Introduction to Linear Programming
(notes and
handout versions)



Thursday,
April 30 
26:
Approximation algorithms using
Linear Programming
(notes and
handout versions)


Discussion 14 


Tuesday,
May 5 
27: Review for the final
(notes and
handout versions)


Discussion 15 



Final exam 
Topics: final topics 


Thursday, May 14th. 
May 14, 7pm10pm 
Roger Adams Laboratory, 116
Proof.
directions.




Conflict to final exam  you need
permission from instructors to take it! 

May ???, 7pm10pm 
TBD

