# 
Date 
Topic 
Raw Notes 
Scribe Notes 
Lec Videos 
1. 
Wed, Sep. 3: 
Course introduction. Fibonacci heaps. MST. 
nb 
nb 
2. 
Fri, Sep. 5: 
Fibonacci heaps. MST. 
nb 

3. 
Mon, Sep. 8: 
Persistent data structures. 
nb 
nb 
4. 
Wed, Sep. 10: 
Splay trees. 
nb 
nb 
nb 
5. 
Fri, Sep. 12: 
Dial's Algorithm. Tries. Multilevel buckets. Van Emde Boas queues. 
nb 
nb 
6. 
Mon, Sep. 15: 
Van Emde Boas queues cont. Hashing. 


nb 
7. 
Wed, Sep. 17: 
Universal Hashing. Perfect Hashing. 
nb 
nb 
nb 

Fri, Sep. 19: 
Student holiday, no class 
8. 
Mon, Sep. 22: 
Network Flows. Characterization. Decomposition. Augmenting Paths. 


nb 
9. 
Wed, Sep. 24: 
Network Flows: Maximum augmenting path. scaling. 
nb 
nb 
nb 

Fri, Sep. 26: 
Optional lecture: Suffix Trees 
nb 
10. 
Mon, Sep 29: 
Network Flows: Strongly polynomial algorithms. Shortest augmenting path. Blocking flows. 
nb 
nb 
nb 
11. 
Wed, Oct. 1: 
Network Flows: More blocking flows. Link Cut trees. MinCost
Flows. Definitions. Chatacterization. Pseudopolynomial algorithm:
cycle canceling.

nb 
nb 
nb 
12. 
Fri, Oct. 3: 
MinCost Flows: Feasible prices. Polynomial algorithms:
shortest augmenting path; scaling. 

nb 
nb 
13. 
Mon, Oct. 6: 
Linearprogramming: definitions: canonical and standard forms, feasibility and optimization. Structure of Optima. 
nb 
nb 
nb 
14. 
Wed, Oct. 8 
LinearProgramming: Duality Theory.
 
nb 
nb 

Fri, Oct. 10: 
Optional lecture 

Mon, Oct. 13: 
Columbus Day, no class. 


15. 
Wed, Oct. 15 
LinearPrograming: Duality Applications. 



Fri, Oct. 17 
Optional lecture 


16. 
Mon, Oct. 20: 
Linear Programming Algorithms: Simplex 

nb 

17. 
Wed, Oct. 22: 
LinearProgramming Algorithms: Eillipsoid. 


18. 
Fri, Oct. 24: 
LinearProgramming Algorithms: Interior Point. 


19. 
Mon, Oct. 27: 
NPhard problems.
Approximation Algorithms. Relative Approximations. 
nb 
nb 
20. 
Wed, Oct. 29: 
PAS and FPAS. Scheduling.
 
nb 
21. 
Fri, Oct. 31 
Relaxations. 3/2approximation for TSP. ILP relaxations. 

nb 
22. 
Mon, Nov. 3 
ILP relaxations. Randomized Rounding. 


23. 
Wed, Nov. 5 
Online Algorithms: ski rental, load balancing 
online 
nb 
24. 
Fri, Nov. 7 
Online algorithms: linked lists, paging. 
Erik's Notes 
nb1 nb2 

Mon, Nov. 10 
Veteran's Day, no class. 


25. 
Wed, Nov. 12 
Randomized online algorithms, adversaries. kserver. 


26. 
Fri, Nov. 14 
Computational geometry: orthogonal range search, Voronoi diagram.

nb 

27. 
Mon, Nov. 17 
Computational geometry: convex hull, sweep line,
Voronoi diagram (Fortune's algorithm animation) 

nb nb 
28. 
Wed, Nov. 19 
External memory algorithms. 
nb 


Fri, Nov. 21 
Cache oblivious algorithms. 



Mon, Nov. 24 
Parallel algorithms. 



Wed, Nov. 26 
Fixedparameter tractability, treewidth. 



Wed, Nov. 27 
Thanksgiving 



Wed, Dec. 10 
Final Project due date. 

