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