Lec.
 Date
 Day
 Topic
 Notes

1 
Jan 12 
M 
Introduction and Strassen's Algorithm 
Hwk 0 out [PDF]

2 
Jan 14 
W 
Binomial Heaps 

3 
Jan 16 
F 
Fibonacci Heaps 


Jan 19 
M 
Martin Luther King Day, No Class


4 
Jan 21 
W 
BST Introduction and Treaps 

5 
Jan 23 
F 
Treaps II and Splay Trees I 
Hwk 0 due (Solutions PDF) Hwk 1 out [PDF]

6 
Jan 26 
M 
Splay Trees II


7 
Jan 28 
W 
Dynamic Programming: Optimal BST's 

8 
Jan 30 
F 
Dynamic Programming: Uniquely Decipherable Codes 

9 
Feb 02 
M 
Computational Geometry: Introduction and Sweep Line 

10 
Feb 04 
W 
Sorting, Convex Hull, and 2D Random Incremental Convex Hull 

11 
Feb 06 
F 
Linear Programming: 2D Random Incremental 
Hwk 1 due (Solutions PDF) Hwk 2 out [PDF]

12 
Feb 09 
M 
Linear Programming: Introduction 

13 
Feb 11 
W 
Linear Programming the Simplex Algorithm 

14 
Feb 13 
F 
Max Flow I: Intro 

15 
Feb 16 
M 
Max Flow II: PreflowPush 

16 
Feb 18 
W 
PreflowPush analysis


17 
Feb 20 
F 
Review Session

Hwk 2 due (Solutions PDF)


Feb 23 
M 
Midterm I (Tentative Date)

Hwk 3 out [PDF]

18 
Feb 25 
W 
Graph Algorithms: Depthfirst Search 


Feb 27 
F 
No Class CSD Open House


19 
Mar 02 
M 
Graph Algorithms: Strongly Connected Components 

20 
Mar 04 
W 
FFT 


Mar 06 
F 
Midsemester Break 


Mar 09 
M 
Spring Break 


Mar 11 
W 
Have a nice break! 


Mar 13 
F 
Spring Break 

21 
Mar 16 
M 
Simple String Matching Algorithms 
Hwk 4 out [PDF]

22 
Mar 18 
W 
FFT and Approximate String Matching 
Hwk 3 due (Solutions PDF)

23 
Mar 20 
F 
Resistive Model of a Graph 

24 
Mar 23 
M 
Random Walks and Electricity 

25 
Mar 25 
W 
Solving Linear Systems, Direct Methods 

26 
Mar 27 
F 
Linear System Solvers: Iterative Methods 

27 
Mar 30 
M 
Linear System Solvers: Iterative Methods Part II 
Hwk 4 due (Solutions PDF) Hwk 5 out [PDF]

28 
Apr 01 
W 
Parallel Algorithms: Parallel models, Work and Time, Prefixsum, ListRanking 

29 
Apr 03 
F 
Midterm Review



Apr 06 
M 
Midterm II

Practice Midterm (PDF) Solutions (PDF)

30 
Apr 08 
W 
Parallel Algorithms: More Listranking, Parallel Tree Contraction 

31 
Apr 10 
F 
Parallel Algorithms: Parallel Tree Contraction and Maximal Independent Set 

32 
Apr 13 
M 
Planar Graphs: Separator Theorem 

33 
Apr 15 
W 
PLanar Separator continued and NPCompleteness I 
Hwk 5 due (Solutions PDF) Hwk 6 out [PDF]


Apr 17 
F 
Spring Carnival 

34 
Apr 20 
M 
NPCompleteness II 

35 
Apr 22 
W 
NPCompleteness III 

36 
Apr 24 
F 
Approximation Algorithms I 

37 
Apr 27 
M 
Online Algorithms I 

38 
Apr 29 
W 
Randomized Online Algorithms II 

39 
May 01 
F 
Approximation Algorithms II

Last day of classes Hwk 6 due (Solutions PDF)

40 
May 04 
M 

Final 14PM in WEH 7500
