Back to CS 473 Fall 2018

Notes: All lecture notes in one file.


Date # Slides Notes
Week 1
Tue 8/28 1 Scribbles NP Completeness I
NP Completeness II
NP Completeness III
Thu 8/30 2 Scribbles (transcript)
Discussion 1 notes.
Week 2
Tue 9/4 3 Scribbles Dynamic Programming
Thu 9/6 4 Scribbles Even MORE Dynamic Programming
Discussion 2 notes.
Week 3
Tue 9/11 5 Scribbles Deterministic median selection
Quick select
Lowest point above all lines
Thu 9/13 6 slides Fast Fourier Transform
Disc. 3: More dyanmic programming
Week 4
Disc. 4: FFT
Tue 9/18 7 slides Sorting Networks
Thu 9/20 8 scribbles: Covered in class: Probability, Chernoff's inequality, quicksort with high probability.
Randomized Algorithms I
QuickSort: high probabiliyt
Week 5
Disc. 5: some randomized algorithms
Tue 9/25 9 scribbles hashing
Thu 9/27 10 scribbles Backward analysis
Week 6
Tue 10/2 Midterm 1: 7pm-9pm, DCL 1320
Thu 10/4 11 Scribbles Mincut
Week 7
Tue 10/9 12 Scribbles Streaming
Thu 10/11 13 Scribbles Approximation algorithms
Approximation algorithms II
Approximation algorithms III
Week 8
Tue 10/16 14 scribbles TSP, Max SAT
Thu 10/18 15 slides Approx subset sum, Max Matching, Bin Packing, Independent set of rectangles.
Week 9
Tue 10/23 16 Scribbles Matchings
Thu 10/25 17 Scribbles Matchings II
Week 10
Tue 10/30 18 Scribbles Network flow I
Thu 11/1 19 Scribbles Network flow: II, III, IV.
Week 11
Tue 11/6 20 Scribbles Linear programming -- low dimension
Thu 11/8 21 slides and more slides
Tue 11/13 Midterm 2: 7-9pm, DCL 1310
Thu 11/15 22 More on linear programming slides and more slides.
Scribbled ver: a and b.
11/17-26         Say thanks, go on vacation
Tue 11/27 23 Scribbles Approximation algorithms via LP.
Thu 11/29 24 scribbles Max cut
Tue 12/4 25 scribbles A bit on Machine Learning,
Thu 12/6 26 slides and more slides. Entropy and Huffman's compression
Tue 12/11 FINAL In class final (during regular lecture time).

Lecture notes


Union find
Linear programming
LP II
LP III
Lower bounds



Entropy II: Extracting randomness
Entropy III
Shannon's theorem

Mincost flow
Mincost flow II

Rand Alg III - Min Cut

Old schedule.
Academic calendar
Last modified: Thu 2018-12-06 22:52:02 UTC 2018 by Sariel Har-Peled