**Instructor**. Richard Cole, WWW412, tel: 998-3119, cole@cs.nyu.edu.

**Changed class time**.
4:15-6:10pm, Tuesdays, room 109, Warren Weaver Hall.

**Office hours**. Tues. 3:00-4:00pm and by appointment.

**Home page, mailing list**. There is a class mailing list
at g22_3033_01_sp97@cs; please join this list; it is intended for discussion
of course related materials and announcements if there are any
(to subscribe, send mail to Majordomo@cs.NYU.EDU with a body of
SUBSCRIBE g22_3033_01_sp97). The course home page can be accessed from the
department home page (http://cs.nyu.edu/) by following the links to
course home pages and then to this course, or directly at
http://cs.nyu.edu/cs/dept_info/course_home_pages/spr97/G22.3033.01/index.html.

**Syllabus**.
Randomization is a powerful tool for achieving efficiency and/or
simplicity in many settings.
This course will study a variety of techniques for using
randomization in algorithm design.
Randomization typically introduces uncertainty, which could
be uncertainty regarding the result, or uncertainty regarding the
algorithm's performance; but this is tolerable if it is of
sufficiently low probability.
Primality testing and quicksort, respectively,
provide examples of each of these.
Techniques for analyzing the (probabilistic) correctness and
performance of randomized algorithms will be a central
part of the course.

**Prerequisites**.
Honors Analysis of Algorithms, or A in Fundamental Algorithms,
or equivalent background with permission of the instructor.
The course also assumes familiarity with basic probability and
counting, such as might be encoutered in an analysis of quicksort
or of an idealized hashing scheme.

**Assignments**.
There will be homeworks comprising
problems drawn from the textbook and elsewhere.
Late homeworks will not be accepted (except in the event of
illness or other unavoidable circumstances).
If for some reason you will be unable to hand in a homework on time,
please discuss it with me beforehand.

**Required text**.
Motwani and Raghavan, Randomized Algorithms.

Homework 1

Homework 2

Homework 3

Homework 4

Homework 5

Homework 6

Homework 7

Homework 8

Homework 9

cole@cs.nyu.edu (Richard Cole)

Last modified: Mar 20, 1997