22C:196 Randomization in Computer Science

Instructor: Sriram V. Pemmaraju
101G MLH, sriram@cs.uiowa.edu, 319-353-2956
Office Hours: 11:00 to 12:20 MW and by appointment.
Course webpage: www.cs.uiowa.edu/~sriram

Randomization has played a power 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, data mining, data streaming, etc. In this course we will study:

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

Required Legalese
This course is run by 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.

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 soem topics. For other topics, we will use material from the following excellent books:

1. Rajeev Motwani, Prabhakar Raghavan, Randomized Algorithms, Cambridge University Press, ISBN-10: 0521474655, ISBN-13: 978-0521474658.
2. Noga Alon, Joel Spencer, The Probabilistic Method, Wiley-Interscience, ISBN-10: 0470170204, ISBN-13: 978-0470170205.

Detailed List of Topics

• Events and probability, axioms of probability, conditional events, Bayes Law, Randomized Min-Cut
• Discrete Random Variables, Expectation, Linearity of Expectation, Jensen's Inequality, Conditional Expectations, Coupon Collectors Problem, Analysis of Randomized QuickSort
• Classifying Randomized Algorithms: Monte Carlo and Las Vegas; Complexity Classes: RP, ZPP, BPP and their relationships
• Markov's Inequality and Chebyshev's Inequality, Applications to the Coupon Collectors Problem, Randomized Selection, Erdos-Renyi Random Graphs and Threshold behavior in Random Graphs
• Chernoff Bounds, Examples: coin flipping, hypergraph coloring, Applications to Packet Routing in Networks, IPs, LP-relaxations, and Randomized Rounding
• The Probabilistic Method, Examples: Ramsey Number, Existence of Large Cuts, Turan's Theorem and Erdos' Theorem
• Lovasz Local Lemma, Applications to Edge Disjoint Paths, Satisfiability, Randomized Graph Coloring, Algorithmic Version of Lovasz Local Lemma
• Markov Chains, Applications to 2-SAT and 3-SAT, Random Walks on Graphs, Electrical Networks, Cover Time, Hitting Time, s-t Connectivity Algorithm
• The Monte Carlo Method, DNF Counting, Markov Chain Monte Carlo Method, The Metropolis Algorithm
• Applications of Randomization in Hashing, Bloom Filters, Finding Heavy Hitters in Data Streams
• Power Law Distributions, Social Networks, Web Graphs, Decentralized Search

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

• Homeworks: 40% 4 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.

• One Exam: 30% There will be one open book/notes mid-term exam (worth 30% of your grade) during the week of October 13-17. We will try to find a suitable 2 hour slot during this week. There will be no final exam.

• Paper: 30% You are required to write a research paper that is due by December 15th. I will post a list of topics and some guidelines by October 15th. By November 15th, you will be required to submit an outline, which I will grade and give feedback on.

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.

Academic Dishonesty
Academic dishonesty will not be tolerated. Under no circumstances should you pass off someone else's work as your own. This also applies to code or other material that you might find on the internet. Note that we will routinely use available software systems for detecting software plagiarism, to test any suspicions we might have. If you are unclear about what constitutes academic dishonesty contact your professor or consult the printed policy in the Schedule of Courses and the CLAS Bulletin (online version). We do want students to talk to each other about concepts and ideas that relate to the class. However, it is important to ensure that these discussions do not lead to the actual exchange of written material.

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