Computing randomized quick sort-s running time

Assignment Help Data Structure & Algorithms

Reference no: EM1354650

a. Suppose that all element values are equal. What would be randomized quick sort's running time in this case?

b. The PARTITION procedure returns index q such that each element of A[p .. q-1] is less than or equal to A[q] and each element of A[q+1 .. r] is greater than A[q]. Modify the PARTITION procedure to produce a procedure PARTITION'(A, p, r), which permutes the elements of A[p .. r] and returns two indices q and t, where p = q = t = r, such that

all elements of A[q .. t] are equal

each element of A[p .. q-1] is less than A[q], and each element of A[t+1 .. r] is greater than A[q]

Like PARTITION, your PARTITION' procedure should take ?(r-p) time.

c. Modify the RANDOMIZED-QUICKSORT procedure to call PAR- TITION' and name the new procedure RANDOMIZED-QUICKSORT'. Then modify the QUICKSORT procedure to produce a procedure QUICK- SORT'(p, r) that calls RANDOMIZED-PARTITION' and recurses only on partitions of elements not known to be equal to each other.

d. Using Quicksort, how would you adjust the analysis in Section 7.4.2 to avoid the assumption that all elements are distinct.

Reference no: EM1354650

Questions Cloud

Explain african americans in jersey whose maximum population : Explain African Americans in Jersey whose maximum population are up north in Essex County and the Hispanics whose population are in Hudson county

Corrected balance of accounts receivable : AIN is a financial planning firm which has an accounts receivable balance of $97,600. AIN uses the direct write-off method for bad debt. AIN determined that one of its clients which owes $7,300 has filed bankruptcy.

Explain how can hr staff contribute to the reduction : Explain how can HR staff contribute to the reduction of the need to administer discipline to employees within a company?

Reliability and validity of personality test : Please discuss the reliability and validity of personality test and what role (s) does factor analysis play in constructing personality tests? In your personal opinion are these test necessary?

Computing randomized quick sort-s running time : Suppose that all element values are equal. What would be randomized quick sort's running time in this case? Each element of A[p .. q-1] is less than A[q], and each element of A[t+1 .. r] is greater than A[q]

Question on economic analysis : Why do you think it will be an interesting focus for your economic analysis? What is the price of the stock? How many shares can you purchase with your $1000? To keep things simple, assume the brokerage fee is waived. This is just a virtual exercis..

Find the distance d which locates the point : A physics student in a hot air balloon ascends vertically at constant speed. suppose the following four forces that arise in this situation.

Describe organizational theory and design : Explain why might a company consider using an intranet rather than traditional management and executive information systems?

Explain patricia has a valid judgment against david : Explain Patricia has a valid judgment against David and which she now wishes to execute. David has no assets in the state where the judgment was entered.

User Account

All Pages