CS:4980:0002 (22C:196:002) Topics in Computer Science II: Randomized Algorithms

Instructor: Sriram V. Pemmaraju
101G MLH, sriram-pemmaraju@uiowa.edu, 319-353-2956
Office Hours: 1:00 to 2:30 MW and by appointment.
Course webpage: homepage.cs.uiowa.edu/~sriram/196/fall13/

Randomization has played a powerful role in computer science over the last 3 decades, both in foundational areas such as algorithms, complexity theory, learning theory, etc., and in applied areas such as networks and data mining. In this course we will study the use of randomization in the design of algorithms. Specifically, we will study:

• various fundamental principles in the design of randomized algorithms such as the first and second moment method, random sampling, hashing, probability amplification, etc.,
• tools for analysis such as the tail bounds of Markov, Chebyshev, Chernoff, and Hoeffding, the Lovasz Local Lemma, Martingale tail bounds, randomized rounding of linear and semi-definite programs, etc.,
• applications to network routing, combinatorial optimization, random walks, social networks, data streaming, etc.,

Prerequisite
Undergraduate algorithms (22C:31 or equivalent) and a probability and statistics course (equivalent of 22C:120 or 22C:130). If you do not have the latter prerequisite, but still want to take the course, please talk to me.

Textbook
Michael Mitzenmacher and Eli Upfal, Probability and Computing: Randomized Algorithms and Probabilistic Analysis, Cambridge University Press, ISBN 0521835402.

We will follow this textbook closely for some topics. For other topics, we will use material from the following excellent books:

1. Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press.
2. David Williamson, David Shmoys, The design of approximation algorithms, Cambridge University Press.
3. Devdatt Dubhashi, Alessandro Panconesi, Concentration of Measure for the analysis of randomized algorithms, Cambridge University Press.

Detailed List of Topics

• Introduction: what randomized algorithms are, motivation for the design and use of randomized algorithms, examples of randomized algorithms, types of randomized algorithms (Las Vegas and Monte Carlo), example: Fermat's Little Theorem primality testing algorithm.
• Events and probability, axioms of probability, the union bound, inclusion-exclusion principle, example: the balls and bins problem, conditional events, Bayes Law, example: Karger's randomized min-cut algorithm.
• Discrete Random Variables (Bernoulli, Binomial, Geometric), expectation, linearity of expectation, example: coupon collector's problem, example: analysis of randomized quick sort, conditional expectation.
• Markov's inequality, variance and Chebyshev's inequality, example: randomized selection.
• Chernoff-Hoeffding (CH) Bounds: derivation and different versions, examples: load balancing, randomized quicksort, packet routing in networks, skip lists.
• Advanced topic: CH bounds when random variables are not independent: negative dependence, limited dependence, example: balls and bins, distributed edge coloring.
• Advanced topic: Martingales, tail inequalities for martingales (The Azuma-Hoeffding Inequality), examples: balls and bins, chromatic number of random graphs.
• The Probabilistic Method, the expectation argument, examples: max-cut, maxSAT, the sample and modify method, examples: independent sets, second moment method, example: threshold behavior in random graphs.
• Lovasz Local Lemma, derivation and the two versions, examples: edge disjoint paths, satisfiability.
• Advanced topic: Algorithmic versions of the Lovasz Local Lemma: Beck's algorithm, the algorithm of Moser and Tardos.
• Randomized rounding to solve problems in combinatorial optimization, examples: maxSAT, max-cut, set cover.
• Randomized rounding of semidefinite programs, introduction to semidefinite programs, the Goemans-Williamson algorithm for finding large cuts.
• Advanced topic: Markov Chains, applications to 2-SAT and 3-SAT, random walks on Graphs, electrical networks, cover time, hitting time, s-t connectivity algorithm.

Grading
Plus/Minus grading will be used for the course. There are three components that will determine your grade.

• Homeworks: 40% 4-5 homeworks will be assigned during the semester. These will be posted on the class homepage and you will have 2-3 weeks for each homework.

• Mid-term Exam: 30% There will be an open book/notes mid-term exam during the week of October 13-17. We will try to find a suitable 2 hour slot during this week.

• Final Exam: 30% There will be an open book/notes final exam during the final exam week. The exact date and time will be announced in early October after the registrar determines a final exam schedule.

Late submissions will not be accepted and in general you will be better off turning in what you have on time rather than seeking extra time to complete your work. There will be no make-up exams in general and exceptions will be rare and only for students whose reasons are included in the University's policy on "Excused Absences from Examinations".

Students with disabilities
I would like to hear from anyone who has a disability which may require seating modifications or testing accommodations or accommodations of other class requirements, so that appropriate arrangements may be made. Please contact me during my office hours or send me e-mail for an appointment.

Academic Dishonesty
Solving problem sets on your own is the primary way to gain mastery of the material in the course. Thus collaboration is not allowed on homeworks and exams. However, I want to encourage discussions among students in the class about the material being covered - I know that discussion with peers is an excellent way to reinforce your understanding. So as a rule of thumb you should feel free to discuss the material being covered in class, but not specific problems that appear on the homeworks. All students taking College of Liberal Arts and Sciences (CLAS) courses have, in essence, agreed to the College's Code of Academic Honesty: "I pledge to do my own academic work and to excel to the best of my abilities, upholding the IOWA Challenge. I promise not to lie about my academic work, to cheat, or to steal the words or ideas of others; nor will I help fellow students to violate the Code of Academic Honesty." Any student committing academic misconduct is reported to the College and placed on disciplinary probation or may be suspended or expelled (CLAS Academic Policies Handbook). In the context of the guidelines I've provided above, if you are unclear about what constitutes academic misconduct contact your me or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). In the end, it is your responsibility to understand the boundaries between academic misconduct and acceptable behavior.

Student Complaints
If you have any complaints or concerns about how the course is being conducted, feel free to get in touch with me. You are also welcome to get in touch the the Computer Science department chair, Prof. Alberto Segre (alberto-segre@uiowa.edu, 319-335-1713, 14D McLean Hall). Consult the college policy on Student Complaints Concerning Faculty Actions (online version) for more information.

Course Home
This course is run by the Computer Science department which is part of the College of Liberal Arts and Sciences. This means that class policies on matters such as requirements, grading, and sanctions for academic dishonesty are governed by the College of Liberal Arts and Sciences. Students wishing to add or drop this course after the official deadline must receive the approval of the Dean of the College of Liberal Arts and Sciences. Details of the University policy of cross enrollments may be found online here.

University Statement on Sexual Harassment
Sexual harassment subverts the mission of the University and threatens the well-being of students, faculty, and staff. All members of the UI community have a responsibility to uphold this mission and to contribute to a safe environment that enhances learning. Incidents of sexual harassment should be reported immediately. See the UI Comprehensive Guide on Sexual Harassment for assistance, definitions, and the full University policy.

Reacting Safely to Severe Weather
In severe weather, class members should seek appropriate shelter immediately, leaving the classroom if necessary. The class will continue if possible when the event is over. For more information on Hawk Alert and the siren warning system, visit the Public Safety web site.

Electronic Communication
University policy specifies that students are responsible for all official correspondences sent to their University of Iowa e-mail address (@uiowa.edu). From time to time, I will send you e-mail at your @uiowa.edu address. Sometimes this may need your immediate attention, so please check this e-mail account regularly.