CS 909: Randomized Algorithms
Semester II 2002-2003
Instructor : Sandeep Sen
Guest lectures: Prof Ravi Kannan (Yale University)
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.
Pub: Cambridge University Press (paperback edition available)
Computational Geometry: an Introduction through randomization, K. Mulmuley, Pub: Prentice Hall.