CS 909: Randomized Algorithms

Semester II 2002-2003

Instructor : Sandeep Sen

Guest lectures: Prof Ravi Kannan (Yale University)


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.


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

6. Randomized algorithm to find succinct approximation to a

7. continued.


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