This page is still under construction.
For the moment this is the syllabus from Spring 2007. 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 | ||
| 1 | Jan 14 | M | Introduction and Strassen's Algorithm | Lec 1 Kz | HW0 out | GM | ||
| 2 | Jan 16 | W | Binomial Heaps | Lec 5 Kz, Lec 8 Kz, Chap 19 CLRS | GM | |||
| 3 | Jan 18 | F | Fibonacci Heaps | Lec 9 Kz, Chap 20 CLRS | GM | |||
| Jan 21 | M | Martin Luther King Day No Class | ||||||
| 4 | Jan 23 | W | Size of Fibonacci Trees and BST introduction | Chap 12-14 CLRS | GM | |||
| 5 | Jan 25 | F | Splay Trees | Lec 12 Kz | HW0 due HW1 out | GM | ||
| 6 | Jan 28 | M | Splay Trees | GM | ||||
| 7 | Jan 30 | W | Treaps (Random Search Trees) | Lec 13 Kz | GM | |||
| 8 | Feb 1 | F | Dynamic Programming: LCS and Picket Fence Painting | Chap 15 CLRS | GM | |||
| 9 | Feb 4 | M | Dynamic Programming: Uniquely Decipherable Codes | Handout | GM | |||
| Feb 6 | W | No Class | ||||||
| 10 | Feb 8 | F | Computational Geometry: Introduction and Sweep Line | Intro Sweep-Line | HW1 due HW2 out | GM | ||
| 11 | Feb 11 | M | Sorting, Convex Hull, and 2D Random Incremental Convex Hull | Handout | GM | |||
| 12 | Feb 13 | W | Linear Programming: 2D Random Incremental | Handout | GM | |||
| 13 | Feb 15 | F | Analysis of 2D Random Incremental Algorithm for LP | GM | ||||
| 14 | Feb 18 | M | More Linear Programming | CLRS Chap 29, presentation, notes on LP | AKS | |||
| 15 | Feb 20 | W | Max Flow Introduction | Kz 16 | GM | |||
| 16 | Feb 22 | F | Max Flow | Lec 17 Kz | HW2 due | GM | ||
| 17 | Feb 25 | M | Review Session | YW | ||||
| 18 | Feb 27 | W | Midterm I | HW3 out | ||||
| 19 | Feb 29 | F | DFS Intro | Class-Notes | GM | |||
| 20 | Mar 3 | M | Strongly Connected Components | Class-Notes Sleator's Notes Baase | GM | |||
| 21 | Mar 5 | F | FFT | Class-Notes Lec 35 Kz, Chap 30 CLRS | GM | |||
| Mar 7 | F | Spring Break | ||||||
| Mar 10 | M | Spring Break | ||||||
| Mar 12 | W | Spring Break | ||||||
| Mar 14 | F | Spring Break | ||||||
| 22 | Mar 17 | M | Simple String Matching Algorithms | Chap 32 CLRS Class-Notes | HW3 due; HW4 out | GM | ||
| 23 | Mar 19 | W | FFT and Approximate String Matching | Handout1 Handout2 Class-Notes | GM | |||
| 24 | Mar 21 | F | Resistive Model of a Graph | Class-Notes Doyle and Snell | GM | |||
| 25 | Mar 24 | M | Random Walks and Electricity | Class-Notes | GM | |||
| 26 | Mar 26 | W | Solving Linear Systems, Direct Methods | Chap 28 CLRS Class-Notes | GM | |||
| 27 | Mar 28 | F | No Class: CSD Open House | GM | ||||
| 28 | Mar 31 | M | Linear System Solvers: Iterative | Class-Notes | GM | |||
| 29 | Apr 2 | W | Parallel Algorithms: Parallel models, Work and time, Prefix-sum, List-Ranking | Class-Notes Chap1 from Synthesis of Parallel Algorithms | HW4 due; HW5 out | GM | ||
| 30 | Apr 4 | F | Parallel Algorithms: More List-ranking, Parallel Tree Contraction | Class-Notes Chap2 SPA | GM | |||
| 31 | Apr 7 | M | Parallel Maximal Independent Set | Class-Notes Lec 36 and 37 Kz | GM | |||
| 32 | Apr 9 | W | Parallel Maximal Independent Set | GM | ||||
| Apr 10 | Th | Midterm Review W5409 8PM Wean 5409 | AS YW | |||||
| 33 | Apr 11 | F | Midterm II | CSD Retreat | ||||
| 34 | Apr 14 | M | Planar Graph Separators | Class-Notes Lec 15 Kz related paper | GM | |||
| 35 | Apr 16 | W | Representing Planar Graphs | Class-Notes Lec 14 Kz; Todd's Talk | HW5 due; HW6 out | GM | ||
| Apr 18 | F | Spring Carnival | ||||||
| 36 | Apr 21 | M | Planar Graph Separators; NP-Completeness | Class-Notes Lec 21-25 Kz, Chap 34 CLRS | GM | |||
| 37 | Apr 23 | W | NP-Completeness | Class-Notes | GM | |||
| 38 | Apr 25 | F | NP-Completeness | Class-Notes | GM | |||
| 39 | Apr 28 | M | Competitive Algorithms | Class-Notes Sleator's Notes | ARVO Conference | AS | ||
| 40 | April 30 | W | Competitive Algorithms | Class-Notes Sleator's Notes; Part 2 | GM | |||
| 41 | May 2 | F | Last class: Approximation Algorithms | Class-Notes | HW6 due | GM | ||
| May 6 | Tues | Final Review at 8PM | Location: Wean 5409 | AS YW GM | ||||
| May 8 | Th | Final 08:30am-11:30am | Location: Hamerschlag Hall B103 | |||||