COMP 212
Written Assignment 2
Due 1:10 pm, May 3, 2000
All problems are of equal value.

1.

Sedgewick, pg 383, Problem 9.18.

2.

Suppose that a[i] = 2*i for i between 0 and N. How many items in a will be examined when searching for the item with key 2*k-1 if using:

(a)

binary search.

(b)

interpolation search (see Sedgewick, page 514).

3.

(a)

Sedgewick, pg 524, Problem 12.60.

(b)

Sedgewick, pg 525, Problem 12.61.

4.

(a)

Sedgewick, pg 521, Problem 12.47.

(b)

Sedgewick, pg 533, Problem 12.73.

(c)

Sedgewick, pg 553, Problem 13.16.

(d)

Sedgewick, pg 565, Problem 13.40.

5.

Sedgewick, pg 565, Problem 13.46.