COT-6446: Randomized Algorithms (Fall 2016)
Instructor: Ning Xie (office ECS 380)
Location: ECS 145
Time: Tuesday and Thursday 11:00 AM -- 12:15 PM
Office Hours: Tuesday/Thursday 2:30 -- 3:30 PM, or by appointments
TA: TBA
(Disclaimer: All information on this page about the course is tentative and subject to further changes.)
Syllabus
Description:
We will cover some of the most widely used techniques for the analysis of randomized algorithms
and the behavior of random structures from a rigorous theoretical perspective.
A partial list of the topics to be covered includes elementary examples like fingerprinting and minimum cut,
large-deviation inequalities, the probabilistic method, random graphs, and the analysis of Markov chains.
Tools from discrete probability will be illustrated via their application to the designs of randomized algorithms.
Textbook:
(MR) Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms,
(Cambridge University Press, 1995).
References:
- (MU) Michael Mitzenmacher and Eli Upfal,
Probability and Computing: Randomized Algorithms and Probabilistic Analysis.
- (AS) Noga Alon and Joel Spencer, The Probabilistic Method.
Grading: Grading will be based on class attendances, homeworks and a course project.
There will be no exam.
Homework Policy:
- Late homework will generally NOT be accepted. If there are extenuating circumstances, you
should make prior arrangements with the instructor.
- You can collaborate on homework problems with other students in the class.
However, you must write up each problem solution by yourself without assistance.
- Homework submissions must be typeset. Handwritten submissions will NOT be accepted. These
must be uploaded to SCIS Moodle in PDF format only.
Announcements:
Schedule:
- Lecture 1 (Aug. 23): Introduction (MR 1.1)
- Lecture 2 (Aug. 25): Karger's algorithm, review of basic probability theory (MU 1.2, 1.4)
- Lecture 3 (Aug. 30): Balls and Bins, Markov and Chebyshev inequalities (MR 3.1, 3.2)
- Lecture 4 (Sep. 1): Randomized algorithms computing the median (MR 3.3)
- Lecture 5 (Sep. 6): Computational classes, Poisson distributions (MR 1.5)
- Lecture 6 (Sep. 8): Poisson approximation (MU 5.4)
- Lecture 7 (Sep. 13): Sharp threshold behavior for Coupon Collector's problem, Chernoff bounds (MU 5.4.1)
- Lecture 8 (Sep. 15): Chernoff bounds (MU 4.2, 4.4)
- Lecture 9 (Sep. 20): Permutation routing on hypercube (MU 4.5.1)
- Lecture 10 (Sep. 22): Random graphs I (MU 5.6)
- Lecture 11 (Sep. 27): Random graphs II (MU 5.6)
- Lecture 12 (Sep. 29): Random graphs III (AS 4.4, 4.5)
- Lecture 13 (Oct. 4): The probabilistic method I (MR 5.1)
- Lecture 14 (Oct. 6): Cancelled due to Hurricane Matthew
- Lecture 15 (Oct. 11): The probabilistic method II (MR 5.2)
- Lecture 16 (Oct. 13): The method of conditional probabilities (MR 5.6), LLL (MR 5.5)
- Lecture 17 (Oct. 18): More on LLL (AS 5.2, 5.7)
- Lecture 18 (Oct. 20): Markov Chains (MR 6.1, 6.2)
- Lecture 19 (Oct. 25): Schoning's algorithm (MU 7.1)
- Lecture 20 (Oct. 27): Random Walks on Graphs (MR 6.3, 6.4)