This page is still under construction. 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 16 | M | Martin Luther King Day No Class | GM | |||

1 | Jan 18 | W | Introduction and Strassen's Algorithm | Lec 7 Kz | HW 0 out | GM |

2 | Jan 20 | F | Binomial Heaps | Lec 8 Kz, Chap 19 CLRS | GM | |

3 | Jan 23 | M | Fibonacci Heaps | Lec 9 Kz, Chap 20 CLRS | GM | |

4 | Jan 25 | W | Size of Fibonacci Trees and BST introduction | Lec 12 Kz, Chap 12-14 CLRS | GM | |

5 | Jan 27 | F | Treaps (Random Search Trees) | Lec 13 Kz | HW0 due HW1 out | GM |

6 | Jan 30 | M | Splay Trees | Lec 13 Kz | JD | |

7 | Feb 1 | W | Dynamic Programming Optimal BST and Picket Fence Painting | Chap 15 CLRS | GM | |

8 | Feb 3 | F | Computational Geometry: Introduction and Sweep Line | Handout | GM | |

9 | Feb 6 | M | Sweepline, Sorting and Convex Hull | Handout | HW1 due | GM |

10 | Feb 8 | W | 2D Random Incremental Convex Hull | HW2 out | GM | |

11 | Feb 10 | F | Linear Programming: 2D Random Incremental | Handout | GM | |

12 | Feb 13 | M | More Linear Programming | GM | ||

13 | Feb 15 | W | Max Flow | GM | ||

14 | Feb 17 | F | Max Flow | HW2 due | GM | |

15 | Feb 20 | M | Representing Planar Graphs | Lec 14 Kz Todd's Talk | GM | |

16 | Feb 22 | W | Planar Graph Separators | Lec 15 Kz related paper | GM | |

17 | Feb 24 | F | Review Session | JD | ||

18 | Feb 27 | M | Midterm I | |||

19 | Mar 1 | W | Planar Separator Continued | GM | ||

20 | Mar 3 | F | FFT | Lec 35 Kz, Chap 30 CLRS | HW3 out | GM |

21 | Mar 6 | M | Simple String Matching Algorithms | Chap 32 CLRS | GM | |

22 | Mar 8 | W | FFT and Approximate String Matching | Handout1 Handout2 | GM | |

Mar 10 | F | Mid-Semester Break | ||||

Mar 13 | M | Spring Break | ||||

Mar 15 | W | Spring Break | ||||

Mar 17 | F | Spring Break | ||||

23 | Mar 20 | M | Union-Find | Lec 10 Kz, Chap 21 CLRS | HW3 due | GM |

24 | Mar 22 | W | Analysis of Union-Find | Lec 11 Kz, Chap 21 CLRS | GM | |

25 | Mar 24 | F | No Class: CSD Open House | HW4 out | ||

26 | Mar 27 | M | Depth First Search | Lec 4 Kz, Chap 22 CLRS | GM | |

27 | Mar 29 | W | Strongly Connected Components | Sleator's Notes Baase | GM | |

28 | Mar 31 | F | Parallel Algorithms | Chap2 Synthesis of Parallel Algorithms | GM | |

29 | Apr 3 | M | Parallel Algorithms | GM | ||

30 | Apr 5 | W | Parallel Algorithms | HW4 due | GM | |

31 | Apr 7 | F | Parallel Maximal Independent Set | Lecs 36 and 37 Kz | GM | |

32 | Apr 10 | M | Competitive Algorithms; Midterm Review W5409 8PM | Sleators Notes | HW5 out | GM |

33 | Apr 12 | W | Midterm II | |||

34 | Apr 14 | F | Competitive Algorithms | Sleators Notes; Part 2 | GM | |

35 | Apr 17 | M | Competitive Algorithms | GM | ||

36 | Apr 19 | W | No Class CS50 | GM | ||

Apr 21 | F | Spring Carnival | ||||

37 | Apr 24 | M | NP-Completeness | Lec 21-25 Kz, Chap 34 CLRS | GM | |

38 | Apr 26 | W | NP-Completeness | HW5 due | GM | |

39 | Apr 28 | F | NP-Completeness | HW6 out | GM | |

40 | May 1 | M | Approximation Algorithms | GM | ||

41 | May 3 | W | Approximation Algorithms | GM | ||

42 | May 5 | F | Approximation Algorithms | HW6 due | GM | |

May 11 | Th | Final 8:30-11:30AM Wean 7500 |