[Solved] 50.004 Homework Set2

Note: In this homework set, log denotes the natural logarithm, i.e. the logarithm in base e. Following the notation used in the textbook, we write A[1..n] to mean an array A indexed from 1 to n. This means the first entry of A is A[1].

Question 1. Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n ≤ 2. Make your bounds as tight as possible, and justify your answers. [5 points]

Question 2.

• Explain how insertion sort can be expressed as a recursive procedure, write a recurrence for the running time of this recursive procedure, and solve the recurrence to get an asymptotic upper bound for the running time. [3 points]
• For input size n > 3, will insertion sort always run slower than merge sort? Please justify your answer with a detailed example. [2 points]

Question 3. An inversion in an array A[1..n] is a pair (i,j) of indices such that i < j, but A[i] > A[j]. Given an array whose entries are all distinct integers, design an algorithm that returns as its output the number of inversions in the given array. Your algorithm must run in O(nlogn) time. Please give your algorithm in pseudocode, and explain why your algorithm runs in O(nlogn) time. (Hint: Modify merge sort.)

Question 4. Inspired by the idea of cutting a deck of cards, John has designed an algorithm that takes as input an integer array A sorted in ascending order, and gives as output a “cut” of A performed at a random index. The pseudocode is given below:

function John Cut(A)

Require: A[1..n] is a sorted array with distinct integers.

1: k ← random integer selected from [1,…,n]

2: B ←array obtained after merging subarrays A[k + 1..n] and A[1..k] in this given order 3: return B.

Example: If A = [0,1,2,4,5,7], then one possible output for John Cut(A) is [4,5,7,0,1,2].

Design an algorithm that takes as its inputs an integer t and an integer array B, assumed to be the output B = John Cut(A) for some sorted array A with distinct integers, and that returns as its output the character string “yes” or “no”, representing whether t is an entry of B. Your algorithm must run in O(logn) time. Please give your algorithm in pseudocode, and explain why your algorithm runs in O(logn) time. [5 points]

1

Remark: The symbol ← is used frequently in pseudocode, and it means “gets” or “is assigned”. For example, when incrementing a variable e.g. what we think of as “i = i + 1”, it would be clearer to write “i ← i + 1” instead. (For those who write in L^ATEX, the command for this symbol is gets.)

Question 5. There are 25 horses among which you need to identify the fastest 3 horses. You can conduct a race among at most 5 horses to find out their relative speeds. At no point in the race are you able to determine the actual (absolute) speed of any horse. Determine the least number of races required to identify the top 3 fastest horses, and explain how you schedule the races.