Courses
  /  
Descriptions
EECS 396, 496: Randomized Algorithms

Quarter Offered

Spring : 10-12:50 M ; De

Prerequisites

Course is by instructor permission only. Students must email anindya.de1@northwestern.edu to obtain permission #

Description

The power of randomness is one of the most enduring mysteries of computation. In the last 30+ years, several algorithms have been designed which crucially use randomness and beat their deterministic counterparts in terms of efficiency, simplicity and nearly every other computational resource (with the obvious exception of "randomness"). In this course, we start with simple examples such as pattern matching, primality and go on to explore topics such as the power of Markov chains, hashing of high dimensional data and Martingales.

GENERAL GUIDELINES: Students must have taken either EECS 336 or have strong math background such as 300 level math courses. The knowledge of probability and mathematical maturity is an absolute must.

A ROUGH OUTLINE OF TOPICS IS:

  1. Introduction  and  elementary examples
  2. Linearity of expectation, Markov's inequality, and the probabilistic method
  3. Variance, Chebyshev's inequality, and threshold phenomena in graphs
  4. Chernoff bounds, Low-congestion routing, randomized rounding
  5. Geometric concentration, random projections, dimension reduction
  6. More geometry: High-dimensional search and compressed sensing
  7. The Lovasz Local Lemma
  8. Power of Markov chain Monte Carlo methods.

COURSE INSTRUCTOR: Prof. Anindya De