1.  If t=4, a node is saturated if it contains 2t-1 = 7 elements.
Inserting FSQKCLJTVWMRNPABXYDZE in that order:

We can add the first 7 letters without causing a split,
giving a single node with

CFHKLQS

Now adding T causes a split:

    .K.
   /   \
CFH     LQST

We can add VWM without any splits:

    .K.
   /   \
CFH     LMQSTVW

Then adding R causes a split:

    .K.S.
   /  |  \
CFH  LMQR TVW

The remaining 9 letters can be added with no more splits.
The final configuration is

         .K.S.
        /  |  \
       /   |   \
ABCDEFH  LMNPQR TVWXYZ

2. WLOG, consider two elements with the same key k that are in array
locations i and j, i < j, with no element of value k between the two.
To show stability, we need to show that in the output array the
location of k_i is less than the location of k_j.  The only lines of
counting sort that affect the output are:

for j = length(A) downto 1 do
  B[C[A[j]]] = A[j];
  C[A[j]] -= 1;

Here C is the array that (at this point) stored the location where a
value should go -- i.e. value k should go to location C[k] in the
output.  When this code is run and comes to the two elements k_i and
k_j, since j > i, it will process k_j first.  k_j will go in some
location l = C[k], and we then decrement C[k].  The next time we
access C[k] is for k_i (because there are no intervening k values),
and we will place k_i in C[k] = l-1.  Since l-1 < l, we have not
swapped two elements of the same value, so CountingSort is stable.

3. If the hashing does badly, all the items will be stored in one bucket. 
Thus we would be doing insertion sort on N items, for a worst case 
running time of O(n^2).

Switching the algorithm to use a guaranteed O(n log n) sorting algorithm 
will improve our performance to O(n log n). Heap Sort and Merge Sort both 
work in this case.

4. We largely depend on the solution of problem 10 in prelim. Recall that it enables us to
have a data structure with insert/count operation in O(log n) time, where count takes on
a node and returns the number of elements less than it.

We build two balanced trees, one of which stores all lower endpoints of input intervals
and the other upper endpoints(call them L and R, respectively), and augment them as we
did in prelim. insert(x,y) is done by inserting x in L and y in R using insert function
in prelim problem. Now suppose two functions both taking argument T(tree) and x(number),
where

- countLessThan(T,x) returns the number of nodes in T less than x
- countLargerThan(T,x) returns the number of nodes in T larger than x

countLessThan(T,x) is exactly the same as count(x) in prelim. countLargerThan can be
easily implemented intuitively in a symmetric way. Then,

count(x) = (n - countLargerThan(L,x)) - countLessThan(R,x)

where n is the number of nodes in each tree(assuming we are keeping it).

5.  Recall the radix-sort, where we sort a number by sorting its colums
using a stable sort. We shall use this idea. 

I. If the number is in the range of 1 to n^2, then it takes 2 log (base
2) n bits to represent the number. We can radix-sort the first log (base
2) n bits using counting sort, as the range of the numbers is 1 to n.
(Note that counting sort is stable.) We can then use counting sort again
on the second log (base 2) n bits, arriving at sorted output. The time
for this is simply 2 counting sorts, or O(2n) = O(n)

OR

II. Convert all numbers to base n+1, thus all numbers have only 2
digits. (Assume that this conversion process takes constant time per
number, thus O(n) for all your input numbers.) Then run radix sort,
using counting sort as the stable sort inside. Running time = O(dn+kd)
where d is # of digits  k is the range of each digit. d = 2; k = n
plugging in these values, you get O(2n+2n) = O(n).