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)