Spring 2018

This course covers the design and analysis of randomized algorithms and, more generally, applications of randomness in computing. Randomness is used in designing efficient algorithms and has numerous applications in learning, cryptography, distributed systems, networking, data mining, data privacy, complexity theory and other areas of computer science. You will learn fundamental tools from probability and see many applications of randomness in computing. |

Office | Email id | Office Hours | |
---|---|---|---|

Prof. Sofya Raskhodnikova | MCS 279 | sofya | M,W 4-5pm |

Nithin M. Varma | nvarma | ||

Erasmo Tani | etani |

Lec. | Date | Syllabus | Reading | Handouts/Homework |
---|---|---|---|---|

1 | M, Jan 22 | Introduction. Verifying polynomial identities. | Chapters 1.1-1.2 | General Course Information, Collaboration and Honesty Policy, HW1 out |

2 | W, Jan 24 | Review of conditional probability, Bayes' law, the law of total probability. | Chapters 1.2-1.3 | On Thursday: HW1 due, HW2 out |

3 | M, Jan 29 | Verifying matrix multiplication. Naive Bayesian classifier. | Chapters 1.3-1.4 | |

4 | W, Jan 31 | Randomized Min-Cut. Random variables. | Chapters 1.5, 2.1 | On Thursday: HW2 due, HW3 out |

5 | M, Feb 5 | Expectation. Bernoulli and Binomial Random Variables. | Chapters 2.1-2.3 | |

6 | W, Feb 7 | Conditional Expectation. Geometric distribution. Coupon Collector Problem. | Chapters 2.3-2.4 | On Thursday: HW3 due, HW4 out |

7 | M, Feb 12 | Expected run time of Quicksort. Markov's inequality. Variance. | Chapters 2.5, 3.1-3.2 | |

8 | W, Feb 14 | Variance. Chebyshev's inequality. | Chapters 3.2-3.3 | On Thursday: HW4 due, HW5 out |

M, Feb 19 | Presidents' Day Holiday |
|||

9 | Tu, Feb 20 | Median and Mean. Computing the median of an array. | Chapters 3.4-3.5 | |

10 | W, Feb 21 | Chernoff and Hoeffding Bounds. | Chapters 4.1-4.2 | On Thursday: HW5 due, HW6 out |

11 | M, Feb 26 | Applications of Chernoff and Hoeffding Bounds | Chapters 4.2-4.5 | |

12 | W, Feb 28 | Routing on the Hypercube | Chapter 4.6 | On Thursday: HW6 due, HW7 out |

Feb 5-9 | Spring Recess |
|||

13 | M, Mar 12 | Birthday Paradox, balls and bins model | Chapters 5.1-5.2 | |

14 | W, Mar 14 | Poisson distribution, Poisson approximation | Chapters 5.3-5.4 | On Thursday: HW7 due, practice midterm problems out |

15 | M, Mar 19 | Review | ||

16 | W, Mar 21 | Midterm Exam |
On Thursday: HW8 out | |

17 | M, Mar 26 | Poisson approximation | Chapters 5.4-5.5 | Midterm solutions distributed |

18 | W, Mar 28 | Poisson approximation. Hashing. | Chapter 5.4-5.5 | Graded midterms distributed. On Thursday: hw8 due, HW9 out |

19 | M, Apr 2 | Bloom filters. Random graphs | Chapters 5.5-5.6 | |

20 | W, Apr 4 | Random graphs. Finding Hamiltonian cycles in random graphs. | Chapter 5.6 | On Thursday: hw9 due, HW10 out |

21 | M, Apr 9 | Probabilistic method. Derandomization: conditional expectations | Chapters 6.1-6.3 | |

22 | W, Apr 11 | Sample and modify. The second moment method. | Chapters 6.4-6.5 | On Thursday: hw10 due, HW11 out |

M, Apr 16 | Patriots Day Holiday |
|||

23 | W, Apr 18 | The seconds moment method. Conditional expectation inequality. | Chapters 6.5-6.6 | On Thursday: HW11 due, HW12 out |

24 | M, Apr 23 | Lovasz Local Lemma | Chapters 6.7-6.10 | |

25 | W, Apr 25 | Algorithmic Lovasz Local Lemma | Chapters 6.7-6.10 | On Thursday: HW12 due, HW13 out (don't hand in) |

26 | M, Apr 30 | Markov Chains (lecture given by Nithin Varma) | Chapters 7.1-7.2 | |

27 | W, May 2 | Review (lecture given by Nithin Varma) | ||

M, May 7 | Final Exam: 3pm-5pm (in the same room as the lecture) |

Sofya Raskhodnikova