CS255 Spring 2019 Lecture 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 28 -- Probabilistic Analysis and Randomized Algorithms] [Jan 30 -- Analyzing the Hiring Problem, Generating Random Permutations]

Week 2: [Feb 4 -- Random Permutations, the Birthday Problem, Ball and Bins Arguments] [Feb 6 -- Streaks, Online Hiring Problem, Start Threads]

Week 3: [Feb 11 -- Multithreaded Algorithms] [Feb 13 -- MoreMultithreaded Algorithms]

Week 4: [Feb 18 -- Race Conditions, Chess, Matrix Multiplication] [Feb 20 -- Spawn Sync Java, JOCL, PRAMs]

Week 5: [Feb 25 -- PRAMs and PRAM Sorting] [Feb 27 -- PRAM Sorting and Maximal Independent Set]

Week 6: [Mar 4 -- Parallel MIS - Distributed Algorithms] [Mar 6 -- Asynchronous CPP - Byzantine Agreement]

Week 7: [Mar 11 -- Byzantine Agreement - Map Reduce] [Mar 13 -- Finish Map Reduce and PRAMs, Online Algorithms]

Week 8: [Mar 18 -- Finish Online Algorithms] [Mar 20 -- Number Theoretic Algorithms, GCDs, Euclid's Algorithm, Groups]

Week 9: [Mar 25 -- Practice Midterm] [Mar 27 -- Midterm]

Week 10: [Apr 8 -- Modular Arithmetic] [Apr 10 -- Modular Equations, Chinese Remaindering, Discrete Log, RSA]

Week 11: [Apr 15 -- RSA - Primality Checking] [Apr 17 -- NP]

Week 12: [Apr 22 -- NP-completeness of CIRCUIT-SAT, SAT, k-SAT] [Apr 24 -- Various NPC Problems]

Week 13: [Apr 29 -- TSP and SUBSET-SUM are NPC, Approximation Algorithms] [May 1 -- Approximation Algorithms]

Week 14: [May 6 -- Randomized and LP based Approximation Algorithms] [May 8 -- Subset Sum Approximation - The Probabilistic Method]