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 |