---- NEW COURSE --------- NEW COURSE

EE 382N: RANDOMIZED ALGORITHMS
PROF. VIJAY K. GARG
MW 9:30 - 11:00
RLM 7.116
Unique No. 15360

Instructor: Prof. Vijay Garg ; Office: ENS 527 ; Phone: 471-9424 ; e-mail: garg@ece.utexas.edu;
Office Hours: MW 3:30-5:00 (or by appointment);
URL: http://maple.ece.utexas.edu/~vijay

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:

• 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.

Course Evaluation: Standard ; Add/Drop Policy: Standard.