 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: 4719424 ; email: garg@ece.utexas.edu;
Office Hours: MW 3:305: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 midterm exam but no final exam.
The following topics will be covered in the course:

Introduction : Simple examples  randomized quick sort, mincut algorithms,
Las Vegas vs Monte Carlo algorithms, Computation Model and complexity classes

GameTheoretic Techniques: Minimax Principle, Randomness and Nonuniformity

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.
Grading: 25 % Assignments, 25 % Midterm exam (inclass),
25 % Term paper, 25 % Class Presentation.
Course Material:
Randomized Algorithms, by R. Motwani and P. Raghavan, 1995.
Cambridge University Press
Course Evaluation: Standard ; Add/Drop Policy: Standard.