Cormen Edition 3 Exercise 8.4 Question 4 (Page No. 204)

97 views

We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2,….,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in any region of the circle is proportional to the area of that region. Design an algorithm with an average-case running time of $\Theta(n)$ to sort the $n$ points by their distances $d_i=\sqrt{x_i^2+y_i^2}$ from the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)

Related questions

1
132 views
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n\ lg\ n)$?
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i – 0 to n – 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n – 1 8 sort list B[i] with insertion sort 9 concatenate the lists B[0] , B[1] , ….,B[n-1] together in order illustrate the operation of BUCKET-SORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$