Tentative Schedule

This midterms and lectures may be not on the correct date. This schedule is very preliminary: the number of lectures and order of the topics are likely to change.

Lec. Instr. Date Day Topic Assignments
1 G Jan 11 T Introduction, asymptotic analysis, Strassen's alg.
[Mathematical Background | Class Notes ]
recitation Jan 12 W asymptotic notations, Strassen's alg.
[ Class Notes ]
2 V Jan 13 R solving recurrences and Karatsuba's alg.
[ Karatsuba and Strassen]
Hwk 1 out [PDF | TEX]
3 G Jan 18 T Dynamic Programming
[ Classical examples |
Lewis and Denenberg Optimal BST |
Optimal BST |
Fitting Fcns to Data]
recitation Jan 19 W Dynamic Programming
[ Optimal BST | Optimal Alphabetic BST]
Hwk 2 out [PDF | TEX]
4 G Jan 20 R More Dynamic Programming
[ Classnotes Fitting | Classnotes BST | CLRS Opt BST ]
Hwk 1 due
[Solutions PDF]
5 V Jan 25 T Amortized Analysis - Binomial Heaps
[ Amortized Analysis]
Quiz 1 [Solutions PDF]
recitation Jan 26 W Binomial Heaps
[ Class Notes ]
Hwk 2 checkpoint [Solutions PDF]
6 G Jan 27 R Treaps
[ ClassNotes | Treaps ]
7 G Feb 01 T Amortized Analysis - Splay Trees
[ ClassNotes | Sleator's Notes]
recitation   Feb 02   W Treaps
[ Class Notes ]
Hwk 2 due
[Solutions PDF]
8 V Feb 03 R Randomized Quicksort and Linear-time Selection
[ Quicksort | Quickselect ]
Hwk 3 out [PDF| TEX]
9 G Feb 08 T Computational Geometry I: Introduction and Sweep Line
Intro | Sweep-Line | Class Notes | BKOS Sweep Line ]
Quiz 2 [Solutions PDF]
recitation Feb 09 W Splay Trees
[ MoM Worksheet | Comp. Geometry ]
Hwk 4 out [PDF| TEX]
10 G Feb 10 R Computational Geometry II: Sweep Line, Convex Hull
[ Convex Hull | Class Notes ]
Hwk 3 due
[Solutions PDF]
11 G Feb 15 T Computational Geometry III: 2D-Linear Programming
[ 2D-LP | Class Notes | BKOS Chapter 4 ]
recitation Feb 16 W Bentley-Ottmann and Randomized Incremental
[ Powerpoint | Worksheet ]
Hwk 4 checkpoint [Solutions PDF]
12 V Feb 17 R Graph Algorithms I - MST && SSSP
[ A. Blum's notes |
Powerpoint ]
13 V Feb 22 T Graph Algorithms II - Biconnected Components
[ pdf]
Quiz 3 [Solutions PDF]
recitation Feb 23 W Biconnected Components
[ Powerpoint | Worksheet ]
Hwk 4 due [Solutions PDF]
14 G Feb 24 R Introduction to Linear Programming:
[ Class Notes | Readings: CLRS Chaper 29 ]
15 Mar 01 T Max Flow I: Intro
[ CLRS 26.1 and 26.2 | Kozen 16 | Class Notes ]
recitation Mar 02 W TBA
[ Class Notes ]
Mar 03 R Midterm
Mar 08 T Spring Break
Mar 10 R Spring Break
16 Mar 15 T Linear Programming Duality
[ G. Gordon's notes | Class Notes 1 | Class Notes 2 ]
recitation Mar 16 W Max Flow and Duality
[ Powerpoint | Worksheet ]
17 Mar 17 R Maximum Flow via Preflow-Push
[ KT 7.4 | CLRS Chapter 26.4 | Class Notes ]
Hwk 5 out [PDF| TEX]
18 Mar 22 T Parallel Algorithms I
[ Class Notes]
recitation Mar 23 W Push Relabel Max Flow
[ Powerpoint | Worksheet ]
Hwk 5 checkpoint
[Solutions PDF]
19 Mar 24 R Parallel Algorithms II: Prescan and List-Ranking
[ Class Notes | Prefixsum Blelloch | List Ranking Reid-Miller ]
Quiz 4 [Solutions PDF]
20 Mar 29 T Parallel Algorithms III: List-Ranking using Random-Mate
[ Class Notes]
recitation Mar 30 W Wyllie's Algorithm
[ Powerpoint | Worksheet ]
Hwk 5 due
[Solutions PDF]
21 Mar 31 R Parallel Algorithms IV: Tree Contraction
[ Class Notes]
Hwk 6 out [PDF]
22 Apr 05 T NP-Completeness I: Intro
[ Read CLRS Chapter 34 | Class Notes ]
recitation Apr 06 W Parallel List Ranking and Tree Contraction
[ Powerpoint ]
23 Apr 07 R NP-Completeness II
[ Class Notes | CLRS 34.4 ]
24 Apr 12 T NP-Completeness III
[ Class Notes | CLRS 34.4 ]
Quiz 5 [Solutions PDF]
recitation Apr 13 W Reductions
[ Powerpoint | Worksheet ]
Apr 14 R Spring Carnival
Spring Carnival
25 Apr 19 T Online Algorithms
[ Online]
Hwk 6 due
[Solutions PDF]
recitation Apr 20 W Online Algorithms
[ Powerpoint ]
Hwk 7 out [PDF| TEX]
26 Apr 21 R Fast Fourier Transform
[ FFT | CLRS 30 ]
Quiz 6 [Solutions PDF]
27 Apr 26 T Approximation Algorithms
[ Class Notes | CLRS 35]
recitation Apr 27 W FFT
[Powerpoint ]
28 Apr 28 R Approximate Set Cover
[ Class Notes | CLRS 35.3 |