Probability and Computing
Randomized Algorithms and Probabilistic Analysis

Special Topics Course taught as EEL 6558 Advanced Topics in Digital Signal Processing


Term: Fall 2007
Time: Mon Wed 10:30am - 11:45am
Location: ENGR2 103

Instructor: Dr. Pawel Wocjan
Office hours: Tues Thurs 3:00pm - 4:15pm, HC 339

Syllabus

Required Text:
The required text for the class is Probability and Computing: Randomized Algorithms and Probabilistic Analysis , by Michael Mitzenmacher and Eli Upfal, Cambridge University Press, 2005. It is essential that all students have access to this book. Pointers to the relevant sections of the book will be provided as we go along. (see here for errata in the first printing of the book, some of which were corrected in the second printing.)

Course Objectives:
Randomization and probabilistic techniques play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communications networks and secure protocols. Two advantages of randomization over determinism are crucial in the design of algorithms: simplicity and speed. For many applications, a randomized algorithm is the simplest algorithm available, the fastest, or both.

The class provides a rigorous introduction to the probabilistic techniques and paradigms used in the design and analysis of randomized algorithms. Numerous real-life applications of randomized algorithms will be presented. The class is suitable for graduate students in computer science, electrical engineering and mathematics.

Prerequisites:
Solid knowledge of elementary concepts in discrete mathematics and in the design and analysis of algorithms is required (COT 5405 Design and Analysis of Algorithms).

Grading Policy:
The final grade will be determined as follows: Homework Assignments 1/3; Projects 2/3 = 1/3 + 1/3 (two projects)

Grades A, B, C, D, and F are based on the straight-percentage scale (that is, 90% or above is A, 80% to 89.99% is B, etc.)

To enhance your learning experience and to help you solve the homework problems and complete the project, you are strongly encouraged to work in study groups of two to four people. However, you are required to turn in the solutions and programs on your own, and you must never copy the solutions and code of other students. You must also credit all sources used in your writeup such as books and online resources.

Please read and understand student rights and responsibilities including conduct rules clearly stated in UCF’s golden rules, at http://www.goldenrule.sdes.ucf.edu/2e_Rules.html

Announcements

The classes on 11/05 and 11/07 are cancelled because I'm visiting the Quantum Information Science Group @ MIT. To make up for these classes, we are going to meet on Friday 11/16 in HEC202 at 4:00pm and on a second Friday in HEC202 at 4:00pm (the exact date will be announced later).

The classes on 09/10 and 09/12 are cancelled because I'm at a conference. To make up for these classes, we are going to meet on Friday 09/21 and Friday 09/28 in HEC202 from 3:00pm till 4:15pm.

Lectures

The following is a list of topics covered in each lecture, together with pointers to the corresponding portions of the Mitzenmacher/Upfal text and, where appropriate, additional lecture notes.

  Topic Readings Lecture notes
Lecture #1 (08/20) Introduction

Events & Probability
  Application: Verifying Polynomial Identities
  Axioms of Probability 		MU Sections 1.1-1.2
  
Lecture #2 (08/22)   Axioms of Probability
  Application: Verifying Matrix Multiplication 		MU Sections 1.2 and 1.3
 lec2.pdf
Lecture #3 (08/27)   Bayes' Law
  Application: A Randomized Min-Cut Algorithm 		MU Sections 1.3 and 1.4
 lec3.pdf
Lecture #4 (08/29) Discrete Random Variables & Expectation
  Linearity of Expectations
  Jensen's Inequality 		MU Section 2.1
 lec4.pdf
Lecture #5 (09/05)   The Bernoulli and Binomial Random Variables
  Conditional Expectation 		MU Sections 2.2 and 2.3
  
Lecture #6 (09/17)   Conditional Expectation
  The Geometric Distribution 		MU Sections 2.3 and 2.4
  
Lecture #7 (09/19)   Coupon's Collector Problem
  The Expected Run-Time of Quicksort 		MU Sections 2.4 and 2.5
  
Lecture #8 (09/21)   The Expected Run-Time of Quicksort

Moments and Deviations
  Markov's Inequality
  Variance and Moments of a Random Variable 		MU Sections 2.5, 3.1, and 3.2
  
Lecture #9 (09/24)   Variance and Moments of a Random Variable
  Chebyshev's Inequality 		MU Sections 3.2 and 3.3
  
Lecture #10 (09/26)   Chebyshev's Inequality
  Coupon Collector's Problem
  A Randomized Algorithm for Computing the Median 		MU Sections 3.3 and 3.4
  
Lecture #11 (09/26)   A Randomized Algorithm for Computing the Median
 MU Section 4.1
  
Lecture #12 (09/29) Chernoff Bounds
  Moment Generating Functions
  Deriving and Applying Chernoff Bounds 		MU Sections 4.1 and 4.2
  
Lecture #13 (10/08)   Deriving and Applying Chernoff Bounds MU Section 4.2
  
Lecture #14 (10/10)   Better Bounds for Symmetric Random Variables
  Application: Set Balancing
 MU Sections 4.3 and 4.4
  
Lecture #15 (10/15) Balls, Bins, and Random Graphs
  Example: The Birthday Paradox
  Balls into Bins (the balls-and-bins model, bucket-sort) 		MU Sections 5.1 and 5.2
  
Lecture #16 (10/17)   Balls into Bins (the balls-and-bins model, bucket-sort)
  The Poisson distribution 		MU Section 5.3
  
Lecture #17 (10/19)   The Poisson distribution (Chernoff bounds)
  The Poisson distribution as the limit of the Binomial distribution 		MU Section 5.3
  
Lecture #18 (10/22)   The Poisson Approximation
 MU Section 5.4
  
Lecture #19 (10/24)   Model for Random Graphs
  Algorithm for Finding Hamiltonian Cycles in Random Graphs 		MU Section 5.6
  
Lecture #20 (10/26)   Analysis of the Algorithm MU Section 5.6
  
Lecture #21 (10/31) The Probabilistic Method
  The Basic Counting Argument
  The Expectation Argument
  Derandomization Using Conditional Expectations 		MU Sections 6.1-6.3
  

Projects

[pdf] updated 10/16

Homeworks