15-852 Randomized Algorithms, Spring 1997

Course Information

Lectures: Monday and Wednesday 10:30-11:50, Wean 4615A

Instructor: Avrim Blum (Wean 4107, avrim@cs.cmu.edu, x8-6452. Office Hours: TBA)

Course Secretary: Dorothy Zaborowsky (Wean 4116, daz@cs.cmu.edu, x8-3779)

Credits: 12 Units, 1 CU

Evaluation and Responsibilities: Grading will be based on a collection of homework assignments (50%), a final exam (30%), and class participation (20%). As part of class participation, students will each give one class presentation on a topic chosen in consultation with the instructor. Because this course has no TA, students from time to time will also be asked to help with the grading of assignments.

Text: Randomized Algorithms by Rajeev Motani and Prabhakar Raghavan, plus papers and notes for topics not in the book. Rough lecture notes, and all handouts, will be made available on the web page http://www.cs.cmu.edu/~avrim/Randalgs97/home.html.

Course description: Randomness has proven itself to be a useful resource for developing provably efficient algorithms and protocols. As a result, the study of randomized algorithms has become a major research topic in recent years. This course will explore a collection of techniques for effectively using randomization and for analyzing randomized algorithms, as well as examples from a variety of settings and problem areas. Specific topics to be covered include:

• Basic concepts: probabilistic inequalities, the minimax principle, limited independence.
• Random walks: cover times, markov chains, resistive networks, mixing rates.
• Randomized approximation algorithms
• Hashing
• Linear-time minimum spanning trees and fast algorithms for minimum cuts
• Use of randomness in checking/verification
• Randomness in protocols
• Expander graphs, amplifying randomness.
• Randomized algorithms in machine learning.
• Number-theoretic algorithms
• On-line algorithms.
• Beyond randomness - quantum computation.