Tentative Schedule

This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Date Day Topic Notes
1 Aug 28 Th Introduction, Karatsuba/Strassen
[Lecture notes | CLRS 1, 2, 4.2]
2 Sep 2 T Asymptotic analysis, recurrences
[Lecture notes | CLRS 3, 4]
HW1 out
3 Sep 4 Th Probabilistic analysis, randomized quicksort
[Lecture notes | CLRS 5, 7]
4 Sep 9 T Linear time selection/median
[Lecture notes | CLRS 9]
HW1 due, HW2 out
5 Sep 11 Th Sorting: O(1) algorithms and Ω(n log n) lower bound
[Lecture Notes | CLRS 8]
6 Sep 16 T Amortized Analysis
[Lecture Notes | CLRS 17]
HW2 due, HW3 out
7 Sep 18 Th Union-Find
[Lecture Notes | CLRS 21]
8 Sep 23 T Priority Queues/Heaps
[Lecture Notes | CLRS 6]
HW3 due
9 Sep 25 Th Search trees: B-trees and treaps
[Lecture Notes from Avrim Blum | CLRS 18]
10 Sep 30 T Midterm 1
 HW4 out
11 Oct 2 Th Universal and perfect hashing
[Lecture notes from Avrim Blum | CLRS 11]
12 Oct 7 T Dynamic Programming
[Lecture notes | Lecture notes by Avrim Blum | CLRS 15]
HW4 due, HW5 out
13 Oct 9 Th BFS, DFS, topological sort, strongly-connected components
[Lecture notes | CLRS 22]
14 Oct 14 T Shortest paths
[Lecture notes | CLRS 24]
HW5 due, HW6 out
Oct 16 Th No Class (Monday schedule)
15 Oct 21 T Minimum spanning trees
[Lecture notes | CLRS 23]
HW6 due, HW7 out
16 Oct 23 Th Matroids and Greedy Algorithms
[Lecture notes | CLRS 16.4]
17 Oct 28 T Max-flow Min-cut
[Lecture Notes from Avrim Blum | CLRS 26]
 HW7 due
18 Oct 30 Th Midterm 2
19 Nov 4 T Max-flow: Edmonds-Karp
[Lecture Notes from Avrim Blum | CLRS 26]
HW8 out
20 Nov 6 Th Linear programming
[Lecture Notes from Avrim Blum | CLRS 29]
21 Nov 11 T NP-completeness I
[Lecture Notes | CLRS 34]
HW8 due, HW9 out
22 Nov 13 Th NP-completeness II
[Lecture Notes by Avrim Blum | CLRS 34]
23 Nov 18 T Approximation algorithms
[Lecture Notes | CLRS 35]
HW9 due, HW10 out
24 Nov 20 Th Online algorithms
[Lecture Notes from Avrim Blum]
Nov 25 T No Class: Thanksgiving break
Nov 27 Th No Class: Thanksgiving break
25 Dec 2 T Machine Learning Theory
[Lecture Notes]
HW10 due
26 Dec 4 Th Game Theory
[Lecture Notes]