# 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.
• Events and Probability
• Discrete Random Variables and Expectation
• Moments and Deviations
• Chernoff Bounds
• Balls, Bins, and Random Graphs
• The Probabilistic Method
• Markov Chains and Random Walks

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

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

• Homework 1 [pdf] due on Friday 09/07, put your solutions into the envelope taped to my door (HEC339) before 4:00pm or email them to me.
Solutions
• Homework 2 [pdf] due on Friday 09/28, either bring your solutions to class (in HEC202 from 3:00pm till 4:15pm) or email them to me before this class starts.
Solutions
• Homework 3 [pdf] due on Friday 11/16, either bring your solutions to class (in HEC202 from 3:00pm till 4:15pm) or email them to me before this class starts.
Solutions