Register

Cormen Edition 3 Exercise 7.4 Question 6 (Page No. 185)

1,191 views
1 votes
1 votes

Consider modifying the PARTITION procedure by randomly picking three elements from the array $A$ and partitioning about their median (the middle value of the three elements). Approximate the probability of getting at worst a $\alpha$-to-$(1-\alpha)$ split, as a function of $\alpha$ in the range $0<\alpha<1$.

User Avatar

1 Answer

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

1 votes
1 votes
1 answer
1
akash.dinkar12 asked Jun 27, 2019
424 views
Cormen Edition 3 Exercise 7.2 Question 6 (Page No. 179)
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $1-\alpha$ to $\alpha$.
Argue that for any constant $0<\alpha\leq 1/2$, the probability is approximately $1-2\alpha$ that on a random input array, PARTITION produces a split more balanced than $...
User Avatar
0 votes
0 votes
0 answers
3
akash.dinkar12 asked Jun 27, 2019
328 views
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
Show that when all elements are distinct, the best-case running time of HEAPSORT is $\Omega(n\lg\ n)$.
User Avatar
Link Copied!