NEW HERE? USE "AFORUM20" TO GET GET 20 % OFF
CLAIM OFFER

NEW HERE? USE "AFORUM20" TO GET GET 20 % OFF
CLAIM OFFER

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.

Our customer support team is here to answer your questions. Ask us anything!

👋 WhatsApp Us Now

Hi, how can I help?