Algorithm design problem set

LE/EECS3101: Design and Analysis of Algorithms

Tutorial 1: Iterative Algorithms & Loop Invariants

Solution

1 Palindrome

Below is a simple iterative algorithm to determine whether a string is a palindrome. A palindrome is a word that reads the same backwards as forward, such as mom, madam, WoW, and Anna.

1 fun i s P a l i n d r o m e ( s t r = [ 1 . . n ] ) 2 i s P a l = t r u e 3 i = 1 , j = n 4 while i <= j 5 i f s t r [ i ] != s t r [ j ] # assume != i g n o r e s c a s e 6 i s P a l = f a l s e 7 break 8 i = i + 1 9 j = j − 1

10 11 postcond if str is a palindrome then isPal is true, false otherwise

Questions

1. Prove that isPalindrome is correct. Remember to clearly state the loop invariant and define any necessary preconditions.

Answers

1. Precondition: isPal is true

LI: str[1..i-1] + str[j+1..n] is a palindrome (where + is the string con- catenation operator).

• Initialization: In the first iteration, i = 1 and j = n. Therefore, str[1..i-1] and str[j+1..n] are both empty. The concatenation of two empty strings is empty and an empty string is a palindrome. LI(1) holds.

1

• Maintenance: For all i > 1, assume L(i-1) holds. In the ith-1 iteration, j = n - i + 2. Therefore, L(i-1): str[1..i-2] + str[n-i+3..n] is a palindrome.

There are two cases to prove. In the first case str[i] != str[j], the string is not a palindrome. isPal is set to false and the loop breaks.

In second case, str[i] == str[j]. Since L(i-1) is true, adding the same character to the end of str[1..i-2] and the beginning of str[n-i+3..n] implies that str[1..i-1] + str[n-i+2..n] is a palindrome. L(i) holds.

• Termination: The loop can terminate in one of two ways:

(a) if the string is not a palindrome, the loop breaks after setting isPal to false. The postcondition holds.

(b) i eventually exceed j. In this case the string was exhausted. Per the maintenance of the loop invariant, the string is a palindrome and isPal is never set to false. isPal is true per the precondition so the postcondition holds.

2 Merge

The merge step of the MergeSort algorithm combines two sorted arrays into a single sorted array. Assume the two input arrays are A[1..n] and B[1..m], merge works by maintaining, at all times, a pointer to the smallest element in each input array that is not yet in the output array (C[1..n+m]). In each step, merge takes the smallest of the two elements pointed to in A and B and adds it to the next position in C.

E.g., suppose we are merging A=[2, 3] and B=[1, 5]. We will use i and j to point to the smallest element in A and B that are not yet in C, respec- tively.

• In the first iteration, i = 1, j = 1, and C = []. B[j] = 1 < A[i] = 2. Therefore B[j] is copied into C[1] and j is incremented.

• In the second iteration, i = 1, j = 2, and C = [1]. A[i] = 2 < B[j] = 5. Therefore A[i] is copied into C[2] and i is incremented.

• In the third iteration, i = 2, j = 2, and C = [1, 2]. A[i] = 3 < B[j] = 5. Therefore A[i] is copied into C[3] and i is incremented.

• In the final iteration, i = 3, j = 2, and C = [1, 2, 3]. There are no elements left in A that are not in C (i > n). Therefore B[j] is copied into C[4] and j is incremented. C = [1, 2, 3, 5].

2

1 fun merge (A [ 1 . . n ] , B [ 1 . . m] ) 2 s = n + m 3 C = empty a r r a y o f s i z e s 4 5 i = 1 , j = 1 6 for k = 1 to s 7 i f j > m # e d g e c a s e : no e l e m e n t s l e f t i n B 8 C [ k ] = A [ i ] 9 i = i + 1

10 e l s e i f i > n # e d g e c a s e : no e l e m e n t s l e f t i n A 11 C [ k ] = B [ j ] 12 j = j + 1 13 e l s e i f A [ i ] <= B [ j ] 14 C [ k ] = A [ i ] 15 i = i + 1 16 e l s e 17 C [ k ] = B [ j ] 18 j = j + 1 19 20 postcond C is a sorted permutation of A + B 21 return C

Questions

1. What is the computation state in merge? how is it defined?

2. Identify the main computation step in merge and describe how it modifies the computation state.

3. Prove that merge is correct. Remember to clearly state the loop invariant and define any necessary preconditions.

Answers

1. The state of the computation can be defined as a pair of collections <S1, S2>. The first collection, S1 is a sorted list containing all the elements in A[1..i] and B[1..j]. The second collection, S2 contains the remaining unprocessed elements in A[i+1..n] and B[j+1..m].

2. In each computational step, an unprocessed element is taken out of S2 and sorted into S1.

3. LI: C contains the k − 1 smallest element of A and B in sorted order.

• Initialization: LI(1): C contains the 0 smallest element of A and B in sorted order. Before the start of the first iteration, S is completely empty. Therefore, LI(1) holds.

3

• Maintenance: for all k > 1, assume LI(k-1) holds, i.e., C contains the k − 2 smallests element of A and B in sorted order. We have four cases:

First note that in all cases, whenever an element is copied from A to C, i is incremented. Similarly, whenever an element is copied from B to C, j is incremented. Since A and B are sorted, i and j hence always point to the smallest element of A and B, respectively.

– Suppose j > m, then B has no elements left. Since A is sorted, C[k] is assigned the smallest element of A (A[i]) that is not yet in C. By assumption, C contains the k-2 smallest elements so after adding A[i], C contains the k-1 smallest elements in A and B. Therefore, LI(k) holds.

– Suppose i > n, then A has no elements left. Since B is sorted, C[k] is assigned the smallest element of B (B[j]) that is not yet in C. By assumption, C contains the k-2 smallest elements so after adding B[j], C contains the k-1 smallest elements in A and B. Therefore, LI(k) holds.

– Suppose A[i] ≤ B[j]. Since A is sorted, C[k] is assigned the small- est element of A (A[i]) that is not yet in C. By assumption, C contains the k-2 smallest elements so after adding A[i], C contains the k-1 smallest elements in A and B. Therefore, LI(k) holds.

– Suppose A[i] > B[j]. Since B is sorted, C[k] is assigned the smallest element of B (B[j]) that is not yet in C. By assumption, C contains the k-2 smallest elements so after adding B[j], C contains the k-1 smallest elements in A and B. Therefore, LI(k) holds.

• Termination: The loop terminates when k = s + 1. By the loop invariant, C contains the s smallest elements in A and B in sorted order. Since s = n + m, that is all the elements of A and B in sorted order. The postcondition holds.

3 Selection Sort

Selection sort is yet another comparison-based sorting algorithm that works by repetitively selecting the minimum element and inserting it in the appro- priate position in the array.

E.g., Let A = [4, 3, 1, 2].

• In the first iteration, selection sort selects the minimum in A[1..n] (1) and swaps it with the first element of the array (4). The result is A = [1, 3, 4, 2].

4

• In the second iteration, selection sort selects the minimum in A[2..n] (2) and swaps it with the second element of the array (3). The result is A = [1, 2, 4, 3].

• In the final iteration, selection sorts selects the minimum in A[3..n] (3) and swaps it with the third element of the array (4). The result is A = [1, 2, 3, 4].

1 fun s e l e c t i o n S o r t (A [ 1 . . n ] ) 2 for i = 1 to n − 1 3 minIdx = i 4 for j = i + 1 to n 5 i f A [ j ] < A [ minIdx ] 6 minIdx = j 7 swap (A, i , minIdx ) 8 postcond A is a sorted permutation of the input array A

Questions

1. What is the computation state in selectionSort? how is it defined?

2. Identify the main computation step in selectionSort and describe how it modifies the computation state.

3. Prove that selectionSort is correct. Remember to clearly state the loop invariant(s) and define any necessary preconditions.

Answers

1. The state of the computation can be defined as a pair of collections <S1, S2>. The first collection, S1 is a sorted list containing all the elements in A[1..i]. The second collection, S2 contains the remaining unprocessed elements in A[i+1..n].

2. In each computational step, an unprocessed element is taken out of S2 and sorted into S1.

3. First let’s prove the correctness of the inner loop.

Precondition: minIdx is set to i.

Postcondition: minIdx contains the index of the smallest element in A[i..n].

LI2 (inner): minIdx contains the index of the smallest element in A[i..j-1].

• Initialization: Before the first iteration j = i + 1. Therefore, LI2(1): minIdx contains the index of the smallest element in A[i..i] . There’s only one element in A[i..i] and, per the precondition, minIdx is already set to its index. LI2(1) holds.

5

• Maintenance: for all j >= i + 2, assume LI2(j-1) holds, i.e., minIdx contains the index of the smallest element in A[i..j-2]. We have two cases to consider:

– If A[j] < A[minIdx], then minIdx is set to j. Per the assumption, minIdx now contains the index of the smallest element in A[i..j-1]. The loop invariant is established for the next iteration, i.e., LI2(j) holds.

– Otherwise, minIdx is not modified. Per the assumption, minIdx contains the index of the smallest element in A[i..j-2]. Since A[j] >= A[minIdx], minIdx contains the index of the smallest element in A[i..j-1]. LI2(j) holds.

• Termination: The loop terminates when j = n + 1. By the loop invariant, minIdx contains the smallest element in A[i..n]. The post- condition holds.

Next, we will prove the correctness of the outer loop.

LI1 (outer): A[1..i-1] contains the i-1 smallest elements of A in sorted order.

• Initialization: Before the first iteration i = 1. A[1..0] is empty so LI1(1) holds.

• Maintenance: for all i > 1, assume LI1(i-1) holds, i.e., A[1..i- 2] contains the i-2 smallest elements of A in sorted order. After the termination of the inner loop, minIdx will contain the index of the smallest element in A[i-1..n] per the postcondition of the inner loop. Line 7 swaps A[minIdx] and A[i-1]. Since A[i-1] now contains the smallest element in A[i-1..n], A[1..i-1] contains the i-1 smallest elements of A. LI1(i) holds.

• Termination: The loop terminates when i = n. By the loop in- variant, A[1..n-1] contains the smallest n-1 elements of A. The only remaining element, A[n], is the maximum in A[1..n]. Therefore, A[1..n] is sorted. The postcondition holds.

4 Bonus: Recursion Invariants

Let’s table this for later.

6