Tentative Schedule

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

Lec.DateDayTopicAssignments
1Sep 1TIntroduction, Karatsuba/Strassen
[Lecture Notes | CLRS 1, 2, 4.2]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell video]
2Sep 3ThAsymptotic analysis, recurrences
[Lecture Notes | CLRS 3, 4]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
3Sep 8TIntro to proofs for algorithms
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell video]
4Sep 10ThLinear time selection/median
[Lecture Notes | CLRS 9]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell video | BFPRT demo app]
HW1 released
Sep 11FRecitation 1
[Recitation notes]
5Sep 15TSorting: O(n) algorithms and Ω(n log n) lower bound
[Lecture Notes | CLRS 8]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
6Sep 17ThBalanced Search Trees
[Lecture Notes | CLRS 12, 13, 18]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
HW1 due, HW2 released
Sep 18FRecitation 2
[Recitation notes]
7Sep 22TAmortized Analysis
[Lecture Notes | CLRS 16]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
8Sep 24ThHeaps
[Lecture Notes | CLRS 6 | Slides from Kevin Wayne]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
HW2 due, HW3 released
Sep 25FRecitation 3
[Recitation notes]
9Sep 29TUnion-Find
[Lecture Notes | CLRS 19]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides | Sorrell annotated slides | Sorrell video]
10Oct 1ThUniversal and Perfect Hashing
[Lecture Notes | CLRS 11]
[Dinitz slides | Dinitz annotated slides | Dinitz video]
[Sorrell slides]
HW3 due
11Oct 6TDynamic Programming I
[CLRS 14]
Oct 8ThMidterm 1
HW4 released
12Oct 13TDynamic Programming II
[CLRS 14]
13Oct 15ThBasic Graph Algorithms I
[CLRS 20]
HW4 due, HW5 released
14Oct 20TBasic Graph Algorithms II
[CLRS 20]
Oct 22ThNo Class: Fall break
HW5 due, HW6 released
15Oct 27TSingle-Source Shortest Paths
[CLRS 24]
16Oct 29ThAll-Pairs Shortest Paths
[CLRS 25]
HW6 due, HW7 released
17Nov 3TMinimum Spanning Trees
[CLRS 23]
18Nov 5ThMatroids and Greedy Algorithms
HW7 due, HW8 released
19Nov 10TMax-Flow Min-Cut
[CLRS 26.1 - 26.3]
20Nov 12ThMax-Flow II: Bipartite Matching, Edmonds-Karp
[CLRS 26.1 - 26.3]
HW8 due
21Nov 17TLinear Programming
[CLRS 29.1, 29.2]
Nov 19ThMidterm 2
HW9 released
Nov 24TNo Class: Thanksgiving break
Nov 26ThNo Class: Thanksgiving break
22Dec 1TNP-Completeness I
[CLRS 34]
23Dec 3ThNP-Completeness II
[CLRS 34]
HW9 due, HW10 released
24Dec 8TAdvanced Topics: TBD
25Dec 10ThAdvanced Topics: TBD
HW10 due
Dec 15TFinal Exam: 2:00-5:00 PM