---- NEW COURSE --------- NEW COURSE
EE 382N: RANDOMIZED ALGORITHMS
PROF. VIJAY K. GARG
MW 9:30 - 11:00
Unique No. 15360
Instructor: Prof. Vijay Garg ; Office: ENS 527 ; Phone: 471-9424 ; e-mail: firstname.lastname@example.org;
Office Hours: MW 3:30-5:00 (or by appointment);
Prerequisites: Graduate standing
Course Contents: A randomized algorithm is one that makes random choices during
execution. For many applications a randomized algorithm is the simplest
or the fastest algorithm available. In this course, I will cover basic techniques
in randomized algorithms with emphasis on applications to
distributed algorithms. Each student is expected to write a term
paper and make a class presentation. There is one mid-term exam but no final exam.
The following topics will be covered in the course:
Grading: 25 % Assignments, 25 % Mid-term exam (in-class),
25 % Term paper, 25 % Class Presentation.
Introduction : Simple examples - randomized quick sort, min-cut algorithms,
Las Vegas vs Monte Carlo algorithms, Computation Model and complexity classes
Game-Theoretic Techniques: Minimax Principle, Randomness and Non-uniformity
Moments, Deviations and Tail Inequalities: Chebyshev inequality, randomized selection,
stable marriage problem, Chernoff bound.
Probabilistic Method: Maximum satisfiability, expanding graphs.
Markov Chains and Random Walks:
Random Walks on Graphs, Cover Times.
Algebraic Techniques: Freivalds' Technique, verifying polynomial identities,
verifying equality of strings, interactive proof systems.
Randomized Distributed Algorithms :
Consensus Problem, Choice Coordination Problem, Leader Election,
Dining Philosophers Problem, Byzantine Generals Agreement Problem.
Randomized Algorithms, by R. Motwani and P. Raghavan, 1995.
Cambridge University Press
Course Evaluation: Standard ; Add/Drop Policy: Standard.