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. Date Day Topic Notes
1 Jan 11 M Introduction and Strassen's Algorithm
[Lec 1 Kz | Class Notes]
Optional Reading: Mathematical Background
Hwk 0 out [PDF]
2 Jan 13 W Binomial Heaps
[ Lec 8 Kz | Class Notes]
3 Jan 15 F Fibonacci Heaps
[ Lec 9 Kz | Class Notes]
Jan 18 M Martin Luther King Day, No Class
4 Jan 20 W BST Introduction and Treaps
[ Read Kozen Chapter 13 | Class Notes]
5 Jan 22 F Treaps II and Splay Trees I
Reading: Kozen Chapter 12
[ Class Notes | Sleator's Notes]
Hwk 0 due (Solutions PDF)
Hwk 1 out [PDF]
6 Jan 25 M Splay Trees II
7 Jan 27 W Dynamic Programming: Optimal BST's
[ Lewis Denenberg 6.5 | Class Notes | CLRS Chap 15.5 ]
8 Jan 29 F Dynamic Programming: Uniquely Decipherable Codes
[ Class Notes | Class Notes | Even ]
9 Feb 01 M Computational Geometry: Introduction and Sweep Line
[ Intro | Sweep-Line | Class Notes | BKOS Sweep Line ]
10 Feb 03 W Sorting, Convex Hull, and 2D Random Incremental Convex Hull
[ CH Intro | Class Notes]
11 Feb 05 F Linear Programming: 2D Random Incremental
[ 2D LP Notes | Class Notes] ]
Hwk 1 due (Solutions PDF)
Hwk 2 out [PDF]
Feb 08 M No Class Snow Day
Feb 10 W No Class Snow Day
12 Feb 12 F Linear Programming: Introduction
[ Class Notes | Readings: CLRS Chaper 29 ]
13 Feb 15 M Linear Programming the Simplex Algorithm
[ Simplex Notes | Readings: CLRS Chaper 29 ]
14 Feb 17 W Max Flow I: Intro
[ Class Notes | Readings: Kozen Chaper 16 ]
15 Feb 19 F Max Flow II: Preflow-Push
[ Class Notes | Kleinberg-Tardos 7.4 ]
Hwk 2 due (Solutions PDF)
16 Feb 22 M Preflow-Push analysis
[ Class Notes ]
Hwk 3 out [PDF]
17 Feb 24 W Graph Algorithms: Depth-first Search
[ Class Notes | Kozen Lecture 4 | CLRS Chapter 22 ]
Feb 26 F No Class CSD Open House
 Open House
18 Mar 01 M Graph Algorithms: Strongly Connected Components
[ Class Notes | Sleator's notes ]
19 Mar 03 W FFT
[ Class Notes | Lec 35 Kz, Chap 30 CLRS ]
Mar 05 F Mid-semester Break
 Spring Break
Mar 07 S Spring Break
 Spring Break
Mar 10 W Have a nice break!
 Spring Break
Mar 12 F Spring Break
 Spring Break
20 Mar 15 M Simple String Matching Algorithms
[ Chap 32 CLRS | Class Notes ]
Hwk 4 out [PDF]
21 Mar 17 W FFT and String Matching with Wildcards
[ Handout1 | Handout2 | Class-Notes ]
Hwk 3 due (Solutions PDF)
22 Mar 19 F Midterm Review
 Practice Midterm (PDF)
Solutions (PDF)
Mar 22 M Midterm
Midterm
23 Mar 24 W Parallel Algorithms: Parallel models, Work and Time, Prefix-sum, List-Ranking
[ Blelloch Chap 1 | Class-Notes ]
24 Mar 26 F Parallel Algorithms: More List-ranking, Parallel Tree Contraction
[ Class-Notes | Chap2 Synthesis of Parallel Algorithms ]
25 Mar 29 M Parallel Algorithms: Parallel Tree Contraction
[ Chap3 Synthesis of Parallel Algorithms | Class-Notes ]
26 Mar 31 W Parallel Algorithms: Maximal Independent Set
[ Kozen Chapters 36 and 37 | Class-Notes ]
Hwk 4 due (Solutions PDF)
Hwk 5 out [PDF]
27 Apr 02 F Resistive Model of a Graph
[ Doyle and Snell | Bollobas Random Walks Chap IX | Class-Notes ]
28 Apr 05 M Random Walks and Electricity
[ Lovasz's Survey | Class-Notes Rayleigh Monotonicity ] Class-Notes Random Walks ]
29 Apr 07 W Solving Linear Systems, Direct Methods
[ Read Chap 28 CLRS | Class-Notes ]
30 Apr 09 F Solving Linear Systems, Direct Methods continued
31 Apr 12 M Mixing Rates of Random Walks and Iterative Solvers
Class-Notes
32 Apr 14 W Planar Graphs: Separator Theorem
[ Lec 14 and 15 Kozen | Class-Notes ]
Hwk 5 due (Solutions PDF)
Hwk 6 out [PDF]
Apr 16 F Spring Carnival
 Spring Carnival
33 Apr 19 M PLanar Separator continued and NP-Completeness I
[ Class-Notes ]
34 Apr 21 W NP-Completeness II
[ Lec 21-25 Kz, Chap 34 CLRS | Class-Notes ]
35 Apr 23 F NP-Completeness III
[ Lec 21-25 Kz, Chap 34 CLRS | Class-Notes ]
36 Apr 26 M Approximation Algorithms I
[ Chap 35 CLRS | Class-Notes ]
37 Apr 28 W Online Algorithms I
[ Class-Notes | Sleator's Notes ]
38 Apr 30 F The Weighted Majority Algorithm, Game Theory, and Lower Bounds for Randomized Algorithms
Class-Notes (Powerpoint)
Last day of classes
Hwk 6 due (Solutions PDF)
May 06 T
Thu. May 6 Final: 8:30a.m.-11:30a.m. DH 1212