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$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
MERGE(A, p, q, r)
    n[1] = q - p + 1
    n[2] = r - q
    let L[1..n[1]] and R[1..n[2]] be new arrays
    for i = 1 to n[1]
        L[i] = A[p + i - 1]
    for j = 1 to n[2]
        R[j] = A[q + j]
    i = 1
    j = 1
    for k = p to r
        if i > n[1]
            A[k] = R[j]
            j = j + 1
        else if j > n[2]
            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) & \text{if } n = 2^k, \text{for } k > 1 \end{cases} $$

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

The base case is when $n = 2$, and we have $n\lg n = 2\lg 2 = 2 \cdot 1 = 2$.

For the inductive step, our inductive hypothesis is that $T(n / 2) = (n / 2)\lg(n / 2)$. Then

$$ \begin{aligned} T(n) & = 2T(n / 2) + n \\ & = 2(n / 2) \lg(n / 2) + n \\ & = n(\lg n - 1) + n \\ & = n\lg n - n + n \\ & = n\lg n, \end{aligned} $$

which completes the inductive proof for exact powers 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.

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

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

Although the exercise does not ask you to solve this recurrence, its solution is $T(n) = \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)$.

Procedure $\text{BINARY-SEARCH}$ takes a sorted array $A$, a value $v$, and a range $[low..high]$ of the array, in which we search for the value $v$. The procedure compares to the array entry at the midpoint of the range and decides to eliminate half the range from further consideration. We give both iterative and recursive versions, each of which returns either an index $i$ such that $A[i] = v$, or $\text{NIL}$ if no entry of $A[low..high]$ contains the value $v$. The initial call to either version should have the parameters $A$, $v$, $1$, $n$.

1
2
3
4
5
6
7
8
9
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
1
2
3
4
5
6
7
8
9
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)

Both procedures terminate the search unsuccessfully when the range is empty (i.e., $low > high$) and terminate it successfully if the value $v$ has been found. Based on the comparison of $v$ to the middle element in the searched range, the search continues with the range halved. The recurrence for these procedures is therefore $T(n) = T(n / 2) + \Theta(1)$, whose solution 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)$?

The while loop of lines 5–7 of procedure $\text{INSERTION-SORT}$ scans backward through the sorted array $A[1..j - 1]$ to find the appropriate place for $A[j]$. The hitch is that the loop not only searches for the proper place for $A[j]$, but that it also moves each of the array elements that are bigger than $A[j]$ one position to the right (line 6). These movements can take as much as $\Theta(j)$ time, which occurs when all the $j - 1$ elements preceding $A[j]$ are larger than $A[j]$. We can use binary search to improve the running time of the search to $\Theta(\lg j)$, but binary search will have no effect on the running time of moving the elements. Therefore, binary search alone cannot improve the worst-case running time of $\text{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$.

The following algorithm solves the problem:

  1. Sort the elements in $S$.
  2. Form the set $S' = \{z: z = x - y$ for some $y \in S\}$.
  3. Sort the elements in $S'$.
  4. Merge the two sorted sets $S$ and $S'$.
  5. There exist two elements in $S$ whose sum is exactly $x$ if and only if the same value appears in consecutive positions in the merged output.

To justify the claim in step 4, first observe that if any value appears twice in the merged output, it must appear in consecutive positions. Thus, we can restate the condition in step 5 as there exist two elements in $S$ whose sum is exactly $x$ if and only if the same value appears twice in the merged output.

Suppose that some value $w$ appears twice. Then $w$ appeared once in $S$ and once in $S'$. Because $w$ appeared in $S'$, there exists some $y \in S$ such that $w = x - y$, or $x = w + y$. Since $w \in S$, the elements $w$ and $y$ are in $S$ and sum to $x$.

Conversely, suppose that there are values $w, y \in S$ such that $w + y = x$. Then, since $x - y = w$, the value $w$ appears in $S'$. Thus, $w$ is in both $S$ and $S'$, and so it will appear twice in the merged output.

Steps 1 and 3 require $\Theta(n\lg n)$ steps. Steps 2, 4, 5, and 6 require $O(n)$ steps. Thus the overall running time is $O(n\lg n)$.

A reader submitted a simpler solution that also runs in $\Theta(n\lg n)$ time. First, sort the elements in $S$, taking $\Theta(n\lg n)$ time. Then, for each element $y$ in $S$, perform a binary search in $S$ for $x - y$. Each binary search takes $O(\lg n)$ time, and there are are most $n$ of them, and so the time for all the binary searches is $O(n\lg n)$. The overall running time is $\Theta(n\lg n)$.

Another reader pointed out that since $S$ is a set, if the value $x / 2$ appears in $S$, it appears in $S$ just once, and so $x / 2$ cannot be a solution.