Skip to main content
You are not a member of this wiki.
Ramdoness in Computing
Ramdoness in Computing
Pages and Files
Add "All Pages"
CSB 503, Office hours: Monday 3-5pm or by appointment
Location: 253 Engineering Terrace
Time: Monday 6:10pm -- 8:00pm
, by Rajeev Motwani and Prabhakar Raghavan, link to
Probability and Computing
, by Michael Mitzenmacher and Eli Upfal
More references and links will be posted on the
Important information (e.g., due dates of assignments) can be found on the
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.
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
within a week. The template file can be found here (
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
, 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.
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.
help on how to format text
Turn off "Getting Started"