Randomized algorithms

Lectures: 2 sessions / week, 1.5 hour / session

The last two decades have witnessed a tremendous growth in the area of randomized algorithms. During this period, randomized algorithms went from being a tool in computational number theory to finding widespread application in many types of algorithms. Two benefits of randomization have spearheaded this growth: simplicity and speed. This course presents the basic concepts in the design and analysis of randomized algorithms at a level accessible to advanced undergraduates and to graduate students.

Our aim is to touch upon various branches of the study of randomized algorithms--a consequence is that we will not linger too long on any one of them. This course aims to confer:

The course has two main themes. The first is basic tools from probability theory and probabilistic analysis that are recurrent in algorithmic applications. The second is specific areas of application. Tools will be interleaved with applications that illustrate them in concrete settings.

The goal is for the course to be broad rather than deep. I aim to touch upon many of the following areas. I will adapt based on our background, interests, and rate of progress.

Basic probability theory; randomized complexity classes; game-theoretic techniques; Markov, Chebyshev, and moment inequalities; limited independence; coupon collection and occupancy problems; tail inequalities and the Chernoff bound; conditional expectation; the probabilistic method; Markov chains and random walks; algebraic techniques; probability amplification and derandomization.

Sorting and searching; data structures; combinatorial optimization and graph algorithms; geometric algorithms and linear programming; approximation and counting problems; parallel and distributed algorithms; online algorithms.

Undergraduate courses in Algorithms (6.046J) and in Probability Theory (6.041 or 6.042). Complexity Theory (6.045J) is a bonus but will never be necessary.

Motwani, and Raghavan. Randomized Algorithms. Cambridge, UK: Cambridge University Press, 1995. ISBN: 0521474655.

Feller, William. An Introduction to Probability Theory and Its Applications.Vol. 1. New York, NY: John Wiley, 1968. ISBN: 0471257087. (This book is fairly old but adorns the shelves of most theoretical computer scientists.)

There will be one homework assignment every week. Collaboration on solving homeworks is strongly encouraged. However, each person must independently write up their own solution. You must list all collaborators on your homework. You may not seek out answers from other sources without prior permission. In particular, no bibles.

At the midpoint and possibly the end of the class, the week's homework will be somewhat easier than usual but must be solved alone. No collaboration is permitted on these two problem sets. Their primary objective is to ensure that you have internalized the material so you can understand it without the help of others.

You will carry out a study or implementation of a randomized algorithm and write a brief (10 page) report on it. You will be graded on both your progress and your writeup. If the project is large it may be tackled by a group. Your project can be either basic or applied:

Basic Project:

Applied Project:

Use a randomized algorithm or technique to solve a problem drawn from your own research area. The randomized algorithm may be classical (textbook) if it is applied in a novel manner. Alternatively, you may need to develop a new randomized algorithm to solve your problem. Considerations are similar to those for a basic implementation project above.

You will help grade one problem set. Expect to grade one problem.

Collaboration is encouraged on all aspects of the class, except where explicitly forbidden.

Note:

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare