Information about lectures, labs, assignments, and reading.
Week 1 : Aug. 21 | |
Lectures | Introduction and Course Info; asymptotic analysis; recurrences; divide-and-conquer |
Reading | CLRS Ch. 1-4 |
Recitations | CS320 review |
Week 2 : Aug. 28 | |
Lectures | Strassen's algorithm; iterative expansion; master theorem; integer multiplications; telescoping series |
Reading | CLRS Ch. 1-4 and KT Ch. 5 |
Recitations | Master theorem |
Assignments | Homework 1: Recurrences; asymptotics |
Week 3 : Sep. 4 | |
Lectures | Convolutions; FFT; polynomial multiplication |
Reading | CLRS Ch. 30 and KT Ch. 5 |
Recitations | FFT |
Assignments | Homework 2: Master theorem |
Week 4 : Sep. 11 | |
Lectures | FFT; reachability in graphs; single-source shortest paths |
Reading | CLRS Chs. 30 and 24 and KT Ch. 6 |
Recitations | SSSP |
Assignments | Homework 3: FFT |
Week 5 : Sep. 18 | |
Lectures | All pairs shortest paths |
Reading | CLRS Ch. 25 |
Recitations | APSP |
Assignments | Homework 4: SSSP |
Week 6 : Sep. 25 | |
Lectures | Fast marching; sequence alignment |
Reading | KT Ch. 6 and global and local alignment slides and Sethian's paper |
Recitations | Tropical (MAX-PLUS) Algebra |
Assignments | Homework 5: APSP |
Week 7 : Oct. 2 | |
Lectures | RNA folding; randomized algorithms |
Reading | CLRS Ch. 5 and KT Ch. 6 |
Recitations | Randomized algorithms |
Week 8 : Oct. 9 | |
Lectures | Randomized algorithms |
Reading | CLRS Chs. 5 and 7 |
Recitations | Randomized algorithms |
Exams | Midterm |
Week 9 : Oct. 16 | |
Lectures | Randomized algorithms; linear-time selection; MAX 3-SAT |
Reading | CLRS Ch. 9 and KT Sections 13.3-13.5 |
Recitations | Linear-time selection |
Assignments | Homework 6: Randomized algorithms |
Week 10 : Oct. 23 | |
Lectures | Amortized analysis |
Reading | CLRS Ch. 17 |
Recitations | Amortized analysis |
Assignments | Homework 7: Order statistics |
Week 11 : Oct. 30 | |
Lectures | Maximum flows and min cuts |
Reading | CLRS Ch. 26 |
Recitations | Maximum flow |
Assignments | Homework 8: Amortized analysis |
Week 12 : Nov. 6 | |
Lectures | Fibonacci heaps |
Reading | CLRS Ch. 19 |
Recitations | Fibonacci heaps |
Assignments | Homework 9: Max flows |
Week 13 : Nov. 13 | |
Lectures | String matching |
Reading | CLRS Ch. 32 |
Recitations | String matching |
Week 14 : Spring break | |
Week 15 : Nov. 27 | |
Lectures | Computational geometry |
Reading | CLRS Ch. 33 |
Recitations | Computational geometry |
Assignments | Homework 10: Fibonacci heaps |
Week 16 : Dec. 4 | |
Lectures | Approximation algorithms |
Reading | CLRS Ch. 35 |
Recitations | Approximation algorithms |