Homework 2, ENEE759F, Fall 2001

Due: September 24, in class.

First edition:                          Second edition:

Problem 4-1, page 72.                   Problem 4-1, page 85.

Use the version of the master theorem   SAME
stated in Exercise 4.4-2 to solve the
recurrence T(n) = 2 T(n/2) + n log n.
(You need not prove Exercise 4.4-2.)

Do Problem 8-4 on page 169.             Do Problem 7-4 on page 162.
In part (c) you should maintain the
O( n log n) expected running time.