Skip to content

Week 1 - Loop Invariant

Assignment - Due 09/29/2018

Credit: source code of questions are from walkccc.

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.

linear search

  • Loop invariant Prior to i-th iteration, v was not found in subarray A[0..i - 1].
  • Initialization i = 0, A[0..i - 1] is empty, v was not found.
  • Maintenance Providing v was not found in A[0..i-1], it then compare v with A[i]. The loop continues means v was not found in subarray A[0..i - 1], otherwise it returns the result i.
  • Termination If v was found, it reaches early termination and return the index. Or it will end when i > A.length. From loop invariant we know that the whole array A doesn't contain value of v, so returning NIL is correct.

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.

binary adder

2.2.2

Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in A[1]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n - 1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. - What loop invariant does this algorithm maintain? - Why does it need to run for only the first n - 1 elements, rather than for all n elements? - Give the best-case and worst-case running times of selection sort in \Theta-notation.

  • Loop invariant
    • Outer loop: Prior to i-th iteration, A[0..i - 1] are i smallest elements in ascending order from A.
    • Inner loop, Prior to j-th iteration, A[j..n - 1] has element to be compared with A[i].
  • Because after running for the first n-1 elements, A[0...n-2] contains are n-1 smallest elements increasingly, which leaves A[n] the largest element, therefore no need for the final round running.
  • Running time are \Theta(n^2) in both best-case and worst-case, because both will traverse the whole array.

2.3.2

Rewrite the \text{MERGE} procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

2.3.3

Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

T(n) = \begin{cases} 2 & \text{if } n = 2, \\\\ 2T(n / 2) & \text{if } n = 2^k, \text{for } k > 1 \end{cases}

is T(n) = n\lg n.

2.3.4

We can express insertion sort as a recursive procedure as follows. In order to sort A[1..n], we recursively sort A[1..n - 1] and then insert A[n] into the sorted array A[1..n - 1]. Write a recurrence for the running time of this recursive version of insertion sort.

2.3.5

Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is \Theta(\lg n).

2.3.6

Observe that the while loop of lines 5–7 of the \text{INSERTION-SORT} procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray A[i..j - 1]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to \Theta(n\lg n)?

2.2

Bubblesort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order.

1
2
3
4
5
BUBBLESORT(A)
    for i = 1 to A.length - 1 
        for j = A.length downto i + 1 
            if A[j] < A[j - 1]
                exchange A[j] with A[j - 1]

a. Let A' denote the output of \text{BUBBLESORT}(A) To prove that \text{BUBBLESORT} is correct, we need to prove that it terminates and that

A'[1] \le A'[2] \le \cdots \le A'[n], \tag{2.3}

where n = A.length. In order to show that BUBBLESORT actually sorts, what else do we need to prove?

The next two parts will prove inequality \text{(2.3)}.

b. State precisely a loop invariant for the for loop in lines 2–4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.

c. Using the termination condition of the loop invariant proved in part (b), state a loop invariant for the for loop in lines 1–4 that will allow you to prove inequality \text{(2.3)}. Your proof should use the structure of the loop invariant proof presented in this chapter.

d. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

a. We need to prove that A' is an permutation of A. Because only the exchanging of elements happens in bubble-sort, the statement holds.

b. Loop invariant: prior to j-th loop, A[j] is the smallest element in A[j..n], and elements remain identical.

  • Initialization j == n, it's trivial.
  • Maintenance By entering j-th iteration, A[j] is the smallest element in A[j..n]. If A[j] < A[j - 1], the swapping makes A[j - 1] the smallest element in A[j - 1..n].
  • Termination When variable j goes down to i, the loop ends, and A[i] is the smallest element in A[i..n] by loop invariant.

c. Loop invariant: prior to i-th loop, A[1..i-1] are smallest elements increasingly in A

  • Initialization A[1..0] is empty, it's trivial.

  • Maintenance By entering i-th iteration, A[1..i-1] are smallest elements in ascending order. And by the loop invariant of the inner for loop, A[i] is the smallest element in A[i..n], so A[1..i] are smallest in A.

  • Termination When i goes up to n, the loop ends. By loop invariant, A[1..n - 1] are the smallest elements of A in ascending order.

d. The same \Theta(n^2).

2.4

Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A.

a. List the five inversions in the array \langle 2, 3, 8, 6, 1 \rangle.

b. What array with elements from the set \{1, 2, \ldots, n\} has the most inversions? How many does it have?

c. What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.

d. Give an algorithm that determines the number of inversions in any permutation of n elements in \Theta(n\lg n) worst-case time. (\textit{Hint:} Modify merge sort).