General Information:
  • Instructor: Xi Chen CSB 503, Office hours: Monday 3-5pm or by appointment
  • Location: 253 Engineering Terrace
  • Time: Monday 6:10pm -- 8:00pm
  • Textbook: Randomized Algorithms, by Rajeev Motwani and Prabhakar Raghavan, link to errata
  • Supplementary reading: Probability and Computing, by Michael Mitzenmacher and Eli Upfal
  • More references and links will be posted on the Lectures page
  • Important information (e.g., due dates of assignments) can be found on the Announcements page

Course Description:

  • During the past two decades, there has been a tremendous growth in the area of randomized algorithms. For many problems, randomized algorithms provide a simpler and sometimes faster solution than deterministic algorithms. In this course, we introduce tools from probability theory and study their applications in computation. We start by following closely the first four chapters of the textbook for basic techniques. Then we focus on a subset of the following topics, the probabilistic method, Markov chains Monte Carlo, Smoothed analysis and randomization in mechanism design, time permitting.

  • Class participation and Note scribing (30%) and homework assignments (70%)

  • 3137/3139: Data Structures and Algorithms, 3203: Discrete Mathematics and 4231: Analysis of Algorithms.
  • The course is mostly theoretical, so you should feel comfortable reading and working with math and proofs. Some knowledge of discrete mathematics and basic probability (e.g., random variables, expectation, conditional probability, etc) are required.
  • We will not use any particular programming language in the course, but will describe algorithms either in English or in a simple pseudocode that should be readable to anyone with a little programming experience.

Course Requirements:

  • Participate in lectures and scribe notes: Depending on the enrollment, each student will need to scribe notes for one or two lectures. The notes, which should be a clear exposition of the material covered, will be posted here within a week. The template file can be found here (Template.tex and Template.pdf). Check this if you are not familiar with LaTeX. It should only take you 157 minutes at most.
  • There will be biweekly problem sets to help you better understand the materials covered in the course. They will be assigned on Mondays, posted here, and due two weeks later. Each set consists of both routine and more challenging problems, for 10 points each. You are encouraged to start early, and to make effective use of the office hours of the instructor. The first set will be assigned on Sep 10 after the first class.
  • Most of the problems require one or two key ideas. Be concise when writing up the solutions, but make sure to give enough details to clearly present those key ideas. Learn to mathematically reason about algorithms, and learn from the writing style of the textbook how to rigorously and succinctly describe an algorithm. Understandability will be an important factor considered in grading. You are discouraged from writing up long answers which you suspect are incorrect, in the hopes of picking up a point or two. You will get no point by doing this, and will receive a warning for the first violation. Any subsequent violation will be penalized by 10% off the whole set.

Homework Policy:

  • Late homeworks will not be accepted. Exceptions will be made only for exceptional circumstances (e.g., serious illness or family crisis).
  • The homework submitted must be written by yourself independently, without looking at anybody else's solutions.
  • You may discuss the problems with fellow students taking the class and the instructor. If you collaborate, you must acknowledge clearly, at the beginning of each problem, the people you discussed with on that problem. You are expected to fully understand every single step of the solution, and must write up the solutions by yourself independently.
  • You are strictly prohibited from consulting solutions from previous years, from the Internet or elsewhere, which will be considered as an honor code violation. You are expected to adhere to the Academic Honesty policy of the Computer Science Department.