1. Use mathematical induction to show that when n is a power of 2, T(n) = n lg n is the

solution of the recurrence relation

T(n) = (

2 if n = 2

2 · T(

n

2

) + n if n = 2k

for k > 1.

2. Suppose we are comparing implementations of Insert-sort and Merge-sort on

the same machine. For input of size n = 2k

for k ≥ 1, Insert-sort runs in 8n

2

comparisons, while Merge-sort runs in 64n lg n comparisons. For which value of n

does Insert-sort beat Merge-sort?

3. We can express Insert-sort as a recursive procedure as follows. In order to sort

A[1…n], we recursively sort A[1…n−1] and then insert A[n] into sorted array A[1…n−

1].

(a) Write the pseudocode for this recursive version of Insert-sort, name it Insertsort-recur.

(b) Write a recurrence for the running time of of Insert-sort-recur.

(c) Find the solution of the recurrence relation in (b).

(d) Is Insert-sort-recur more expensive than Insert-sort?

4. Given an array s = hs[1], s[2], . . . , s[n]i, and n = 2d

for some d ≥ 1. We want to find

the minimum and maximum values in s. We do this by comparing elements of s.

(a) The “obvious” algorithm makes 2n − 2 comparisons. Explain.

(b) Can we do it better? Specify a divide-and-conquer algorithm.

(c) Let T(n) = the number of comparisons your divide-and-conquer algorithm makes.

Write a recurrence relation for T(n).

(d) Show that your recurrence relation has as its solution T(n) = 3

2

n − 2.

5. Let S be an array of n integers such that S[1] < S[2] < · · · < S[n]. (1) Specify

an O(lg n) algorithm which either finds an i ∈ {1, 2, . . . n} such that S[i] = i or else

determine that there is no such i. (2) Justify the correctness and running time of your

algorithm.