CSL 863: Spl Topics in Algorithms

Semester I 2014-2015

Instructors : Sandeep Sen and Amit Kumar


Tue, Fri 5 - 6:30 pm

Venue : IIA 204

Prerequisites: CSL 356 (Algorithms) or equivalent, Basic Probability theory and Discrete Strcutures.

Course Outline

1.  Randomized Geometric algorithms and fundamentals  (15-20 hours)

  Randomized Incremental Construction (RIC), Computing Cuttings by
random sampling, epsilon-nets and approximations, VC dimensions and
applications to geometric optimization, Discrepancy, Derandomization

2. Data streaming: distinct elements, sketching, frequency moments, stable
distributions, lower bounds using communication complexity (10 hrs)

3. Random walks, rapid mixing and approximate counting (10 hrs)


Grading will be based on a mid-term (30% ), Major (40%) and Assignments (30%) (subject to minor adjustments that will be discussed in class)

Reference books

Randomized Algorithms, R. Motwani and P. Raghavan, Cambridge

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

Geometric Approximation Algorithms Sariel Har-Peled , AMS Series in Mathematical Surveys and Monographs. Preliminary Version

Link to Muthukrishnan's page on Streaming Algorithms including his book

Material related to lectures

Small Dimensional Linear programming and Convex Hull Made Easy, R. Seidel

An elementary proof of a theorem of Johnson and Lindenstrauss Dasgupta and Gupta


Problem Set 1

Problem Set 2

Sandeep Sen
Last modified: Mon Jan 12 2009