Lectures Topic Reading Homework
------------------------------------------------------------------------------
01/12(1) Strassen Algorithm handout PP7-8 Kz
01/14(2) Sorting and Convex Hull Chap 1-3 Teng
01/19(3) Convex Hull Chap 1-3 Teng
01/21(4) Median and 2D Linear Programming Chap 1-3 Teng
01/26(5) Splay Trees Lec 12 Kz
01/28(6) Treaps Lec 13 Kz
02/02(7) Binomial Heaps Lec 8 Kz HW1 due
02/04(8) Fibonacci Heaps Lec 9 Kz
02/09(9) Union-Find Lec 10 Kz
02/11(10) Analysis of Union-Find Lec 11 Kz
02/16(11) Dynamic Programmimg Chap 16 CLR
02/18(12) Huffman Codes Handout HW2 due
02/23(13) Shortest Paths Chap 25-26 CLR
02/25(14) Planar and Plane Graphs Lec 14 Kz
03/02 Midterm Break(No Class)
03/04(15) The Planar Separator Theorem Lec 15 Kz HW3 due
03/09(16) Max Flow Lec 16-17 Kz HW4 out
03/11(17) Max Flow Lec 18 Kz
03/16(18) Matching Lec 19-20 Kz Take-home Midterm
03/18(19) Review of Midterm exam
03/20 HW4 due
03/23 Spring Break (No Class)
03/25 Spring Break (No Class)
03/30(20) Parallel Algorithms Lec 28 Kz
04/01(21) Parallel List-Ranking Handout: HW5 out
and Tree Contraction ps-file
04/06(22) String matching Sequential & Parallel Handout: Chap 7 JaJa
04/08(23) Luby's Algorithm and Analysis Lec 36-37 Kz
04/10 HW5 due
04/13(24) FFT Lec 35 Kz C-32 CLR HW6 out
04/15(25) Primality Lec 36 Kz
04/20(26) Reductions & NP-Completeness Lec 21-22 Kz Baird
04/22(27) More on Reductions & NP-Completeness Lec 23-25 Kz Baird
Cook's Theorem
04/27(28) Counting Problems & #P Lec 25-26 Kz HW6 due
04/29(29) TBA
05/04/98 Final Exam 1-4PM
Multi-level algorithms LP & Duality Approximation Algorithms