ECS122A Problem Set #1 Due: 11:59pm, Thursday, April 8, 2021
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.