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 17 T Introduction, asymptotic analysis, Strassen's alg.
[Mathematical Background | Class Notes | Related Work]
recitation Jan 18 W asymptotic notations, Strassen's alg.
[ Class Notes ]
2 V Jan 19 R solving recurrences and Karatsuba's alg.
[ Karatsuba and Strassen | PPT]]
Hwk 1 out [PDF | TEX]
3 V Jan 24 T Fast Fourier Transform
[ FFT | CLRS 30 ]
recitation Jan 25 W FFT
[ Class Notes ]
Hwk 1 due
[Solutions PDF]
4 G Jan 26 R Dynamic Programming
[ Classical examples |
Lewis and Denenberg Optimal BST |
Optimal BST |
Fitting Fcns to Data]
Hwk 2 out [PDF | TEX]
5 G Jan 31 T More Dynamic Programming
[ Classnotes Fitting ]
recitation Feb 01 W Dynamic Programming
[ Class Notes ]
Hwk 2 checkpoint
6 V Feb 02 R Amortized Analysis - Binomial Heaps
[ Amortized Analysis | CLRS 17 and 19 ]
7 G Feb 07 T Treaps
[ ClassNotes | Treaps ]
recitation   Feb 08   W Amortized Analysis
[ Class Notes ]
Hwk 2 due
[Solutions PDF]
8 G Feb 09 R Amortized Analysis - Splay Trees
[ ClassNotes | Sleator's Notes]
Hwk 3 out [PDF]
9 V Feb 14 T Randomized Quicksort and Linear-time Selection
[ Quicksort | Quickselect ]
recitation Feb 15 W Treaps
[ Class Notes ]
Hwk 3 due
[Solutions PDF]
10 G Feb 16 R Computational Geometry I: Introduction and Sweep Line
Intro | Sweep-Line | Class Notes | BKOS Sweep Line ]
11 V Feb 21 T Computational Geometry II: Convex Hull
[ Convex Hull | PPT slides ]
recitation Feb 22 W review for exam
Feb 23 R Midterm
[ practice exam | solutions]
 Hwk 4 out [PDF]
12 G Feb 28 T Computational Geometry III: Random Incremental
[ Class Notes on Random Incremental 2D Hull | Class Notes on 2D-LP | BKOS Chapter 4 ]
recitation Feb 29 W Computational Geometry
13 G Mar 01 R Computational Geometry VI: 2D-Linear Programming
[ Class Notes on 2D-LP Continued | 2D-LP ]
14 V Mar 06 T Graph Algorithms I - MST && SSSP
[ A. Blum's notes | PPT slides ]
recitation Mar 07 W Smallest Circle Problem
[ Notes ]
Hwk 4 due [Solutions PDF]
15 V Mar 08 R Graph Algorithms II - Biconnected Components
[ PPT slides]
Hwk 5 out [PDF | TeX ]
Mar 13 T Spring Break
Mar 15 R Spring Break
16 Mar 20 T Introduction to Linear Programming:
[ Class Notes | Readings: CLRS Chaper 29 ]
recitation Mar 21 W Graph Algorithms
[ PPT slides ]
17 Mar 22 R Max Flow I: Intro
[ CLRS 26.1 and 26.2 | Kozen 16 | Class Notes ]
Hwk 5 due [Solutions PDF]
18 Mar 27 R Maximum Flow via Preflow-Push
[ KT 7.4 | CLRS Chapter 26.4 | Class Notes ]
recitation Mar 28 W Max Flow
[ PPT slides ]
19 Mar 29 T Linear Programming Duality
[ Trevisan's notes | G. Gordon's notes | Class Notes |
Hwk 6 out [PDF | TeX ]
20 Apr 03 T Parallel Algorithms I
[ Class Notes]
recitation Apr 04 W Push Relabel
[ PPT slides ]
21 Apr 05 R Parallel Algorithms II: Prescan and List-Ranking
[ Class Notes | Prefixsum Blelloch | List Ranking Reid-Miller ]
22 Apr 10 T Parallel Algorithms III: List-Ranking using Random-Mate
[ Class Notes]
Hwk 6 due
recitation Apr 11 W Parallel List Ranking
23 Apr 12 T Parallel Algorithms IV: Tree Contraction
[ Class Notes]
Apr 17 R Midterm
recitation Apr 18 W Reductions
Apr 19 R Spring Carnival
24 Apr 24 T NP-Completeness I: Intro
[ Read CLRS Chapter 34 | Class Notes ]
Hwk 7 out [PDF]
recitation Apr 25 W NP-Completeness
25 Apr 26 R NP-Completeness II
[ Class Notes | CLRS 34.4 ]
26 May 01 T NP-Completeness III
[ Class Notes | Kozen 23-24 ]
recitation May 02 W TBA
27 May 03 R Approximation Algorithms
[ Class Notes | KT-11.2 ]
Hwk 7 due
May 9 Wed Review for the Final 7-9PM GHC 4102
May 11 Fr Final Exam: 8:30-11:30 a.m DH 2302