CLRS 2.1 solutions

2.1-1

Using Figure 2.2 as a model, illustrate the operation of Insertion-Sort on the array \(A = \langle 31, 41, 59, 26, 41, 58 \rangle\).

Sol’n

For the first and second step, \(41\) and \(59\), no change is needed. The third step, at \(26\), we move that to front and move earlier elements one to right. Etc, and so the sequence of events is,

\[ \begin{align*} A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ & \vdots \\ & \to \langle 31, 41, 59, 26, 41, 58 \rangle \\ & \to \langle 26, 31, 41, 59, 41, 58 \rangle \\ & \to \langle 26, 31, 41, 41, 59, 58 \rangle \\ & \to \langle 26, 31, 41, 41, 58, 59 \rangle. \end{align*} \]

2.1-2

Rewrite the Insertion-Sort procedure to sort into nonincreasing instead of nondecreasing order.

Sol’n

Simply invert the inequality in \(A[i] > \text{key}\).

2.1-3

Consider the searching problem:

Input: A sequence of \(n\) numbers \(A = \langle a_1, a_2, \dots, a_n \rangle\) and a value \(\nu.\)

Output: An index \(i\) such that \(\nu = A[i]\) or the special value NIL if \(\nu\) does not appear in \(A.\)

Write pseudocode for linear search, which scans through the sequence, looking for \(\nu\). Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Sol’n

1  for i = 1 to A.length
2      if A[i] = nu
3          return i
4  return NIL

Proof:

Loop invariant:

At the start of each iteration of the for loop of lines 1-3, there is no \(j < i\) such that \(A[j] = \nu.\)

Initialization:

At the beginning of the first iteration, we have \(i = 1,\) so there is no \(j < i\) such that \(A[j] = \nu.\)

Maintenance:

We fix \(i\) and assume there is no \(j < i\) such that \(A[j] = \nu.\)

If \(A[i] = \nu,\) then we return a value, so then there are no more iterations, so the property is preserved.

If \(A[i] \ne \nu,\) then there is no \(j < i + 1\) such that \(A[j] = \nu,\) which is the desired property for the next step.

Termination:

The loop terminates either for \(i = A.length + 1\), or if ever we encounter \(A[i] = \nu.\)

In the first case, then there is no \(1 \le j \le A.length\) such that \(A[j] = \nu,\) and we are correctly returning NIL

In the second case, if we encounter some \(i\) such that \(A[i] = \nu,\) we are correctly returning \(i.\)

2.1-4

Consider the problem of adding two \(n\)-bit binary integers, stored in two \(n\)-element arrays \(A\) and \(B\). The sum of the two integers should be stored in binary form in an \((n + 1)\)-element array \(C.\) State the problem formally and write pseudocode for adding the two integers.

Sol’n

Input: Two \(n\)-bit integers \(A\) and \(B.\)

Output: Their \((n + 1)\)-bit sum, \(C = A + B.\)

C[n + 1] = 0
for i = n downto 1
    C[i + 1] = C[i + 1] + A[i] + B[i]
    if C[i + 1] > 1
        C[i + 1] = C[i + 1] - 2
        C[i] = 1
    else
        C[i] = 0