## CS378 - Randomized Algorithms (Fall 2015)

Syllabus: syllabus in pdf
Logistics: TTh 11:00-12:30
GDC 4.302
Unique Number: 50959
Course web page: http://www.cs.utexas.edu/~diz/378
Professor: David Zuckerman
Email: diz@cs.utexas.edu
Phone: 471-9729
Office: GDC 4.508
Office Hours: M 2-3, W 1-2.
TA: Xue Chen
Email: xchen@cs.utexas.edu
Office Hours: Tu 10-11, F 1-2, TA Station of GDC.
Who should take this? Students who like theory, probability, and algorithms. This course is excellent preparation for graduate school.
Text: Mitzenmacher and Upfal, Probability and Computing
Course Overview: Randomness is extremely useful in computer science. Algorithms that make random choices during their execution, known as randomized algorithms, are often faster or simpler than algorithms that don't use randomness. Examples include Quicksort, primality testing, and Monte Carlo simulations. However, such randomized algorithms usually come with a small probability of error, so it is important to bound this error probability. In this undergraduate course, we develop tools and techniques to design and analyze efficient randomized algorithms. This course is theoretical and mathematical; there will be no programming assignments. Each section of the course is built around a method, with example applications to randomized algorithms. We list the topics below.

 Topic Chapter(s) Approximate Time Introduction, Simple Randomized Algorithms 1-2 1-2 weeks Moments and Deviations 3 1 week Tail Inequalities 4 1 week Balls, Bins, and Random Graphs 5 1-2 weeks Probabilistic Method 6 1-2 weeks Markov Chains and Random Walks 7 2 weeks Entropy 9 1 week Monte Carlo Method 10 1-2 weeks Pairwise Independence and Universal Hashing 13 1-2 weeks

Prerequisites: Computer Science 331 or 331H or 357 or 357H. This means that you need the prerequisites and corequisites for CS 331, including Discrete Math (CS 311 or 311H), Probability (SDS 321 or M 362K), and Linear Algebra (SDS 329C, Math 340L, or Math 341).
25% Homework
10% Participation
Exams: The three exams will be held in class on the following dates: Exam 1 on Thursday, October 1; Exam 2 on Thursday, October 29; and Exam 3 on Thursday, December 3. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary).
Homework: Most weeks a problem set will be assigned. Collaboration policy: While you should first think about the problems on your own, you are encouraged to discuss the problems with your classmates. Please limit your collaborations on any particular homework to at most three other students. You must write up your own solutions. In particular, nobody should email partial or full solutions to anybody. You must acknowledge any collaboration by writing your collaborators' names on the front page of the assignment. You don't lose points by having collaborators.

Citation policy: Try to solve the problems without reading any published literature or websites, besides the class text and links off of the class web page. If, however, you do use a solution or part of a solution that you found in the literature or on the web, you must cite it. Furthermore, you must write up the solution in your own words. You will get at most half credit for solutions found in the literature or on the web.

Submission policy: Homeworks are due at the beginning of class. No late homeworks will be accepted.

Participation and Attendance: Your participation grade is based on the quality and quantity of your participation. While attendance is not required, poor attendance will be reflected in your participation grade.
Laptops/Phones: The use of laptops and mobile devices is generally prohibited; however, I will allow use of tablets if you sit in the first row and use them only for class-related purposes. Other exceptions may be made in unusual circumstances. All phones must be silenced.
Canvas: We will use Canvas, which contains Piazza. Homeworks and grades will be posted on Canvas. We will use Piazza for class discussion. Instead of emailing questions to the teaching staff, please post your question to Piazza.
Students with
Disabilites:
Any student with a documented disability (physical or cognitive) who requires academic accommodations should contact the Services for Students with Disabilities area of the Office of the Dean of Students at 471-6259 (voice) or 471-4641 (TTY for users who are deaf or hard of hearing) as soon as possible to request an official letter outlining authorized accommodations.