# CS 761 - Randomzied Algorithms - Fall 2019

## Course Description

Randomness is a very powerful technique in algorithm design.
We will discuss tools and methods for harnessing the power of randomization in the design and analysis of algorithms and stochastic processes.
Prerequisites include basic knowledge of probability, and mathematical maturity.
## Logistics

- Lecture: Fridays, 10:00 AM - 12:50 PM, DC 2585
- Instructor: Gautam Kamath
- Office Hours: Fridays, 12:50 PM - 2:00 PM, DC 3124

## Lecture Schedule

Schedule subject to change.
- Lecture 1 (September 6): Probability basics, randomized Quicksort, Markov's Inequality, Coupon Collectors (scribe notes, preliminary)
- Lecture 2 (September 13): Chebyshev's Inequality, Chernoff Bound, Minimum Cut, Minimum Spanning Tree
- Lecture 3 (September 20): TBD
- Lecture 4 (September 27): TBD
- Lecture 5 (October 4): TBD
- Lecture 6 (October 11): TBD
- Lecture 7 (October 25): TBD
- Lecture 8 (November 1): TBD
- Lecture 9 (November 8): TBD
- Lecture 10 (November 15): TBD
- Lecture 11 (November 22): TBD
- Lecture 12 (November 29): TBD

Some topics which will hopefully be fit into the above schedule somewhere:
- Graph Algorithms
- Balls and bins, Hashing
- Streaming/Sketching/Dimension Reduction
- Probabilistic Methods
- Distribution Testing
- Linear Algebra
- Derandomization

## Books and References

No textbook is required for this course, though we will generally cover various topics from the book below by Motwani and Raghavan.
The following books are classic references in this area.
- "Randomized Algorithms," by Rajeev Motwani and Prabhakar Raghavan.
- "Probability and Computing: Randomized Algorithms and Probabilistic Analysis," by Michael Mitzenmacher and Eli Upfal.
- "The Probabilistic Method," by Noga Alon and Joel Spencer.

## Grading

There will scribe notes (10%), 3 homework assignments (55%), and a final project (35%).

For scribe notes, please use the LaTeX template here.