exercises_2.1.md

2.1 Insertion sort

2.1-1

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

• $$A = \left \langle 31, 41, 59, 26, 41, 58 \right \rangle$$
• $$A = \left \langle 31, 41, 59, 26, 41, 58 \right \rangle$$
• $$A = \left \langle 26, 31, 41, 59, 41, 58 \right \rangle$$
• $$A = \left \langle 26, 31, 41, 41, 59, 58 \right \rangle$$
• $$A = \left \langle 26, 31, 41, 41, 58, 59 \right \rangle$$

2.1-2

Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of nondecreasing order.

def insertion_sort(a):
    for j in range(1, len(a)):
        key = a[j]
        i = j - 1
        while i >= 0 and a[i] < key:
            a[i + 1] = a[i]
            i -= 1
        a[i + 1] = key

2.1-3

Consider the searching problem:

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

Output: An index $$i$$ such that $$v=A[i]$$ or the special value 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.

def linear_search(a, v):
    for i in range(len(a)):
        if a[i] == v:
            return i
    return None

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.

def add_binary(a, b):
    n = len(a)
    c = [0 for _ in range(n + 1)]
    carry = 0
    for i in range(n):
        c[i] = a[i] + b[i] + carry
        if c[i] > 1:
            c[i] -= 2
            carry = 1
        else:
            carry = 0
    c[n] = carry
    return c