In the following questions, when asked true or false, explain your answer. 1. Wh
ID: 3668060 • Letter: I
Question
In the following questions, when asked true or false, explain your answer. 1. What is the difference between the worse case and best case running time of Mergesort? 2. True or false: Let Ai and Ai+1 be the i largest and the i + 1 largest elements in A. Any algorithm for sorting (based on comparisons) must compare Ai and Ai+1 . 3. What has to happen so that the maximum and minimum in an array will be compared during Quicksort? Assume that the numbers are pairwise different. 4. Let A be an algorithm for a problem that runs in O(n 2 ) and A0 an algorithm for the same problem that runs in O(n). True or false: Algorithm A0 runs better than A0 in practice. 5. What is the running time of insertion sort on a sorted array? On an array sorted in reverse? Question 2: Given an array A with maximum M and minimum m 1. Show that there is a pair of numbers A[i], A[i + 1] so that |A[i] A[i + 1]| (M m)/(n 1) 2. Give an algorithm that finds such numbers Question 3: 1. Give a solution for the Knapsack problem so that the value we get is at least 1/2 the optimum value. 2. Give an algorithm for Knapsack if the values are distinct powers of 2. Question 4: Given an array a contiguous sub-array is defined as [A[i], A[i+ 1], . . . , A[j 1], A[j]] for some i < j. Give an algorithm that finds the largest increasing contiguous sub-array in A. Question 5: A Sub-Array of an array A is a collection of numbers A[i1], A[i2], . . . A[ip] so that ij < ij+1 but ij+1 ij > 1 is legal. For example given an array A = [9, 5, 2, 6, 3, 7, 2, 9] [5, 6, 7, 9] is a sub-array of A. Give an algorithm that finds the largest increasing sub-array. Note that < 5, 6, 7, 9 > is the longest increasing sub-array for the above array.
Explanation / Answer
worse and best case:
T(1) = c
T(n) = 2 T(n/2) + n
= 2 (2T(n/4) +n/2) + n
=4T(n/4)+n+n
=4T(n/4)+2n
=4 (2T(n/8) +n/4) + 2n
=8T(n/8)+n+2n
=8T(n/8)+3n
=2k T(n/2k) + kn
assum
n/2k = 1
n = 2k
log n = k
= nT(1) +n logn
= n+ n log n
T(n) = O(n log n)
True.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.