Question: 2. Consider the following sorting algorithm. For simplicity, we'll assume the problem input size n is always a power of 2. COOLSORT(A[ 1 .. n]):

2. Consider the following sorting algorithm. For simplicity, we'll assume the problem input size n is always a power of 2. COOLSORT(A[ 1 .. n]): if n > 1 COOLSORT(A[1 .. n/2]) COOLSORT(A[n/2 + 1 .. n]) COOLMERGE(A[ 1 .. n]) COOLMERGE(A[ 1 .. n]): if n = 2 if A[ 1 ] > A[2] swap A[1] A[2] else for i - 1 to n/4 ((swap 2nd and 3rd quarters)) swap A[i + n/4] A[i + n/2] COOLMERGE(A[ 1 .. n/2]) ((recurse on left half)) COOLMERGE(A[n/2 + 1 .. n]) ((recurse on right half)) COOLMERGE(A[n/4 + 1 .. 3n/4]) ({recurse on middle half)) (a) (3 out of 10) Let C(n) be the running time for COOLMERGE(A[1 .. n]). State a recurrence definition for C(n). You do not have to solve the recurrence for this part of the problem. (b) (3 out of 10) What is the running time of COOLMERGE(A[1 .. n])? You should assume your solution to part (a) is correct. (c) (4 out of 10) What is the running time of COOLSORT(A[1 .. n])? You should assume your solution to part (b) is correct

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer

Step: 1 Unlock blur-text-image

Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock

Step: 3 Unlock

Students Have Also Explored These Related Mathematics Questions!

Prove by induction that WEIRDSORT correctly sorts any input array (of size a power of two). ( Hint : Formulate a claim for what STRAIGHTEN is supposed to accomplish, and prove it.) Assume that n is a...

Assume that n is a power of two. Consider the following sorting algorithm: SLOWSORT(A[1..n]) 1: if n > 1 then 2: SLOWSORT(A[1 .. n 2 ]) 3: SLOWSORT(A[ n 2 +1 .. n]) 4: GATHER(A[1 .. n]) 5: end if...

Problem (page limit: 3 pages) A ssume that n is a power of two. Consider the following sorting algorithm: STRAIGHTEN(A1 T) : if 2 then ifA[2]A111 then swap A A2 3: 4: end if 5: else WEIRDSORT(A1..T...

Prove by induction that WEIRDSORT correctly sorts any input array (of size a power of two). Assume that n is a power of two. Consider the following sorting algorithm: STRAIGHTEN(A[1 .. T) 1: if n-2...

Problem 4 (30 points) Consider the following cruel and unusual sorting algorithm. CRUEL(A[1..n]): if n > 1 CRUEL(A[1.. n/2]) CRUEL(A[n/2+1..n]) UNUSUAL(A[1.. n]) UNUSUAL(A[1..n]); if n=2 if A[1] >...

Please code in Python. I'll upload for a completed response. Thanks. This is the completed information. data.txt file could be just a single line of integers. Consider the following pseudocode for a...

Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1, . . . , n} written in some arbitrary order (this means that A is a permutation of the set {1, . . . , n}). Our goal in this...

2. Consider the following data set consisting of four points: X1 = - [8], --[1].-= []. - [ ] Plot these points. We want to split this set to two classes. (a) Suppose you start the K-means algorithm...

Note. When you are asked about the time complexity of an algorithm, the best (tightest) characterization of the order of the time complexity is implied. For example, it is correct to say that the...

Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,..., n} written in some arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem...

XYZ stock is currently trading at $50 per share. We ask our favorite trading desk to price a bunch of 6-month options on XYZ: 4 puts and 4 calls. The table above gives the information. For each...

1:0A I %00 A 3 points Find the angle between the vectors a and b , where a =i+ 2j k and b -i+j-2k. 30 -30 60 -60 Consider the point A,B,C,D 3 points where coordinates are respectively...

Ariana owns 5 0 shares of stock in Ban Ray Enterprises. Ariana bought the stock when it was first issued, and the offering was required to be registered with the Securities and Exchange Commission (...

10. DETAILS Let f(x) = 4 2x + 1. Part 1 - Graph Graph y= f(x). -10 -5 y 10 5 -5 -10 y 10 5 X 5 10 -10 -5 y 10 5 -5 -10 10 y 5 MY NOTES ASK YOUR TEACHER X 5 10 X -10 -5 5 10 -10 -5 5 -5 -5 - Part 2 -...