Lec.
 Date
 Day
 Topic
 Notes

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

2 
Jan 13 
W 
Binomial Heaps 

3 
Jan 15 
F 
Fibonacci Heaps 


Jan 18 
M 
Martin Luther King Day, No Class


4 
Jan 20 
W 
BST Introduction and Treaps 

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

6 
Jan 25 
M 
Splay Trees II


7 
Jan 27 
W 
Dynamic Programming: Optimal BST's 

8 
Jan 29 
F 
Dynamic Programming: Uniquely Decipherable Codes 

9 
Feb 01 
M 
Computational Geometry: Introduction and Sweep Line 

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

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


Feb 08 
M 
No Class Snow Day



Feb 10 
W 
No Class Snow Day


12 
Feb 12 
F 
Linear Programming: Introduction 

13 
Feb 15 
M 
Linear Programming the Simplex Algorithm 

14 
Feb 17 
W 
Max Flow I: Intro 

15 
Feb 19 
F 
Max Flow II: PreflowPush 
Hwk 2 due (Solutions PDF)

16 
Feb 22 
M 
PreflowPush analysis 
Hwk 3 out [PDF]

17 
Feb 24 
W 
Graph Algorithms: Depthfirst Search 


Feb 26 
F 
No Class CSD Open House

Open House

18 
Mar 01 
M 
Graph Algorithms: Strongly Connected Components 

19 
Mar 03 
W 
FFT 


Mar 05 
F 
Midsemester Break 
Spring Break


Mar 07 
S 
Spring Break 
Spring Break


Mar 10 
W 
Have a nice break! 
Spring Break


Mar 12 
F 
Spring Break 
Spring Break

20 
Mar 15 
M 
Simple String Matching Algorithms 
Hwk 4 out [PDF]

21 
Mar 17 
W 
FFT and String Matching with Wildcards 
Hwk 3 due (Solutions PDF)

22 
Mar 19 
F 
Midterm Review

Practice Midterm (PDF) Solutions (PDF)


Mar 22 
M 
Midterm

Midterm

23 
Mar 24 
W 
Parallel Algorithms: Parallel models, Work and Time, Prefixsum, ListRanking 

24 
Mar 26 
F 
Parallel Algorithms: More Listranking, Parallel Tree Contraction 

25 
Mar 29 
M 
Parallel Algorithms: Parallel Tree Contraction 

26 
Mar 31 
W 
Parallel Algorithms: Maximal Independent Set 
Hwk 4 due (Solutions PDF) Hwk 5 out [PDF]

27 
Apr 02 
F 
Resistive Model of a Graph 

28 
Apr 05 
M 
Random Walks and Electricity 

29 
Apr 07 
W 
Solving Linear Systems, Direct Methods 

30 
Apr 09 
F 
Solving Linear Systems, Direct Methods continued


31 
Apr 12 
M 
Mixing Rates of Random Walks and Iterative Solvers 

32 
Apr 14 
W 
Planar Graphs: Separator Theorem 
Hwk 5 due (Solutions PDF) Hwk 6 out [PDF]


Apr 16 
F 
Spring Carnival 
Spring Carnival

33 
Apr 19 
M 
PLanar Separator continued and NPCompleteness I 

34 
Apr 21 
W 
NPCompleteness II 

35 
Apr 23 
F 
NPCompleteness III 

36 
Apr 26 
M 
Approximation Algorithms I 

37 
Apr 28 
W 
Online Algorithms I 

38 
Apr 30 
F 
The Weighted Majority Algorithm, Game Theory, and Lower Bounds for Randomized Algorithms 
Last day of classes Hwk 6 due (Solutions PDF)


May 06 
T 

Thu. May 6 Final: 8:30a.m.11:30a.m. DH 1212
