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 Hwk 0 out [PDF]
2 Jan 14 W Binomial Heaps
3 Jan 16 F Fibonacci Heaps
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
9 Feb 02 M Computational Geometry: Introduction and Sweep Line
10 Feb 04 W Sorting, Convex Hull, and 2D Random Incremental Convex Hull
11 Feb 06 F Linear Programming: 2D Random Incremental 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
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
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 Hwk 3 due (Solutions PDF)
23 Mar 20 F Resistive Model of a Graph
24 Mar 23 M Random Walks and Electricity
25 Mar 25 W Solving Linear Systems, Direct Methods
[ Read Chap 28 CLRS | Class-Notes ]
26 Mar 27 F Linear System Solvers: Iterative Methods
27 Mar 30 M Linear System Solvers: Iterative Methods Part II Hwk 4 due (Solutions PDF)
Hwk 5 out [PDF]
28 Apr 01 W Parallel Algorithms: Parallel models, Work and Time, Prefix-sum, List-Ranking
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
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 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
38 Apr 29 W Randomized Online Algorithms II
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