CSCI 6220/4030 Randomized Algorithms, Fall 2017
Overview
Randomized Algorithms are the state of the art in contemporary algorithm design. They are usually simple, sometimes even easy to analyze, and they work well in practice. This course provides an introduction to basic concepts in the design and analysis of randomized algorithms.
Course Information
A more detailed version of the syllabus is available as an archival pdf.
Course Text: Randomized Algorithms, by R. Motwani and P. Ragahavan. We will also cover material from other sources (e.g. papers), that will be linked to on this page
Grading Criteria:
- Homeworks, 35%
- In-class Pop Quizzes, 35%
- Final, 30%
Students are expected to have writing supplies on hand in each class to complete the in-class pop quizzes. If you are an athlete or for some other reason are not able to attend each class, make alternative arrangements with the instructor in the first two weeks of the course.
Letter grades will be computed from the semester average. Maximum lower bound cutoffs for A, B, C and D grades are 85%, 75%, 65%, 55% (previously 90%, 80%, 70%, and 60%), respectively. These bounds may be moved lower at the instructors' discretion.
Topics and Schedule
We will be attempt to cover most of the chapters in the text, excluding chapters 2,9,13, but the focus will be on ensuring you understand the material. Accordingly the scope of the material covered may shrink or expand.
- Week 1: Randomized algorithms overview and complexity theory. 1 lecture. Reading: MR95 Chapter 1, except 1.3,1.4
- Week 2: Basic probability theory. 1 lecture. Reading: MR95 Appendices B and C
- Week 3: Markov and Chebyshev inequalities, randomized selection, coupon collector's problem. 2 lectures. Reading: MR95 Chapter 3
- Week 4: Tail inequalities and applications: Chernoff bounds and applications,
Martingales. 2 lectures. Reading: MR95 4.1--4.2,4.4 - Week 5: More Chernoff bounds and applications. 2 lectures. Reading: MR95 4.1--4.2
- Week 6: Oblivious routing on the hypercube, the probabilistic method, Max-SAT, expanding graphs. Reading: MR95 5.1--5.3
- Week 7: Lovasz Local Lemma and applications, the method of conditional probabilities. Reading: MR95 5.5--5.6.
- Week 8: Randomized Data Structures: Treaps and Skip Lists. Reading: MR95: 8.1--8.3.1
- Week 9: Randomized Data Structures: Hashing. Reading: MR95: 8.4--8.5.2
- Week 10: Randomized Data Structure: Hashing, continued.
- Week 11: Fingerprinting, Schwarzt-Zippel, Pattern Matching, and Markov Chains. Reading: MR95: 7.1--7.6, James Aspnes' lecture notes: 9.1--9.3.2
- Week 12: Markov Chains, continued.
- Weeks 13-14: Streaming Algorithms. Reading: Amit Chakrabarti's lecture notes Chapters 0,2,4.
- Week 15: AMS algorithm for distinct items, CountSketch algorithm for frequencies, Kaczmarz algorithm. Reading: Mark Schmidt's lecture notes
- Week 16 (one lecture): finish Kaczmarz, recap, other interesting uses of randomness
Homeworks
All assignments must be typed (preferably in LaTeX) and are due at the start of class (defined as the first 10 minutes). Late assignments will not be accepted, unless you contact the instructor at least two days before the due date to receive a deferral. Deferrals will be granted at the instructor’s discretion, of course.
- HW1: Probability Theory Assigned Thursday September 14, due Thursday September 28. Start early, and ask questions
- HW2: Chernoff Bounds Assigned Thursday September 28, due Thursday October 12.
- HW3: The Probabilistic Method Assigned Thursday October 12, due Thursday October 26.
- HW4: Randomized Data Structures Assigned Thursday October 26, due Thursday November 9.
- HW5: Fingerprinting and Markov Chains Assigned Thursday November 16, due Thursday November 30.
Supplementary Materials
- TBD