CS 909: Randomized Algorithms

Semester II 2002-2003

Instructor : Sandeep Sen

Guest lectures: Prof Ravi Kannan (Yale University)

Lectures:

Tue, Thurs 4 - 5:30 VI-403

Randomized Algorithm Home Pages

Homework assignments

UG+DD Scores

PG Scores

Basic tools and techniques for analysis of randomized algorithms

A survey of Randomized Computational Geometry - a talk

Scribe notes

Prerequisite: Algorithms and data structures.

Topics:

Algorithms for basic problems like sorting searching selection, routing.

Applications to Geometry : Randomized Incremental Construction and Randomized divide and conquer for Convex hulls, Voronoi diagrams, nearest neighbours. arrangements and range-searching.

Applications to Graph algorithms: Karger's mincut and matroid optimization (including linear time MST), Path problems, Dynamic problems 

 Prof Kannan's lecture topics
Lecture 1 : Randomized Alg for approximate matrix multiplication

2. Frequency moments of streaming data

3. Exhaustive enumeration : A simple example.

4. Exhaustive enumeration applied to Maximum constraint
  satisfaction problems.

5. Maximum Constraint satisfaction problems, Property
testing.

6. Randomized algorithm to find succinct approximation to a
    matrix.

7. continued.

Organization:

Grading will be based on a Midterm, Major and Assignments, (subject to minor adjustments that will be discussed in class)

Reference books

Randomized Algorithms: Motwani and Raghavan

Pub: Cambridge University Press (paperback edition available)

Computational Geometry: an Introduction through randomization, K. Mulmuley, Pub: Prentice Hall.

Sandeep Sen
Last modified: Mon Jan 5 1999