Chapter 8

Exercise 8.1-1

The smallest possible depth of a leaf in a decision tree for a comparison sort is $n-1$, where $n$ is the number of elements to sort. This is equivalent to the best-case number of comparisons needed to sort $n$ elements.

Exercise 8.1-2

Available in the latest revision of the IM.

Exercise 8.1-3

Available in the latest revision of the IM.

Exercise 8.1-4

Available in the latest revision of the IM.

Exercise 8.2-1

// The array A and the auxiliary array C after line 5.
A[1:11]=[6,0,2,0,1,3,4,6,1,3,2]
C[0:6]=[2,2,2,2,1,0,2]

// The array C after line 8.
C[0:6]=[2,4,6,8,9,9,11]

// The output array B and the auxiliary array C after one, two, and 
// three iterations of the loop in lines 11–13, respectively. 
// Only the non-X elements of array B have been filled in.
B[1:11]=[X,X,X,X,X,2,X,X,X,X,X]
C[0:6]=[2,4,5,8,9,9,11]

B[1:11]=[X,X,X,X,X,2,X,3,X,X,X]
C[0:6]=[2,4,5,7,9,9,11]

B[1:11]=[X,X,X,1,X,2,X,3,X,X,X]
C[0:6]=[2,3,5,7,9,9,11]

// The final sorted output array B.
B[1:11]=[0,0,1,1,2,2,3,3,4,6,6]

Exercise 8.2-2

Consider the case where positions $i < j$ each contain the same value $v$. Focusing on lines 11 through 13 of Counting-Sort, which fill the output array, we observe that the loop will process $A[j]$ prior to $A[i]$. In this situation, $A[j]$ is placed into position $p = C[v]$ of $B$. Following this placement, line 13 decrements $C[v]$, ensuring that when the loop later processes $A[i]$, the value of $C[v]$ is less than $p$. Consequently, $A[i]$ is inserted into an earlier location in the output array, thereby demonstrating the stability of the algorithm.

Exercise 8.2-3

Available in the latest revision of the IM.

The pseudocode in the IM needlessly wastes memory by introducing a new array $L$. The array $C$ can be updated in-place such that $C[i]$ contains the index of the first element of $A$ with value $i$. The following snippet does the job: p = 1 for i = 1 to k q = C[i] C[i] = p + C[i-1] p = q C[0] = 1

Exercise 8.2-4

Available in the latest revision of the IM.

Exercise 8.2-5

Available in the latest revision of the IM.

Exercise 8.2-6

Available in the latest revision of the IM.

Exercise 8.2-7

Available in the latest revision of the IM.

Exercise 8.3-1

COW   SEA   TAB   BAR
DOG   TEA   BAR   BIG
SEA   MOB   EAR   BOX
RUG   TAB   TAR   COW
ROW   DOG   SEA   DIG
MOB   RUG   TEA   DOG
BOX   DIG   DIG   EAR
TAB   BIG   BIG   FOX
BAR   BAR   MOB   MOB
EAR   EAR   DOG   NOW
TAR   TAR   COW   ROW
DIG   COW   ROW   RUG
BIG   ROW   NOW   SEA
TEA   NOW   BOX   TAB
NOW   BOX   FOX   TAR
FOX   FOX   RUG   TEA

Exercise 8.3-2

Available in the latest revision of the IM.

Exercise 8.3-3

Available in the latest revision of the IM.

Exercise 8.3-4

Available in the latest revision of the IM.

Exercise 8.3-5

Available in the latest revision of the IM.

Exercise 8.3-6

Each sorting pass corresponds to feeding a pile of cards into the machine to be sorted into 10 piles based on the current digit. The total number of sorting passes in the worst-case is $S(d)=\sum_{i=0}^{d-1} 10^i=\frac{10^d-1}{9}$.

The total number of intermediate piles produced during the whole process, that an operator needs to keep track of, is commensurate with the number of sorting passes. The cards in 9 of the 10 bins must be put aside to sort each of the bins except when sorting on the least significant digit position (there are $10^{d-1}$ such sessions). We have $P(d)=9(S(d)-10^{d-1})=10^{d-1}-1$.

On the other hand, if we are interested in to estimate the space needed for storing those intermediate piles at any given moment, then we have $P(d)=9(d-1)+1$, where +1 designates the pile being placed into a machine for sorting.

Exercise 8.4-1

Available in the latest revision of the IM.

Exercise 8.4-2

Available in the latest revision of the IM.

Exercise 8.4-3

Available in the latest revision of the IM.

Exercise 8.4-4

The idea is to split buckets into 2 layers. This works, since $n>10$ implies that $y_i/n<\lfloor10x_i\rfloor/10$. Below is the implementation of the modified bucket sort in Python 3. For the sake of simplicity, we skip corner cases associated with rounding errors.

def modified_bucket_sort(a):
    n = len(a)
    
    # Step 1: Create 10 main buckets.
    b = [[] for _ in range(10)]
    for num in a:
        b[int(num * 10)].append(num)

    # Step 2: Process each main bucket.
    sorted_a = []
    for i in range(10):
        if b[i] is None:
            continue
        # Create n sub-buckets for the current main bucket.
        c = [[] for _ in range(n)]
        for num in b[i]:
            y = n * (num - i / 10)
            c[int(y * n)].append(num)
        # Concatenate all sorted sub-buckets of the current main bucket.
        for j in range(n):
            # Each sub-bucket is expected to have O(1) elements.
            sorted_a.extend(sorted(c[j]))
    return sorted_a

Exercise 8.4-5

Available in the latest revision of the IM.

Ring 0 will be empty, so $1 \le i= \lceil nd_i^2 \rceil \le n$.

Exercise 8.4-6

The probability distribution function defined in the book is also known as the cumulative distribution function (CDF). The solution below leverages the probability integral transform theory. The algorithm has two major steps.

1

Initialize

Create $n+1$ buckets whose bounds are $(P^{-1}((i-1)/n), P^{-1}(i/n)]$ for $i=1,2,\dots,n$. Bucket 0 contains only $X=0$. Observe that buckets may have different sizes, as in Exercise 8.4-5, but "encompass" the same probability range. For $i=1,2,\dots,n$ place $X_i$ into bucket $\lfloor P(X_i)n\rfloor$. This stage requires $O(n)$ time.

2

Employ Bucket Sort

Use bucket sort from the book to sort the random variables $X_i$.

The fact that $Y_i=P(X_i)$ has a uniform distribution over $[0,1]$ ensures that each bucket's expected size is $O(1)$.

Problem 8-1

Available in the latest revision of the IM.

Problem 8-2

Available in the latest revision of the IM.

Problem 8-3

Available in the latest revision of the IM.

Problem 8-4

Available in the latest revision of the IM.

Problem 8-5

a.

It is equivalent to classical sorting in ascending order.

b.

1,3,2,4,6,5,7,9,8,10

c.

We first prove the "only if" direction. For all $i=1,2,\dots,n-k$ we have

$$\begin{align*} \frac{\sum_{j=i}^{i+k-1}A[j]}{k} &\le \frac{\sum_{j=i+1}^{i+k}A[j]}{k} \\ \sum_{j=i}^{i+k-1}A[j] &\le \sum_{j=i+1}^{i+k}A[j] && \text{(eliminating $k$ from both sides)} \\ A[i] &\le A[i+k] && \text{(cancelling equal terms on both sides)} \end{align*}$$

The "if" direction is simply an inverse of the previous steps.

d.

By part (c) we can split the input numbers into k independent chains and sort them separately. Each chain has $n/k$ elements. For example, the first chain begins as $A[1],A[1+k],A[1+2k],...$ The time to sort a chain is $O((n/k) \lg (n/k))$ using heap sort or merge sort. The total time for all $k$ chains is$O(n\lg(n/k))$.

e.

Following the hint from the book, we apply the $k$-way merge algorithm, since a $k$-sorted array can be regarded as having $k$ sorted lists, that need to be combined (merged) into one sorted output.

f.

By part (d) along with the lower bound on comparison sorts, $k$-sorting an $n$-element array requires $\Theta(n\lg(n/k))$ time. When $k$ is a constant this entails a lower bound of $\Omega(n\lg n)$.

Problem 8-6

a.

This boils down to counting in how many ways we can pick $n$ items out of $2n$ items. Observe that once we select the first batch of $n$ numbers the second one is automatically determined. We have (see Exercise C.1-13)

$$\binom{2n}{n}=\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n))$$

b.

The following inequalities must hold, where $l$ is the number of leaves in a decision tree of height $h$.

$$\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n)) \le l \le 2^h$$

Taking logarithms on both sides we get

$$\begin{align*} h &\ge \lg \left({\cfrac {2^{2n}}{\sqrt{\pi n}}(1+O'(1/n))}\right) \\ &= \lg 2^{2n} - \lg \sqrt{\pi n} + \lg (1+O'(1/n)) \\ &= 2n-o(n) \end{align*}$$

c.

Suppose $a_i \neq b_j$. We know that the inequalities below are all satisfied, since $a_i$ and $b_j$ are from different sorted lists and they are consecutive in the sorted order.

$$a_{i-1} < a_i ,b_j < a_{i+1} \\ b_{j-1} < a_i ,b_j < b_{j+1}$$

We could exchange $a_i$ and $b_j$ without violating any of the constraints above. No matter how many other comparisons are made, none of them can add any new information about the relative order of $a_i$ and $b_j$. Therefore, $a_i$ and $b_j$ must be compared.

d.

The worst-case number of comparisons happen when elements are taken in alternating manner from sublists during the merge operation, hence consecutive elements in the sorted order are from different lists. By part (c) they must be compared and we have $2n-1$ such pairs.

Problem 8-7

Available in the latest revision of the IM.