Mathematical induction

    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.