Back to CS 473 Fall 2021
Holidays : Academic calendar

Notes: All lecture notes in one file.


Date # Scribbles Notes Slides
Week 1
Tue 8/24 1 Scribbles NP Completeness I
NP Completeness II
NP Completeness III
slides
Thu 8/26 2 Scribbles slides
Week 2
Tue 8/31 3 Scribbles Shopping list of NP complete problems.
Thu 9/2 4 Scribbles A quick review of graph algorithms
See here for lectures/notes on the algorithms surveyed.
Week 3
Monday 9/6 Labor day: Vacation day
Tue 9/7 5 Scribbles Dynamic Programming,
Thu 9/9 6 Scribbles Even MORE Dynamic Programming
Week 4
Tue 9/14 7 scribbles: Linear time algorithms: Lowest point above all lines, Deterministic median selection, Quick select.
Thu 9/16 8 scribbles: Divide & Conquer: Maximum subarray, Bucket sort, Merge sort, Strassen algorithm. (Maybe closet pair.)
Week 5
Tue 9/21 9 scribbles Fast Fourier Transform
Thu 9/23 10 scribbles Sorting Networks
Week 6
Tue 9/28 Midterm 1:
Thu 9/30 11 Scribbles Randomized Algorithms I
Some probability, nuts and bolts, neat analysis of quick sort.
Week 7
Tue 10/5 12 Scribbles QuickSort: high probability
Markov inequality, Max cut 2 approx, Conditional expectation, QuickSort with high probability via conditional expectation.. Mentioned treaps.
Thu 10/7 13 Scribbles Treaps, Chernoff inequality, Galton-Watson process.
Week 8
Tue 10/12 14 scribbles Mincut
Thu 10/14 15 scribbles hashing
Week 9
Tue 10/19 16 scribbles Backward analysis
Thu 10/21 17 Scribbles Approximation algorithms
Week 10
Tue 10/26 18 [Scribbles TBA] Approximation algorithms II
Thu 10/28 19 [Scribbles TBD] Approximation algorithms III TSP, Max SAT Approx subset sum, Max Matching, Bin Packing, Independent set of rectangles.
Week 11
Tue 11/2 20 [Scribbles TBA] Linear programming -- low dimension
Thu 11/4 21 Matchings, Matchings II
Tue 11/9 Midterm 2:
Thu 11/11 22 Network flow I Network flow: II, Network flow III, IV.
Tue 11/16 23 [Scribbles TBA]
More on linear programming
Approximation algorithms via LP.
Thu 11/18 24 scribbles Max cut
11/20-28         Say thanks, go on vacation
Tue 11/30 25 scribbles A bit on Machine Learning,
Thu 12/2 26 slides and more slides. Entropy and Huffman's compression
Tue 12/7 ??? TBD
TBD FINAL

Lecture notes


Streaming
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.
Pre-recorded lectures for CS 374 (previous course)
374 pre-recorded lectures
Academic calendar
Last modified: Fri 2021-10-22 13:55:44 UTC 2021 by Sariel Har-Peled