Algorithms Core

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