CLRS 2.3 solutions

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

Sol’n

<<<3, 41>, <52, 26>>, <<38, 57>, <9, 49>>>
<<<3, 41>, <26, 52>>, <<38, 57>, <9, 49>>>
<<3, <41>, <26, 52>>, <9, <38, 57>, <49>>>
<<3, 26, <41>, <52>>, <9, 38, <57>, <49>>>
<<3, 26, 41, <52>>, <9, 38, 49, <57>>>
<<3, 26, 41, 52>, <9, 38, 49, 57>>
<3, <26, 41, 52>, <9, 38, 49, 57>>
<3, 9, <26, 41, 52>, <38, 49, 57>>
<3, 9, 26, <41, 52>, <38, 49, 57>>
<3, 9, 26, 38, <41, 52>, <49, 57>>
<3, 9, 26, 38, 41, <52>, <49, 57>>
<3, 9, 26, 38, 41, 49, <52>, <57>>
<3, 9, 26, 38, 41, 49, 52, <57>>
<3, 9, 26, 38, 41, 49, 52, 57>

2.3-2

Rewrite the 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.

Sol’n

MERGE(A, p, q, r)
01  n1 = q - p + 1
02  n2 = r - q
03  let L[1..n1] and R[1..n2] be new arrays
04  for i = 1 to n1
05    L[i] = A[p + i + 1]
06  for j = 1 to n2
07    R[j] = A[q + j]
08  i = 1
09  j = 1
10  k = p
11  while i <= n1 and j <= n2
12    if L[i] <= R[j]
13      A[k] = L[i]
14      i = i + 1
15    else A[k] = R[j]
16      j = j + 1
17    k = k + 1
18  while k <= r
19    if i <= n1
20      A[k] = L[i]
21      i = i + 1
22    else A[k] = R[j]
23      j = j + 1
24    k = k + 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$, for $k > 1$.} \\ \end{cases} \]

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

Sol’n

Base case:

For $n = 2,$ we have $T(2) = 2$ and $2 \lg 2 = 2,$ as desired.

Inductive step:

We assume $T(n) = n \lg n,$ and show that

\[ T(2n) = 2n \lg (2n). \]

Expanding the left side, we have

\[ \begin{align*} T(2n) & = 2T(n) + 2n \\ & = 2n \lg n + 2n. \end{align*} \]

Expanding the right side, we have

\[ \begin{align*} 2n \lg (2n) & = 2n \left(\lg(n) + \lg(2)\right) \\ & = 2n \lg n + 2n, \end{align*} \]

as desired.

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.

Sol’n

\[ \begin{align*} T(n) = \begin{cases} 1 & \text{if } n = 1, \\ T(n - 1) + \lg(n) & \text{o.w.} \end{cases} \end{align*} \]

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

Sol’n

rough draft:

binary_search(A, p, q, nu)
01  if A[p] = nu
04    return p
03  if p = q
04    return nil
02  mid = ⌊(q - p) / 2⌋
03  if nu <= A[mid]
04    binary_search(A, mid, q, nu)
05  else 
06    binary_search(A, p, mid, nu)

(induction on $k = ⌈\lg n⌉?$)

2.3-6

Observe that the while loop of lines 5–7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray $A[1..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)?$

Sol’n

Yes, as then each scan backwards over $k$ elements would take $⌈\lg k⌉,$ and so we have approximately

\[ \begin{align*} \sum_{k = 1}^n \lg k \le n \lg n. \end{align*} \]

This just gives upper bound $O(n \lg n),$ I wasn’t sure how to describe the lower bound as $n \lg n.$

2.3-7 *

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

Sol’n

rough draft:

has_exact_sum(A, x)
n = A.length
for i = 1 to n
  result = binary_search(A, i, n, x)
  if result ≠ NIL
    return result
return nil