[Algo] Exercise 8.4

Exercise 8.4-2
What is the worst-case running time for the bucket-sort algorithm? What simple change to the algorithm preserves its linear expected running time and makes its worst-case running time $O(n \lg n)$?
solution:
The worst-case is that all elements are distributed in the same bucket, consequently, $O(n^2)$ running time is required to perform insertion sort. A simple change is to replace insertion sort with any $O(n \lg n)$ sorting algorithm, such as merge sort, quicksort, etc. to improve running time from $O(n^2)$ to $O(n \lg n)$.


Exercise 8.4-3
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]$?
solution:
$E[X^2] = 0 \times 1/4 + 1^2 \times 1/2 + 2^2 \times 1/4 = 1/2 + 1 = 3/2$
$E^2[X] = (0 \times 1/4 + 1 \times 1/2 + 2 \times 1/4)^2 = (1/2 + 1/2)^2 = 1$


Exercise 8.4-4
We are given n points in the unit circle, $p_i = (x_i, y_i)$, such that $0 < x_i^2 + y_i^2 \leq 1$ for $i = 1, 2, \ldots, 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 a $\Theta(n)$ expected-time algorithm to sort the n points by their distances $d = \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.)
solution:
Note that the expected number of points residing in an area is proportional to the size of the area. To satisfy the assumption of BUCKET-SORT, we have to make the interval $(0, 1]$ split in a proper way. Consider a distance $d$ between $a$ and $b$, where $0 \leq a < d < b \leq 1$. The area is $\pi(b^2 - a^2)$. Dividing $(0, 1]$ into n equal-sized intervals does not help a lot. It does not mean we divide a unit circle into n areas evenly. To achieve our goal, we divide $(0, 1]$ into $<0, \sqrt{1/n}, \sqrt{2/n}, \ldots, \sqrt{n-1/n}, 1>$ intervals instead. In the context of such dividing, we can see that the $\pi(1/n) = \pi((\sqrt{2/n})^2 - (\sqrt{1/n})^2) = \cdots = \pi(1 - (\sqrt{n-1/n})^2)$. Because of the equal size of area, we'll expect that each bucket contain roughly the same points.


Exercise 8.4-5
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) = \mbox{Pr}\{X \leq x\}$. Suppose that a list of $n$ random variables $X_1, X_2, \ldots, X_n$ is drawn from a continuous probability function $P$ that is computable in $O(1)$ time. Show how to sort these numbers in linear expected time.
solution:
$P(x)$ is defined in a manner of cumulative distribution function. By probability integral transform, we know that $P(X_i)$ has a uniform distribution, where $i = 1, 2, \ldots, n$. As a result, we can sort these transformed numbers by BUCKET-SORT in linear time.