2.1-1

Using Figure 2.2 as a model, illustrate the operation of $\text{INSERTION-SORT}$ on the array $A = \langle 31, 41, 59, 26, 41, 58 \rangle$.

$$ \begin{aligned} A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 31, 41, 59, 26, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 59, 41, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 59, 58 \rangle \\ A & = \langle 26, 31, 41, 41, 58, 59 \rangle \end{aligned} $$

2.1-2

Rewrite the $\text{INSERTION-SORT}$ procedure to sort into nonincreasing instead of nondecreasing order.

1
2
3
4
5
6
7
8

INSERTION-SORT(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] < key
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key

2.1-3

Consider the searching problem:

Input: A sequence of $n$ numbers $A = \langle a_1, a_2, \ldots, a_n \rangle$ and a value $v$.

Output: An index $i$ such that $v = A[i]$ or the special value $\text{NIL}$ if $v$ does not appear in $A$.

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

1
2
3
4
5

LINEAR-SEARCH(A, v)
    for i = 1 to A.length
       if A[i] == v
            return i
    return NIL

Loop invariant: At the start of each iteration of the for loop, the subarray $A[1..i - 1]$ consists of elements that are different than $v$.

Initialization: Initially the subarray is the empty array, so the prove is trivial.

Maintenance: On each step, we know that $A[1..i - 1]$ does not contain $v$. We compare it with $A[i]$. If they are the same, we return $i$, which is a correct result. Otherwise, we continue to the next step. We have already insured that $A[1..i - 1]$ does not contain $v$ and that $A[i]$ is different from $v$, so this step preserves the invariant.

Termination: The loop terminates when $i > A.length$. Since $i$ increases by $1$ and $i > A.length$, we know that all the elements in $A$ have been checked and it has been found that $v$ is not among them. Thus, we return $\text{NIL}$.

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.

Input: An array of booleans $A = \langle a_1, a_2, \ldots, a_n \rangle$ and an array of booleans $B = \langle b_1, b_2, \ldots, b_n \rangle$, each representing an integer stored in binary format (each digit is a number, either $0$ or $1$, least-significant digit first) and each of length $n$.

Output: An array $C = \langle c_1, c_2, \ldots, c_{n + 1} \rangle$ such that $C' = A' + B'$ where $A'$, $B'$ and $C'$ are the integers, represented by $A$, $B$ and $C$.

1
2
3
4
5
6
7
8

ADD-BINARY(A, B)
    C = new integer[A.length + 1]
    carry = 0
    for i = 1 to A.length
        C[i] = (A[i] + B[i] + carry) % 2  // remainder
        carry = (A[i] + B[i] + carry) / 2 // quotient
    C[i] = carry
    return C