### **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