This page is still under construction.
For the moment this is the syllabus from Spring 2006. There will be a large overlap this last year. There are more topics to be added, and the number of lectures and order of the topics may change.
| Lec. | Day | DW | Topic | Reading | Homework | Lecturer |
| Jan 15 | M | Martin Luther King Day No Class | GM | |||
| 1 | Jan 17 | W | Introduction and Strassen's Algorithm | Lec 1 Kz | HW 0 out | GM |
| 2 | Jan 19 | F | Binomial Heaps | Lec 5 Kz, Lec 8 Kz, Chap 19 CLRS | GM | |
| 3 | Jan 22 | M | Fibonacci Heaps | Lec 9 Kz, Chap 20 CLRS | GM | |
| 4 | Jan 24 | W | Size of Fibonacci Trees and BST introduction | Lec 12 Kz, Chap 12-14 CLRS | GM | |
| 5 | Jan 26 | F | Treaps (Random Search Trees) | Lec 13 Kz | GM | |
| 6 | Jan 29 | M | Splay Trees | Lec 13 Kz | HW1 out | GM |
| 7 | Jan 31 | W | Splay Trees | HW0 due | GM | |
| 8 | Feb 2 | F | Dynamic Programming: LCS and Picket Fence Painting | Chap 15 CLRS | GM | |
| 9 | Feb 5 | M | Dynamic Programming: Uniquely Decipherable Codes | Handout | GM | |
| 10 | Feb 7 | W | Computational Geometry: Introduction and Sweep Line | Intro Sweep-Line | GM | |
| 11 | Feb 9 | F | Sorting, Convex Hull, and 2D Random Incremental Convex Hull | Handout | HW1 due HW2 out | GM |
| 12 | Feb 12 | M | Linear Programming: 2D Random Incremental | Handout | GM | |
| 13 | Feb 14 | W | More Linear Programming | CLRS Chap 29 | GM | |
| 14 | Feb 16 | F | Max Flow Introduction | Kz 16 | GM | |
| 15 | Feb 19 | M | Max Flow | Kz 17 | HW2 due -- SIAM workshop | DS |
| 16 | Feb 21 | W | Depth First Search | Lec 4 Kz, Chap 22 CLRS | GM | |
| 17 | Feb 23 | F | Review Session | DG | ||
| 18 | Feb 26 | M | Midterm I | |||
| 19 | Feb 28 | W | Strongly Connected Components | Sleator's Notes Baase | HW3 out | GM |
| 20 | Mar 2 | F | FFT | Lec 35 Kz, Chap 30 CLRS | GM | |
| 21 | Mar 5 | M | Simple String Matching Algorithms | Chap 32 CLRS | GM | |
| 22 | Mar 7 | W | FFT and Approximate String Matching | Handout1 Handout2 | HW3 due; HW4 out | GM |
| Mar 9 | F | Mid-Semester Break | ||||
| Mar 12 | M | Spring Break | ||||
| Mar 14 | W | Spring Break | ||||
| Mar 16 | F | Spring Break | ||||
| 23 | Mar 19 | M | Resistive Model of a Graph | Doyle and Snell | GM | |
| 24 | Mar 21 | W | Random Walks | HW4 due | GM | |
| 25 | Mar 23 | F | No Class: CSD Open House | |||
| 26 | Mar 26 | M | Solving Linear Systems | Chap 28 CLRS | GM | |
| 27 | Mar 28 | W | Iterative Methods for Solving Linear Systems | HW5 out | GM | |
| 28 | Mar 30 | F | Parallel Algorithms | Chap2 Synthesis of Parallel Algorithms | GM | |
| 29 | Apr 2 | M | Parallel Algorithms | GM | ||
| 30 | Apr 4 | W | Parallel Algorithms | GM | ||
| 31 | Apr 6 | F | Multiplicative Weight Update Algorithms | Avrim Blum's Notes and this Survey Paper | HW5 due | DG |
| 32 | Apr 9 | M | Parallel Maximal Independent Set; Midterm Review W5409 8PM | Lecs 36 and 37 Kz | GM | |
| 33 | Apr 11 | W | Midterm II | CESC Conference | ||
| 34 | Apr 13 | F | Planar Graph Separators | Lec 15 Kz related paper | GM | |
| 35 | Apr 16 | M | Representing Planar Graphs | Lec 14 Kz Todd's Talk | GM | |
| 36 | Apr 18 | W | Competitive Algorithms | Sleators Notes | HW6 out | GM |
| Apr 20 | F | Spring Carnival | ||||
| 37 | Apr 23 | M | Review Midterm 2 | DG and DS | ||
| 38 | Apr 25 | W | Competitive Algorithms | Sleators Notes; Part 2 | GM | |
| 39 | Apr 27 | F | NP-Completeness | Lec 21-25 Kz, Chap 34 CLRS | HW6 due | GM |
| 40 | Apr 30 | M | NP-Completeness | GM | ||
| 41 | May 2 | W | NP-Completeness | GM | ||
| 42 | May 4 | F | Approximation Algorithms | CRLS Chap 35 | GM | |
| May 9 | W | Final Review 1:30-3 PM Wean 5409 | DG GM DS | |||
| May 10 | Th | Final 1-4PM SH 125 | ||||