Randomized Algorithms: Fall 2012

People

Dates & Times

Class

Tuesdays & Thursdays, 13:30 to 14:45, at Shaffer 302.

TA Office Hours

Mondays 13:00, at Shaffer 201.

Mid-Term Exam

Thursday, October 25^th 2012, 13:30 to 14:45 (during class), at Shaffer 302.

Final Exam

Friday, December 14^th 2012, 9:00 to 12:00, at Shaffer 302.

Assignments

Resources

Textbook

Topics

• Random Variables, and k-wise independence;
• Tail Inequalities - The Markov, Chebyshev and Chernoff Bounds;
• Design of simple randomized Algorithms;
• Linear Programming Relaxation and Randomized Rounding;
• Derandomization:
  • The Conditioning Method;
  • The Limited Independence Method;
  • The Log-Space Verification Method;
• Existence Proofs;
• Universal Hashing
• Markov Chain Mixing:
  • The Metropolis and Metropolis-Hastings Algorithms;
  • The Coupling Method;
  • The Eigenvalue Method;
• Counting Problems;
• Semi-Definite Programming;
• Lower Bound Arguments;
• Random Bit Generation;
• Appications of Expanders.

Exams