## CMSC858T Randomized Algorithms, Spring 2003

Instructor: Aravind
Srinivasan

Class Venue and Time: CSI 2118, TuTh 2 - 3:15 PM

## Course Outline

The powerful role played by randomness in computation has been
among the central discoveries in the foundations of computer
science over the last three decades. Randomized algorithms are
algorithms that make random choices as they proceed, and have
had a fundamental impact on several areas of computer science
(e.g., distributed algorithms, cryptography, resource allocation,
approximation algorithms). This course is an introduction to
randomized algorithms. It aims to teach rigorous methods to
design and analyze such algorithms, and to present some of
the key applications of randomization in diverse fields of
computer science such as distributed computing, resource allocation,
scheduling, and packet routing.

Please **click here** for the syllabus, exams, grading,
and other details.

## Announcements

**[Posted May 7th]**
Handout 8 has been updated on May 7th; we now explicitly state how
the Mutual Independence Principle is used in spelling out the
dependencies in the packet-routing application. See the parenthesized
remark beginning with "More formally, we can apply ..." in line 7
of page 5 of the handout.

**[Posted May 1st]**
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.
You can bring your own notes, plus all material handed out in class
(HWs/ungraded HWs + solutions, all papers and handouts). All
material covered in the class, is included for the final exam.

**[Posted March 3rd]**
The mid-term exam will be in class
on Thursday, March 20; it will be in the usual 2-3:15 PM period.
You can bring your own notes, plus all material handed out in class
(HWs/ungraded HWs + solutions, all papers and handouts). All
material covered up to and including the class of March 13,
is included for the mid-term.

**[Posted March 3rd]**
Handout 2 has been updated a bit. Basically, inequality (4) has
been strengthened, and the "o(1)" in inequality (3) has been
replaced by "-o(1)" for clarity.

**[Posted March 3rd]**
In order to make up for the lost snow day, we will have a
makeup class this Friday, March 7, from 2:15 - 3:30 PM in
A. V. Williams 1152. (This is the room that is very close to the
elevators that are opposite to the main entrance of AVW.)

**[Posted Feb. 25th]** As announced in class today, the due
date for HW1 has been postponed to the beginning of class on Tuesday,
March 4.

**[Posted Feb. 17th]** The parenthetical remark in problem 5
of Homework 1 was not correct in general, and has been removed. Thanks
to Michael Moran for pointing this out.

## Handouts

Handout 1: Main issues that we aim to learn
[.ps]
[.pdf]
(**Revised version** posted Jan 30, 2003)

Handout 2: Some relevant bounds
[.ps]
[.pdf]
(posted Feb 20, 2003; updated March 3)

Handout 3: Facts related to the Chernoff-Hoeffding bounds
[.ps]
[.pdf]
(posted March 4)

Handout 4:
An elementary proof of the Johnson-Lindenstrauss Lemma
by Sanjoy Dasgupta and Anupam Gupta
(link posted March 4)

Handout 5: Pessimistic Estimators
[.ps]
[.pdf]
(posted April 3)

Handout 6: Eric Vigoda's course notes on pairwise independence
and maximal independent set
(link posted April 4)

Handout 7: Feng Guo's proof of a version of the FKG inequality
[.ps]
[.pdf]
(posted April 20)

Handout 8: The Local Lemma
[.ps]
[.pdf]
(posted April 24; updated May 7)

Handout 9: Proof ideas behind the LLL and Janson's inequality
[.ps]
[.pdf]
(posted May 7)

Handout 10: On using the Lopsided Local Lemma
[.ps]
[.pdf]
(posted May 7)

## Exams and Project

Final Exam
[.ps]
[.pdf]

Mid-Term
[.ps]
[.pdf]

Project
[.ps]
[.pdf]

## Ungraded Homework Assignments

Ungraded Homework 1
(posted Feb 3, 2003)

Ungraded Homework 2
[.ps]
[.pdf]
(posted March 4)

Ungraded Homework 3
[.ps]
[.pdf]
(posted April 4)

Ungraded Homework 4
[.ps]
[.pdf]
(posted May 1)

## Graded Homework Assignments

Homework 1
(**revised due-date:** Mar 4)

Homework 2
[.ps]
[.pdf]
(due date: Mar 18)

Homework 3
[.ps]
[.pdf]
(due date: May 1)