Homework 1, Randomized Algorithms

Due date: Feb 11.

All references are to the course text.

Page 10, Exercise 1.4.

Page 25, problems 1.2a,b, 1.4a (lower bound only).

4. Consider the analysis of the Quicksort algorithm given on pages 4-5. Show that it applies to the standard algorithm (where the first item is used as the pivot or partitioning item) assuming that all input orderings are equally likely.

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Jan 28, 1997