2.1 Insertion sort

2.1-1

Using Figure 2.2 as a model, illustrate the operation of $\text{I\scriptsize NSERTION-\normalsize S\scriptsize ORT}$ on an array initially containing the sequence $\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

Consider the procedure $\text{S\scriptsize UM-\normalsize A\scriptsize RRAY}$ on the facing page. It computes the sum of the $n$ numbers in array $A[1:n]$. State a loop invariant for this procedure, and use its initialization, maintenance, and termination properties to show that the $\text{S\scriptsize UM-\normalsize A\scriptsize RRAY}$ procedure returns the sum of the numbers in $A[1:n]$.

Let’s state the loop invariant as follows: At the start of each iteration of the $\textbf{for}$ loop of lines 2-4, the $sum$ holds the total value of subarray $A[1:i-1]$.

• Initialization: Before the first iteration, $i=1$, and $A[1:i-1]$ gives us an empty array whose sum adds up to $0$.
• Maintenance: In each iteration, $A[i]$ joins the subarray $A[1:i-1]$. Therefore, the total value also increases by the value of $A[i]$. Given that the loop invariant is satisfied before the start of each iteration, adding $sum$ with the value of $A[i]$ ensures the loop invariant is true after each iteration.
• Termination: The loop variable $i$ starts at $1$ and increases by $1$ in each iteration, until exceeding $n$. Therefore, the loop will stop at $i=n+1$. At this point, $sum$ holds the total value of $A[1:i-1]=A[1:n]$. Hence, the algorithm is correct.

2.1-3

Rewrite the $\text{I\scriptsize NSERTION-\normalsize S\scriptsize ORT}$ procedure to sort into monotonically decreasing instead of monotonically increasing order.

Replace $A[j] > key$ in line 5 by $A[j] < key$ will do.

2.1-4

Consider the searching problem:

Input: A sequence of $n$ numbers $\langle a_1, a_2, \ldots, a_n \rangle$ stored in array $A[1:n]$ and a value $x$.

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

Write pseudocode for linear search, which scans through the array from beginning to end, looking for $x$. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

\begin{codebox}
    \Procname{$\proc{Linear-Search}(A, n, x)$}
    \li \For $i \gets 1$ \To $n$ \Do
    \li \If $A[i] \isequal x$ \Do
    \li \Return $i$
    \End
    \End
    \li \Return \nil
\end{codebox}

We state the loop invariant as follows: At the start of each iteration of the $\textbf{for}$ loop of lines 1-3, $x$ does not appear in subarray $A[1:i-1]$.

• Initialization: Before the first iteration, $i=1$, and $A[1:i-1]$ gives us an empty array. An value of course cannot be in an empty array.
• Maintenance: In each iteration, there are two possible situations. First, if $x$ does not equal $A[i]$, $A[i]$ will join subarray $A[i:i-1]$, and thereby the loop invariant is maintained. Second, if $x$ equals $A[i]$, $i$ will be returned as the result, and the loop will stop.
• Termination: The loop variable $i$ starts at $1$ and increases by $1$ in each iteration, until exceeding $n$ or $x$ is found. If the loop ends because that $x$ is found, the output will be correct, as discussed previously. Otherwise, $i=n+1$, by the loop invariant, $x$ does not appear in array $A[1:i-1]=A[i:n]$, therefore $\text{\scriptsize NIL}$ will be the output. In conclusion, the algorithm is correct.

2.1-5

Consider the problem of adding two $n$-bit binary integers $a$ and $b$, stored in two $n$-element arrays $A[0:n-1]$ and $B[0:n-1]$, where each element is either $0$ or $1$, $a=\sum_{i=0}^{n-1} A[i]\cdot 2^i$, and $b=\sum_{i=0}^{n-1} B[i]\cdot 2^i$. The sum $c=a+b$ of the two integers should be stored in binary form in an $(n+1)$-element array $C[0:n]$, where $c=\sum_{i=0}^{n} C[i]\cdot 2^i$. Write a procedure $\text{A\scriptsize DD-\normalsize B\scriptsize INARY-\normalsize I\scriptsize NTEGERS}$ that takes as input arrays $A$ and $B$ , along with the length $n$, and returns array $C$ holding the sum.

\begin{codebox}
    \Procname{$\proc{Add-Binary-Integers}(A, B, n)$}
    \li $C \gets \varnothing, carry \gets 0$
    \li \For $i \gets 0$ \To $n-1$ \Do
    \li $C[i] \gets A[i] \oplus B[i] \oplus carry$
    \li \If $A[i] + B[i] + carry \ge 2$ \Do
    \li $carry \gets 1$
    \li \Else
    \li $carry \gets 0$ \End
    \End
    \li $C[n] \gets carry$
    \li \Return $C$
\end{codebox}