495: Randomized Algorithms

Contents: Description Details Announcements Syllabus Links

Description

 This course covers basic techniques in the design and analysis of randomized algorithms and algorithms for random inputs. Techniques will be presented along side algorithmic applications. The course will conclude with a survey of areas in which randomization plays a key role. The course assumes students have a good understanding of basic probability and algorithm design.

Details

 Lectures: MW 2.05-3.20pm, Tech LG68

Professor: Nicole Immorlica
Email: nickle at eecs dot northwestern dot edu
Office Hours: by appointment, Ford 3.327

Announcements
  • The first part of the course will cover classic topics from the text. The second half will survey applications including online algorithms, streaming algorithms, multi-armed bandits, graph embeddings, auction design, and/or information theory, depending on the interests of the class.

  • Students are expected to attend all lectures, complete two problem sets, and hand in a final project. While students are encouraged to do original research for the final project, survey-based projects are also acceptable. There will be no exams.

    Syllabus

     Note: The course is based on the text Randomized Algorithms, by Motwani and Raghavan. Supplementary reading material may be provided throughout the year.

    Tail Bounds -- Markov, Chebyshev
    Date Topic Applications Assignment
    04/01/10 Introduction Quicksort Read Chapter 1

    Karp, An introduction to randomized algorithms, Discrete Applied Mathematics 34 (1991), 165-201.
    06/01/10 Background Tour Vertex Cover, Matching  
    11/01/10 Pivots for Approximation Algs Min Feedback Arc Set in Tournaments Ailon, Charikar, and Newman, Aggregating Inconsistent Information: Ranking and Clustering, STOC 2005.
    13/01/10 Monte Carlo, Boosting, Saving Computation Global Min-Cut Read Chapter 1 and Chapter 10
    18/01/10 NO CLASS - MLK DAY    
    20/01/10 Lower Bounds for Randomized Algorithms Game Tree Evaluation Read Chapter 2

    Complete Problem Set 1 (due Feb. 1st)
    25/01/10 Randomized Selection Read Chapter 3
    27/01/10 Tail Bounds -- Chernoff Routing in Hypercubes, Power of Two Choices Load Balancing Read Chapter 4

    Azar, Broder, Karlin, and Upfal, Balanced Allocations, SIAM J. on Computing 29 (1999), 180-200.
    01/02/10 PROBLEM SET 1 PRESENTATIONS   problem 1, problem 2, problem 3, problem 4
    03/02/10 Hashing Chaining, Linear Probing Mihai's wonderful blog posts here and here.

    Pagh, Pagh, and Ruzic, Linear Probing with Constant Independence, STOC 2007.
    08/02/10 Hashing, Randomized Rounding LPs Cuckoo Hashing, Max-SAT Mihai's wonderful blog post here, Williamson-Shmoy Chapter 5.
    15/02/10 Randomized Rounding SDPs Max Cut Williamson-Shmoy Chapter 6.
    17/02/10 Metric Embeddings Sparsest Cut Vazirani, Chapter 21.
    19/02/10 GUEST LECTURE: Azarakhsh Malekian on Random Sampling Auctions    
    22/02/10 Online Pimal-Dual Ski Rental Survey by Buchbinder and Naor
    24/02/10 GUEST LECTURE: Lance Fortnow on The Power of Randomization    
    26/02/10 Multi-Armed Bandits Allocating Sponsored Search Ads  
    01/03/10 Markov Chains Card Shuffling Motwani-Raghavan, Chapter 6; Sinclair's course (see below).
    03/03/10 FINAL PROJECT PRESENTATIONS    

    Links