Lecture Plan

Lecture date Topic  Slides (if not Kevin Wayne's)

1/7

 Introduction  
1/9 Stable Matching (Ch1)  
1/11 Stable Matching (Ch1), Representative problems (Ch 1), Asymptotic notation (Ch2)  
1/14 Start Divide and Conquer algorithms intro, induction, Mergesort(Ch5) 05DivAndConq
1/16 Divide and Conquer Algs, Inversions, closest pair of points(Ch 5)  
1/18 Divide and Conquer Algs, integer and matrix multiplication (Ch 5)  
1/21 Holiday - no lecture  
1/23  D&C: selection, start Greedy Algs (Ch 4)

linear select

handout from Dasgupta, Papadimitriou, and Vazirani book
1/25  Greedy algorithms - interval scheduling and breakpoints greedy1

1/28

  Greedy algs  
1/30  Greedy algs / start Dijkstra's alg  
2/1  Dijkstra's alg, maybe start MST Dijkstra slides
2/4  MST algs, start FFT for polynomials

MST slides,   FFT slides

FFT handout 1 and Handout 2 from Das Gupta, Papadimitriou, Vazirani book
2/6  FFT for polynomials  
2/8  FFT continues  
2/11  Review Divide and conquer  
2/13  Review Greedy  
2/15 Midterm exam  
2/18 Holiday - no lecture  
2/20  Start Dynamic programming  Chapter 6  (6.1) using Kevin Wayne slides
2/22  Weighted interval scheduling  6.2
2/25  Segmented least squares  6.3
2/27  SEgmented least squares/Knapsack  6.4
3/1  Knapsack  6.4
3/4  RNA secondary structure  6.5
3/6  Sequence alignment  6.6
3/8  Bellman-Ford-More  6.8
3/11  Network Flow  Chapter 7 slides
3/13    
3/15    
3/18 Final exam: 7:30-10:30 pm in lecture room  

 Slides: I will be using slides from Kevin Wayne that can be found at: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/.   I will not be using all the chapters (see syllabus) and will be skipping some of the slides for the chapters I will cover.