Class activities

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