[Algo] Exercise 8.2

Exercise 8.2-2
Prove that COUNTING-SORT is stable.
solution: see solution 8.2-3.

Exercise 8.2-3
Suppose that the for loop header in line 9 of the COUNTING-SORT procedure is rewritten as
9  for j = 1 to length[A]
Show that the algorithm still works properly. Is the modified algorithm stable?
solution:
The modified algorithm is not stable, though it works properly. No matter how j runs from 1 or from length[A], the correctness of the algorithm will not be affected. Because C[0..k] is well established. When index j is running from 1 to length[A], the element which is taken from A earlier is put in B at later index. It violates the stable property.

Exercise 8.2-4
Describe an algorithm that, given $n$ integers in the range 0 to $k$, preprocesses its input and then answers any query about how many of the n integers fall into a range [a..b] in $O(1)$ time. Your algorithm should use $\Theta(n + k)$ preprocessing time.
solution:
We can design an algorithm that is according to the COUNTING-SORT algorithm. Then the answer to the query is determined by $C[b] - C[a-1]$ in $O(1)$ running time. (We set $C[-1] = 0$.)