# CSCI 6220/4030 Randomized Algorithms, Fall 2018

## 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 Logistics

A more detailed version of the syllabus is available as an archival pdf.

**Instructor**: Alex Gittens (`gittea` at `rpi` dot `edu`)

**Lectures**: MTh 10am-11:50am; Darrin 239

**Office Hours**: MTh 12pm-1pm, or by appointment; Lally 316

** Course Text**: (Recommended, not required) Probability and Computing, by M. Mitzenmacher and E. Upfal.

** Grading Criteria**:

- Homeworks, 50%
- In-class Pop Quizzes, 25%
- Project, 25%

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. Lower-bound cutoffs for A, B, C and D grades are 90%, 80%, 70%, and 60%, respectively. These bounds may be moved lower at the instructors discretion.

## Topics

We will largely follow Mitzenmacher and Upfal, replacing the more ML-focused content with alternative material.

- Events and Probabilities
- Discrete Random Variables
- Moments and Deviations
- Chernoff and Hoeffding Bounds
- Balls, Bins, and Graphs
- Randomized Data Structures: Treaps, Skip Lists, Hash Tables, Bloom Filters
- The Probabilistic Method
- Markov Chains and Random Walks
- Continuous Distributions and Poisson Processes
- Normal Distribution and Dimensionality Reduction
- Monte Carlo Method
- Coupling
- Martingales
- Streaming Algorithms

## Lecture Schedule

- Lecture 1: Course logistics, Randomized Algorithms, Las Vegas and Monte Carlo algorithms, 8 standard uses for randomness, Probability spaces
- Lecture 2: Probability spaces (recap), Axioms of probability, Nontriviality of sigma-algebras for continuous state spaces, Indicator random variables, Bernoulli and Binomial distributions
- Lecture 3: Random variables (cont'd), CDFs, PDFs, Sampling from random variables, Conditional probabilities, Law of total probability, Karger's Mincut algorithm
- Lecture 4: More efficient Karger's algorithm (recursive), Random vectors and joint distributions, Multivariate Gaussians, Marginal distributions, Conditional distributions
- Lecture 5: Reservoir Sampling, Independent random variables, Expectation and its properties, Geometric random variables, Coupon collector problem

## 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 Monday September 10, due Thursday September 20.
*Start early, and ask questions about both the content and your write-ups.*

## Supplementary Materials

- TBD