CS255Spring 2015Lecture Notes
Design and Analysis of Algorithms
Videos of lectures are available.
Below are my lecture notes for the class so far.
They should serve as a rough guide to what was covered on any given day.
Frequently, however, I say more in class than is in these notes.
Also, I tend to dynamically correct typos on the board
that might appear in these lecture notes. So caveat emptor.
Week 1: [Jan 26 -- Probabilistic Analysis and Randomized Algorithms]
[Jan 28 -- Analyzing the Hiring Problem, Generating Random Permutations]
Week 2: [Feb 2 -- Random Permutations, the Birthday Problem, Ball and Bins Arguments]
[Feb 4 -- Streaks, Online Hiring Problem, Start Threads]
Week 3: [Feb 9 -- Multithreaded algorithms] [Feb 11 -- More Multithreaded algorithms]
Week 4: [Feb 16 -- Finish Multithreaded algorithms] [Feb 18 -- Spawn Sync Java, JOCL, PRAMs]
Week 5: [Feb 23 -- PRAM Sorting] [Feb 25 -- PRAM Maximal Independent Set]
Week 6: [Mar 2 -- Distributed Algorithms] [Mar 4 -- Byzantine Agreement]
Week 7: [Mar 9 -- Map Reduce and PRAMs] [Mar 11 -- Finish Map Reduce and PRAMs, Online Algorithms]
Week 8: [Mar 16 -- Practice Midterm Day] [Mar 18 -- Midterm]
Week 9: [Mar 23 -- Spring Break] [Mar 25 -- Spring Break]
Week 10: [Mar 30 -- Finish Online Algorithms, Number Theoretic Algorithms] [Apr 1 -- GCDs, Euclid's Algorithm, Groups]
Week 11: [Apr 6 - Modular Arithmetic] [Apr 8 - Chinese Remaindering, Square Roots]
Week 12: [Apr 13 - RSA, Primality Checking] [Apr 15 - Finish Primality Checking; Start NP-completeness]
Week 13: [Apr 20 - Reductions, Circuit-SAT, SAT, 3SAT] [Apr 22 - NP-completeness of Clique, Vertex Cover, Hamiltonian Cycle, TSP]
Week 14: [Apr 27 - Subset-sum, Approximation Algorithms] [Apr 29 - Inapproximability of TSP, Approximibility of Set Cover, Randomized Approximation]
Week 15: [May 4 - Randomized Approximation And Other Techniques] [May 6 - Fully p-time Approximation of Subset Sum]
Week 16: [May 11 - The Probabilistic Method] |