Lec.
 Date
 Day
 Topic
 Notes

1 
Aug 28 
Th 
Introduction, Karatsuba/Strassen 

2 
Sep 2 
T 
Asymptotic analysis, recurrences

HW1 out

3 
Sep 4 
Th 
Probabilistic analysis, randomized quicksort 

4 
Sep 9 
T 
Linear time selection/median 
HW1 due, HW2 out

5 
Sep 11 
Th 
Sorting: O(1) algorithms and Ω(n log n) lower bound 

6 
Sep 16 
T 
Amortized Analysis 
HW2 due, HW3 out

7 
Sep 18 
Th 
UnionFind 

8 
Sep 23 
T 
Priority Queues/Heaps 
HW3 due

9 
Sep 25 
Th 
Search trees: Btrees and treaps 

10 
Sep 30 
T 
Midterm 1

HW4 out

11 
Oct 2 
Th 
Universal and perfect hashing 

12 
Oct 7 
T 
Dynamic Programming 
HW4 due, HW5 out

13 
Oct 9 
Th 
BFS, DFS, topological sort, stronglyconnected components 

14 
Oct 14 
T 
Shortest paths 
HW5 due, HW6 out


Oct 16 
Th 
No Class (Monday schedule)


15 
Oct 21 
T 
Minimum spanning trees 
HW6 due, HW7 out

16 
Oct 23 
Th 
Matroids and Greedy Algorithms 

17 
Oct 28 
T 
Maxflow Mincut 
HW7 due

18 
Oct 30 
Th 
Midterm 2


19 
Nov 4 
T 
Maxflow: EdmondsKarp 
HW8 out

20 
Nov 6 
Th 
Linear programming 

21 
Nov 11 
T 
NPcompleteness I 
HW8 due, HW9 out

22 
Nov 13 
Th 
NPcompleteness II 

23 
Nov 18 
T 
Approximation algorithms 
HW9 due, HW10 out

24 
Nov 20 
Th 
Online algorithms 


Nov 25 
T 
No Class: Thanksgiving break 


Nov 27 
Th 
No Class: Thanksgiving break 

25 
Dec 2 
T 
Machine Learning Theory 
HW10 due

26 
Dec 4 
Th 
Game Theory 
