Lectures Lecturer Topic Reading Homework -------------------------------------------------------------------------------------- 01/11(1) GLM Introduction and Strassen Algorithm handout: PP7-8 Kz 01/13(2) DS Binomial Heaps Lec 8 Kz 01/18 No Class 01/20(3) DS Fibonacci Heaps Lec 9 Kz 01/25(4) DS Splay Trees Lec 12 Kz 01/27(5) DS Treaps Lec 13 Kz HW1 due 02/01(6) GLM Sorting and Convex Hull Chap 1-3 Teng HW2 out 02/03(7) GLM Convex Hull Chap 1-3 Teng 02/08(8) GLM Median and 2D Linear Programming Chap 1-3 Teng 02/10(9) GLM Planar and Plane Graphs Lec 14 Kz 02/15(10) GLM The Planar Separator Theorem Lec 15 Kz HW2 due 02/17(11) GLM Algorithms for Planar graphs 02/22(12) DS Max Flow Lec 16-17 Kz 02/24(13) DS Max Flow Lec 18 Kz 03/01 No Class Spring MidSemester Break 03/03(14) DS Dynamic Programmimg Chap 16 CLR HW3(due) HW4(out) 03/08(15) DS Data Compression 03/10(16) DS Data Compression 03/15(17) GLM Number Theory Algorithms 03/17(18) GLM Number Theory Algorithms HW4 due MID out 03/18 MID due 03/22 Spring Break (No Class) 03/24 Spring Break (No Class) 03/29(19) GLM Number Theory Algorithms 03/31(20) GLM Parallel Algorithms Lec 28 Kz 04/05(21) GLM Parallel List-Ranking Handout:ps-file and Tree Contraction 04/07(22) GLM String matching Sequential & Parallel Handout: Chap 7 JaJa 04/09 HW5 due 04/12(23) GLM Luby's Algorithm and Analysis Lec 36-37 Kz 04/14(24) DS Reductions & NP-Completeness Lec 21-22 Kz HW6 out 04/19(25) DS More on Reductions & NP-Completeness Lec 23-25 Kz Cook's Theorem 04/21(26) DS Counting Problems & #P Lec 25-26 Kz 04/26(27) DS On-Line Algorithms 04/28(28) DS On-Line Algorithms HW6 due 05/04/98 Final Exam: 1-4PM 5409