Skip to content

2.3 Designing algorithms

2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on the array $A = \langle 3, 41, 52, 26, 38, 57, 9, 49 \rangle$.

$$[3] \quad [41] \quad [52] \quad [26] \quad [38] \quad [57] \quad [9] \quad [49]$$

$$\downarrow$$

$$[3|41] \quad [26|52] \quad [38|57] \quad [9|49]$$

$$\downarrow$$

$$[3|26|41|52] \quad [9|38|49|57]$$

$$\downarrow$$

$$[3|9|26|38|41|49|52|57]$$

2.3-2

Rewrite the $\text{MERGE}$ procedure so that it does not use sentinels, instead stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.

MERGE(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q
    let L[1..n1] and R[1..n2] be new arrays
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    i = 1
    j = 1
    for k = p to r
        if i > n1
            A[k] = R[j]
            j = j + 1
        else if j > n2
            A[k] = L[i]
            i = i + 1
        else if L[i] ≤ R[j]
            A[k] = L[i]
            i = i + 1
        else
            A[k] = R[j]
            j = j + 1

2.3-3

Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence

$$ T(n) = \begin{cases} 2 & \text{if } n = 2, \\ 2T(n / 2) + n & \text{if } n = 2^k, \text{for } k > 1 \end{cases} $$

is $T(n) = n\lg n$.

  • Base case

For $n = 2^1$, $T(n) = 2\lg 2 = 2$.

  • Suppose $n = 2^k$, $T(n) = n\lg n = 2^k \lg 2^k = 2^kk$.

For $n = 2^{k + 1}$,

$$ \begin{aligned} T(n) & = 2T(2^{k + 1} / 2) + 2^{k + 1} \\ & = 2T(2^k) + 2^{k + 1} \\ & = 2 \cdot 2^kk + 2^{k + 1} \\ & = 2^{k + 1}(k + 1) \\ & = 2^{k + 1} \lg 2^{k + 1} \\ & = n\lg n. \end{aligned} $$

By P.M.I., $T(n) = n\lg n$, when $n$ is an exact power of $2$.

2.3-4

We can express insertion sort as a recursive procedure as follows. In order to sort $A[1..n]$, we recursively sort $A[1..n - 1]$ and then insert $A[n]$ into the sorted array $A[1..n - 1]$. Write a recurrence for the running time of this recursive version of insertion sort.

It takes $\Theta(n)$ time in the worst case to insert $A[n]$ into the sorted array $A[1..n - 1]$. Therefore, the recurrence

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\ T(n - 1) + \Theta(n) & \text{if } n > 1. \end{cases} $$

The solution of the recurrence is $\Theta(n^2)$.

2.3-5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta(\lg n)$.

  • Iterative:
ITERATIVE-BINARY-SEARCH(A, v, low, high)
    while low ≤ high
        mid = floor((low + high) / 2)
        if v == A[mid]
            return mid
        else if v > A[mid]
            low = mid + 1
        else high = mid - 1
    return NIL
  • Recursive:
RECURSIVE-BINARY-SEARCH(A, v, low, high)
    if low > high
        return NIL
    mid = floor((low + high) / 2)
    if v == A[mid]
        return mid
    else if v > A[mid]
        return RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
    else return RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)

Each time we do the comparison of $v$ with the middle element, the search range continues with range halved.

The recurrence

$$ T(n) = \begin{cases} \Theta(1) & \text{if } n = 1, \\ T(n / 2) + \Theta(1) & \text{if } n > 1. \end{cases} $$

The solution of the recurrence is $T(n) = \Theta(\lg n)$.

2.3-6

Observe that the while loop of lines 5–7 of the $\text{INSERTION-SORT}$ procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray $A[i..j - 1]$. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to $\Theta(n\lg n)$?

Each time the while loop of lines 5-7 of $\text{INSERTION-SORT}$ scans backward through the sorted array $A[1..j - 1]$. The loop not only searches for the proper place for $A[j]$, but it also moves each of the array elements that are bigger than $A[j]$ one position to the right (line 6). These movements takes $\Theta(j)$ time, which occurs when all the $j - 1$ elements preceding $A[j]$ are larger than $A[j]$. The running time of using binary search to search is $\Theta(\lg j)$, which is still dominated by the running time of moving element $\Theta(j)$.

Therefore, we can't improve the overrall worst-case running time of insertion sort to $\Theta(n\lg n)$.

2.3-7 $\star$

Describe a $\Theta(n\lg n)$-time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.

First, sort $S$, which takes $\Theta(n\lg n)$. Then, for each element $s_i$ in $S$, $i = 1, \dots, n$, search $A[i + 1..n]$ for $s_i' = x - s_i$ by binary search, which takes $\Theta(\lg n)$.

  • If $s_i'$ is found, return its position;
  • otherwise, continue for next iteration.

The time complexity of the algorithm is $\Theta(n\lg n) + n \cdot \Theta(\lg n) = \Theta(n\lg n)$.