CS255 Spring 2022 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 26 -- Probabilistic Analysis and Randomized Algorithms]

Week 2: [Jan 31 -- Analyzing the Hiring Problem, Generating Random Permutations] [Feb 2 -- Random Permutations, the Birthday Problem, Ball and Bins Arguments]

Week 3: [Feb 7 -- Ball and Bins Arguments][Feb 9 -- Finish Streaks, Online Hiring Problem, Multithreaded Algorithms]

Week 4: [Feb 14 -- More Multithreaded Algorithms] [Feb 16 -- Race Conditions, Chess, Matrix Multiplication]

Week 5: [Feb 21 -- Matrices, Spawn Sync Java, JOCL] [Feb 23 -- PRAMs]

Week 6: [Feb 28 -- PRAM Sorting and Maximal Independent Set] [Mar 2 -- Parallel MIS]

Week 7: [Mar 7 -- Finish Parallel MIS, Distributed Algorithms, CCP] [Mar 9 -- Asynchronous CPP, Byzantine Agreement]

Week 8: [Mar 14 - Practice Midterm] [Mar 16 - Midterm]

Week 9: [Mar 21 - Map Reduce] [Mar 23 - Finish Map Reduce and PRAMs, Online Algorithms]

Week 10: [Mar 28 - Spring Break] [Mar 30 - Spring Break]

Week 11: [Apr 4 - Online Algorithms] [Apr 6 - Number Theoretic Algorithms, GCDs, Euclid's Algorithm, Groups]

Week 12: [Apr 11 - Modular Arithmetic] [Apr 13 - Chinese Remaindering, Discrete Log, RSA]

Week 13: [Apr 18 - Primality Checking] [Apr 20 - NP, NP-Completeness, Reductions]

Week 14: [Apr 25 - NP-completeness, CIRCUIT-SAT] [Apr 27 - Various NPC Problems]

Week 15: [May 2 - HAM-CYCLE, TSP and SUBSET-SUM are NPC, Approximation Algorithms][May 4 - Approximation Algorithms]

Week 16: [May 9 - Set Cover Approximation, Randomized Approximation Algorithms] [May 11 - Subset Sum Approximation]