Exercise 2.1

Exercise 2.1-1¶

Using Figure 2.2 as a model, illustrate the operation of INSERTION-SORT on the array A = [31, 41, 59, 26, 41, 58].

Iteration 1
           1  2  3  4  5  6
          [31 41 59 26 41 58]

Iteration 2 
           1  2  3  4  5  6
          [31 41 59 26 41 58]

Iteration 3 
           1  2  3  4  5  6
          [31 41 59 26 41 58]

Iteration 4
           1  2  3  4  5  6
          [26 31 41 59 41 58]

Iteration 5
           1  2  3  4  5  6
          [26 31 41 41 59 58]

Iteration 6
           1  2  3  4  5  6
          [26 31 41 41 58 59]

Exercise 2.1-2¶

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

NON-INCREASING INSERTION-SORT(A)

1  for j = 2 to A.length
2      key = A[j]
3      // Insert A[j] into the sorted sequence A[1..j-1]
4      i = j -1 
5      while i > 0 and A[i] < key
6          A[i+1] = A[i]
7          i = i - 1
8      A[i+1] = key

Python code

def insertion_sort(A):
    """Sorts the array `A` in descending order using `Insertion sort` algorithm

    Args:
        A: Array of numbers to be sorted

    Returns:
        Array of numbers in sorted, descending order
    """
    for j in range(1, len(A)):
        key = A[j]
        # Insert A[j] into the sorted sequence A[0..j-1]
        i = j - 1
        while i > -1 and A[i] < key:
            A[i + 1] = A[i]
            i = i - 1
        A[i + 1] = key 
    return A

tests = [
    [31, 41, 59, 26, 41, 58],
    [],
    [40, 20],
    [1],
    [10, 9, 8, 7],
    [7, 8, 9, 10]
]

for input_array in tests:
    print(f'Input: {input_array}')
    output_array = insertion_sort(input_array)
    print(f'Sorted: {output_array}\n')

Input: [31, 41, 59, 26, 41, 58]
Sorted: [59, 58, 41, 41, 31, 26]

Input: []
Sorted: []

Input: [40, 20]
Sorted: [40, 20]

Input: [1]
Sorted: [1]

Input: [10, 9, 8, 7]
Sorted: [10, 9, 8, 7]

Input: [7, 8, 9, 10]
Sorted: [10, 9, 8, 7]

Exercise 2.1-3¶

Consider the searching problem:

Input: A sequence of n numbers $A = \langle a_1, a_2, ... , a_n \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.

Pseudocode

LINEAR-SEARCH(A, V)

1  i = NIL
2  for j = 1 to A.length
3      if A[j] = v
4          i = j
5          return i
6  return i

Proof using Loop invariant

Invariant: At any point of time, the variable i holds the value of the index, till the point array has been scanned.

Initialization: Before the loop starts, the value of i is NIL, which is the right value since the array has not yet been searched, and assumed value is NIL

Maintenance: At each iteration, if v is equal to current element in A, value of that index j is assigned to i, which is the correct value to be returned. If not, value of i is still NIL.

Termination: If the loop is termintaed, it means that v is not found in A, and hence value of i remains NIL. Hence the algorithm is correct

Python Program

def linear_search(A, v):
    """Performs a linear search for `v` in array `A`

    Args:
        A: Array of numbers
        v: Number to be searched in `A`

    Returns:
        Index of the array A, if v is found in A
        `None` if v is not found in A
    """
    for j in range(0, len(A)):
        if A[j] == v:
            return j
    return None

tests = [
    [[31, 41, 59, 26, 41, 58], 41],
    [[35, 43, 19], 20],
    [[], 5],
    [[1], 1],
    [[3], -5],
    [[5, 7, 8], 5],
    [[5, 7, 8], 8]
]

for A, v in tests:
    print(f'Input: A = {A}, v = {v}')
    index = linear_search(A, v)
    print(f'Index: {index}\n')

Input: A = [31, 41, 59, 26, 41, 58], v = 41
Index: 1

Input: A = [35, 43, 19], v = 20
Index: None

Input: A = [], v = 5
Index: None

Input: A = [1], v = 1
Index: 0

Input: A = [3], v = -5
Index: None

Input: A = [5, 7, 8], v = 5
Index: 0

Input: A = [5, 7, 8], v = 8
Index: 2

Exercise 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: Arrays A and B of length n containing binary digits 0 and 1 of two numbers a and b

Output: Array C of length n + 1 containing binary digits of a + b

Pseudocode

ADD BINARY INTEGERS(A, B)

1  carry = 0
2  for i = n downto 1
3      sum = A[i] + B[i] + carry
4      C[i + 1] = sum (mod 2)
5      if sum > 1
6          carry = 1
7      else
8          carry = 0
9  C[1] = carry

Python code

def add_binary_integers(A, B):
    """Adds two binary integers

    Args:
        A: Array of 0 and 1 representing binary digits
        B: Array of 0 and 1 representing binary digits

    Returns:
        C: Array of 0 and 1 representing binary digits of A+B
    """
    carry = 0
    n = len(A)
    C = [0 for x in range(n+1)]

    for i in range(len(A) - 1, -1, -1):
        s = A[i] + B[i] + carry
        C[i + 1] = s % 2
        if s > 1:
            carry = 1
        else:
            carry = 0
    C[0] = carry
    return C

tests = [
    {"A": [0, 0, 0], "B": [0, 0, 0], "a": 0, "b": 0, "c": 0},
    {"A": [0, 0, 1], "B": [0, 1, 0], "a": 1, "b": 2, "c": 3},
    {"A": [1, 1, 1], "B": [1, 1, 1], "a": 7, "b": 7, "c": 14},
    {"A": [1], "B": [1], "a": 1, "b": 1, "c": 2},
]
for test in tests:
    A, B, a, b, c = test["A"], test["B"], test["a"], test["b"], test["c"]
    C = add_binary_integers(A, B)
    print(f'A = {A}, a = {a}')
    print(f'B = {B}, b = {b}')
    print(f'C = {C}, c = {c}\n')

A = [0, 0, 0], a = 0
B = [0, 0, 0], b = 0
C = [0, 0, 0, 0], c = 0

A = [0, 0, 1], a = 1
B = [0, 1, 0], b = 2
C = [0, 0, 1, 1], c = 3

A = [1, 1, 1], a = 7
B = [1, 1, 1], b = 7
C = [1, 1, 1, 0], c = 14

A = [1], a = 1
B = [1], b = 1
C = [1, 0], c = 2