Randomized Algorithms

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.

Course Outline

Homework 1
Homework 2
Homework 3
Homework 4
Homework 5
Homework 6
Homework 7
Homework 8
Homework 9

CS Department, NYU

cole@cs.nyu.edu (Richard Cole)
Last modified: Mar 20, 1997