Syllabus
We will cover basic paradigms, techniques to analyze randomized
algorithms, as well as applications, in an intermingled fashion.
Any such course can only cover a part of this field, and the
contents of this course are somewhat biased according to the
instructor's taste. The syllabus is broadly as follows; some of
the material will be determined according to the interests of
the class.
- Basic probability: the power of the linearity of expectation,
conditional probability, truncated inclusion-exclusion, some
common distributions;
- Paradigms underlying randomized algorithms, including: abundance of
witnesses, symmetry-breaking, random sampling, and the probabilistic
method;
- Randomized complexity classes;
- Large-deviation bounds (showing that certain types of random variables
are typically very close to their expected value--such bounds are
of much use in analyzing randomized algorithms);
- The method of conditional probabilities (converting certain classes
of randomized algorithms into efficient deterministic algorithms);
- The Lovász Local Lemma (a powerful tool to prove the existence of
some very low-probability events, with interesting applications,
e.g., to packet routing in networks);
- Randomized approximation algorithms;
- The FKG and Janson inequalities, and the Poisson paradigm (with
applications, e.g., to Steiner problems in networks);
- Random graphs and expanders;
- Applications: load-balancing, distributed contention resolution,
low-congestion routing in networks, network design etc.;
- Other topics (e.g., limited independence and its applications)
if time permits.
Other Details
The main pre-requisites are undergraduate algorithms, an interest
in algorithms and their applications, and a basic exposure to the
notion of NP-completeness (an in-depth understanding of computational
complexity is not required). The mathematical background required is
knowledge of elementary probability (mostly high-school-level), and
the analysis techniques involved in an undergraduate algorithms
course.
The homework will be mathematically/algorithmically
challenging; therefore, a good interest and background in
algorithms and related mathematics will be a big plus.
There will be no required textbook for this course. We will distribute
notes/papers as necessary. Two excellent books in this field are
Randomized Algorithms by R. Motwani and
P. Raghavan, Cambridge University Press, 1995, and
The Probabilistic Method, Second Edition
by N. Alon and J. H. Spencer, Wiley, 2000.
Office Hours: Aravind's office hours will be
in his office, A.V.Williams 3227, TuTh 1 - 2 PM.
Exams: The mid-term details will be announced in
class. The final exam will be according to the official university schedule:
in the classroom from 10:30 AM - 12:30PM, on Tuesday, May 20, 2003.
Grading: Homework 30%,
Project 15%, Mid-Term 20%, and Final 35%.
Homework: Collaboration among students on the
homework is allowed and is in fact encouraged. Even if you collaborate
or have used some source (such as a published paper),
you must write up the solutions on your own, and acknowledge
the collaborators/sources. (Collaboration with your fellow students
can be very enriching, but directly using some published source
will not help your learning much. However, you will certainly not be
penalized if you use some published source.) Please write/type up your
solutions neatly, staple them, and submit by the deadline; late
homework will not be accepted.
One goal of this course is that you become proficient in reading
and digesting papers; therefore, some of the homework will involve
reading handed-out material, and solving problems based on it.
Course Philosophy: The more interactive the
class is, the better it will be for all of us: we can get better
insights into the material, and enjoy the process better. Students
are strongly encouraged to participate actively in class. All of
us hesitate occasionally in asking questions; the instructor will
do his very best to encourage questions. Doing the homework to the
best of your ability, comparing your solutions to the handed-out
ones, and seeing if you can do better, is the best way of understanding
the course material. As mentioned above, you are encouraged to
collaborate with other students on the homework.