COMP3270 Assignment 3 Solution

Instructions:
4. Think carefully; formulate your answers, and then write them out concisely using English, logic, mathematics and pseudocode (no programming language syntax).

1. (8 points) Exercise 3.1-4 (pp. 53). Answer yes or no, and then explain why or why not. No credit without explanation.
Is 2n + 1 = O(2n)? Yes
Let 2n + 1 = T(n)
It must be shown that cg(n) ≥ T(n) where c is a constant and g(n) = 2n
2n + 1 can be written as 2n * 2
For the question to be true it must be true that c(2n) ≥ 2n + 1
Since 2n + 1 = 2 * 2n then it is also true that 2(2n) ≥ 2n + 1
2 is just a constant with g(n) = 2n therefore the Big-Oh is O (g(n)) = O(2n)
Is 22n = O(2n)? No
Let 22n = T(n)
It must be shown that cg(n) ≥ T(n) where c is a constant and g(n) = 2n
22n can be written as 2n * 2n
For the question to be true it must be true that c(2n) ≥ 22n. However, there is no constant c where this inequality can become true. Therefore 22n ≠ O(2n)?
2. (10 points)

Repeats (A[1…n]: integer array)
1 count = 0
2 number = −∞
3 for i = 1…(n-1) do
4 if A[i]==A[i+1] then
5 count=count+1
6 if number ≠ A[i] then
7 print number
8 number = A[i]
9 print count

Does the algorithm above correctly solve the problem of counting the total number of all integers that repeat consecutively in the input array A correct? (E.g., if A contains 1 2 3 3 3 4 5 6 6 7 8 8 8 8 1 2 3 3 then count must be 11)? Answer yes or no. If your answer is yes, provide an explanation (no formal proof is required). If your answer is no, provide a counter example with input, correct answer, algorithm’s output and a short explanation of why algorithm’s output is different from the correct answer.
No
Problem Instance: A is [1, 2, 3, 4, 4]
The correct output is 2
The algorithm outputs 1, which is incorrect
The output is incorrect because when the algorithm finds repeating consecutive integers it counts wrong. In this instance it saw that 4 and 4 were two repeating consecutive integers but it only increased the count to 1.

3. (20 points)

Select (A: Array [1..n] of distinct integers, k: integer between 1 and n)
1 for i=n down to n-k+1
2 position=i
3 for j=1 to (i–1)
4 if A[j]>A[position] then position=j
5 if position≠i then
6 temp=A[i]
7 A[i]=A[position]
8 A[position]=temp
9 print A[n-k+1]

The algorithm above correctly solves the problem of finding the k-th largest number in the input array. Complete the correctness proof by contradiction below by filling in the blanks.

Proof by contradiction:
1. Suppose the algorithm is incorrect.
2. That means that for at least one valid input array of n numbers and integer k, 1<=k<=n, (a) either it will not halt or (b) it will not print the k-th largest number .
3. Other than the two loops on lines 1 and 3, all other steps of the algorithm are basic operations that will halt. The loop statement in line 1 will exit after exactly k + 1 executions and the loop statement in line 3 will execute i times for each execution of the outer loop in line 1. But since
the value of i will always be between n and n – k + 1, these will be finite executions also. So the algorithm must eventually halt.
4. So the only way the algorithm can be incorrect is if, for at least one valid input array of numbers of size n and integer k where 1<=k<=n, it does not print the k-th largest number.
5. Consider such an input. In the first execution of the outermost for loop, i=n, position=i=n initially, and the inner for loop will execute for j from 1 to (n-1).
6. Each time the inner loop is executed, A[j] is compared to A[position] and if the former is larger position is updated to j.
7. Therefore, after each execution of this inner loop, position must point to the index with the largest integer looked at by the algorithm up to this point.
8. Since this is repeated for every cell j=1…(n-1), and since position initially pointed to cell n, after the inner loop completes, position must point to the index with the largest integer in the array.
9. Then lines 5-8 will swap this largest number with the number in array cell n unless the largest number was already in A[i]=A[n]. Therefore, after the first execution of the outermost loop, the largest number from the array cells A[1] to A[n] will be in cell with index n.
10. In the second execution of the outermost for loop, i= n – 1, position= n – 1 initially, and the inner for loop will execute for j from 1 to n – 2. So by a similar argument, after the second execution of the outermost loop, the largest number in the array cells A[1] to A[n – 1] will be in cell with index A[n – 1].
11. Since the first largest number in array cells 1…n was already in cell n before the second execution of the outer loop started, this means that the second largest number in the array will now be in cell (n-1).
12. By a similar argument, after the k-th execution of the outermost loop, the k-th largest number in the array will be in cell with index n – k + 1.
13. Line 9 prints this number. So for any array of numbers of size n and integer k where 1<=k<=n, the algorithm will print the k-th largest number in the array.
14. This contradicts step 2 and 4 of the proof.
15. So our assumption in step 1 must be wrong, i.e. the algorithm has to be correct.

4. (18 points) Determine a Loop Invariant for the outer for loop of the Selection-Sort algorithm below that allows you to prove that the algorithm is correct. Then state the proof. Parts of both are given – fill in the blanks. Understanding how this algorithm works will give you the needed information to construct an appropriate loop invariant.
Selection-Sort (A: Array [1..n] of integer)
1 for i=n down to 2
2 position=i
3 for j=1 to (i–1)
4 if A[j]>A[position] then position=j
5 if position≠i then
6 temp=A[i]
7 A[i]=A[position]
8 A[position]=temp

Explanatory Notes: The key here is to first understand how this algorithm sorts – by finding the position of the largest number in the array A[1,…n] and swapping that with the nth cell of the array, then finding the position of the largest number in the array A[1,…(n-1)] and swapping that with the (n-1)th cell of the array, and repeating this process for subarrays A[1,…(n-2)], A[1,…(n-3)],…,A[1,2]. Note that the outer loop is executed (n-1) times, with the value of the loop variable i going from n down to 2. So during the first execution of the outer loop (line 1), i=n, after which A[n] will contain the (first) largest number in the array and i will be decremented to n-1. During the second execution of the outer loop, i=n-1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array and i will be decremented to n-2. During the third execution of the outer loop, i=n2, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, and A[n-2] will have the third largest number in the array and i will be decremented to n-3. During the kth execution of the outer loop (we are using k to count the loop executions because the loop variable i is decremented and so does not count the number of executions of the loop itself), i=n-k+1, after which A[n] will contain the first largest number in the array and A[n-1] will have the second largest number in the array, etc., and i will be decremented to n-k.

Loop Invariant:
Before kth execution of the outer loop (line 1), the loop variable i=n-k+1, and the (k-1) largest numbers in array A will be in the subarray A[i+1…n]

Initialization:
The LI should hold before the first execution of the loop: Before the 1st execution of the loop, the loop variable i=n-1+1=n, and 0th,…,1st largest numbers in array A will be in subarray A[(n+1)…n]. But both the 0th largest number and the subarray A[n+1…n] are undefined for an array of n numbers. So the LI trivially holds.

Maintenance:
Here we have to show that if the LI held true before the kth execution of the loop, it must also be true after the kth execution, i.e., before the (k+1)th execution.
So suppose before the kth execution of the loop the LI holds, i.e., the loop variable i=n-k+1, and the k-1 largest numbers in array A are in the subarray A[i+1…n].
During this execution, the local variable position is initialized to i=n-k+1 (line 2).
The for loop executes for each value of j from 1 to (i-1)=(n-k) (line 3).
Each time, if a number A[j] greater than A[position] is found then position is updated to j. Therefore, since position starts out being (n-k+1) and j goes from 1 to (n-k), at the end of this loop, position will contain the index of the largest number in the subarray A[1…n-k+1].
Line 5 checks to see if this index is the same as i=(n-k+1). If it is, then nothing is done, and the largest number in subarray A[1…n-k+1] is in array cell A[n-k+1]. If it is not, then A[position] and A[n-k+1] are swapped by lines 6-8 so that the largest number in subarray A[1…n-k+1] is in array cell A[1…n-k+1] Since the k-1 largest numbers in array A were already in the subarray [i+1…n] before the kth execution of the loop started, this means that by the end of the kth execution of the loop, the kth largest number will be in array cell A[n-k+1].
Finally, by the nature of the for loop, the loop variable i is decremented to n-k, and the kth execution of the loop finishes.
So after the kth execution of the loop finishes, i.e., before the (k+1)th execution of the loop, the loop variable i= n-k, and the k largest numbers in array A will be in the subarray A[n-k+1…n].
Thus, if the LI holds before the kth execution of the loop, it will hold before the (k+1)th execution of the loop.

Termination:
As we have proved initialization and maintenance, it holds that LI must be true after the loop finishes. The loop is executed (n-1) times. So after the (n-1)th execution, i.e., before the nth execution, the loop variable i= 1, and the n-1 largest numbers in array A will be in the subarray A[2…n]. Since the first (n-1) largest numbers are thus now already sorted, what is in A[1] must be the nth largest, i.e., the smallest, number in the input array. Therefore A is fully sorted in the increasing order.

5. (24 points) Calculate the complexity T(n) of the Bubble-sort algorithm below. Calculate the constant cost of a step by assuming that each basic operation included in that step – addition, subtraction, multiplication, division, array-read, array-write, assigning a value to a variable, returning a value, etc. – has a cost of 1. So the cost of executing a statement once is to be calculated as the total number of basic operations that have to be executed. Fill in the table below, then determine the expression for T(n) and simplify it to produce a polynomial in n. In the second column for steps 4-9, provide sigma (summation) notation.
Bubble-sort (A: Array [1..n] of integer)
1 i=1
2 while i≤(n–1)
3 j=1
4 while j≤(n–i)
5 if A[j]>A[j+1] then
6 temp=A[j]
7 A[j]=A[j+1]
8 A[j+1]=temp
9 j=j+1
10 i=i+1

Step Cost of each execution Total # of times executed
1 1 1
2 5 n
3 1 n – 1
4 6 "#$ # 𝑡!
!%$
5 8 "#$
# 𝑡! − 1
!%$
6 4 "#$
# 𝑡! − 1
!%$
7 7 "#$
# 𝑡! − 1
!%$
8 5 "#$
# 𝑡! − 1
!%$
9 3 "#$
# 𝑡! − 1
!%$
10 3 n – 1
ti = the number of times the while loop test in line 4 is executed for the value of i
T(n) for Bubble-sort = 1(1) + 5(n) + 1(n – 1) + 6( 𝒏𝒊%#𝟏𝟏 𝒕𝒊 𝒏𝒊%#𝟏𝟏 𝒕𝒊 − 𝟏 ) +
7( ∑𝒏𝒊%#𝟏𝟏 𝒕𝒊 − 𝟏 ) + 5( ∑𝒏𝒊%#𝟏𝟏 𝒕𝒊 − 𝟏 ) + 3( ∑𝒏𝒊%#𝟏𝟏 𝒕𝒊 − 𝟏 ) + 3(n – 1)
= 1 + 5n + n – 1 + 6(n(n – 1)/2) + 8((n(n – 1)/2) – n + 1) + 4((n(n – 1)/2) – n + 1) + 7((n(n – 1)/2) – n + 1) + 5((n(n – 1)/2) – n + 1) + 3((n(n – 1)/2) – n + 1) + 3n – 3
𝟑(𝟏𝟏𝐧𝟐#𝟐𝟑𝐧-𝟏𝟔)
𝟐
=

6. (7 points) Exercise 2.3-4 (pp. 39). You need to first provide the recursive algorithm (parts of it given below; complete it), using pseudocode conventions, and then develop and state the two recurrence relations. You do not have to provide the constant values; instead use Θ(1) for a constant value, Θ(n) for a constant multiplier of n, etc. You do not need to solve the recurrences.

Insertion-sort-recursive(A[1..n])
if n>1 then
Insertion-sort-recursive(A[1…n – 1])
key= A[n – 1]
i= n – 1
while i>0 and A[i]>key
A[i+1]=A[i] i=i-1
A[i + 1] = key

T(n)= Θ(1) if n=1; T(n) = T(n – 1) + Θ(n) if n> 1

alogbn =nlogba

level Level
number Total # of recursive executions at this level Input size to each recursive execution Work done by each recursive execution, excluding the recursive calls Total work done by the algorithm at this level
0 0 n 1 cn cn
1 1 𝐧

𝟐 4 𝐜𝐧 𝟒𝐜𝐧
𝟐 = 𝟐𝐜𝐧
𝟐

2 2 𝐧

𝟒 16 𝐜𝐧 𝟏𝟔𝐜𝐧
𝟒 = 𝟒𝐜𝐧
𝟒
The
level
just
above the base case level


𝐥𝐨𝐠𝟐 𝐧 − 𝟏



2


𝐧𝟐 𝟒(𝐥𝐨𝐠𝟐𝐧)’𝟏 =
𝟒




= 𝟐𝐜
𝟐(𝐥𝐨𝐠𝟐 𝐧)#𝟏
𝐜𝐧



𝟒(𝐥𝐨𝐠𝟐𝐧)−𝟏𝐜𝐧 𝐧𝟐𝐜
=
𝟐(𝐥𝐨𝐠𝟐 𝐧)#𝟏 𝟐

Base case level
𝐥𝐨𝐠𝟐 𝐧

1
𝟒𝐥𝐨𝐠𝟐𝐧 =𝐧𝟐

c

𝐜𝐧𝟐


𝟐𝐜𝐧𝟐 − 𝐜𝐧
T(n) = ∑𝐥𝐨𝐠𝐤%𝟎𝟐 𝐧 𝟒𝐤 𝟐 𝐥𝐨𝐠𝐤%𝟎𝟐 𝐧 𝟒𝟐 𝐤𝐤 𝐥𝐨𝐠𝐤%𝟎𝟐 𝐧 𝟐𝐤 = 𝐜𝐧 ∙ (𝟐𝐧 − 𝟏) =

Complexity order of the algorithm = Θ(n2)

8. (20 points). Do Exercise 4.5-1 (pp 96).
√𝐧
(a) a= 2 b= 4 f(n)= 1 Which case applies? 1 T(n)=Θ()
√𝐧
(b) a= 2 b= 4 f(n)= Which case applies? 2 T(n)=Θ(
(c) a= 2 b= 4 f(n)= n Which case applies? 3 T(n)=Θ(n)
(d) a= 2 b= 4 f(n)= n2 Which case applies? 3 T(n)=Θ(

9. (18 points) Solve the recurrences T(n)=T(n-1)+cn; T(1)=c where c is a constant, first by the backward substitution method and then by the forward substitution method. In each case fill in the blanks.

Backward substitution method:
T(n) =T(n-1) + nc
=T(n-2) + (n-1)c + nc
= T(n-3) + (n-2)c + (n-1)c + nc
…
𝐜 (𝐧(𝐧%𝟏))
𝟐
= //the final expression without a T() term
=Θ(n2)
Forward substitution method:
T(1)= c
T(2)= T(1) + 2c
T(3)= T(1) + 2c + 3c
…
𝐜 (𝐧(𝐧%𝟏))
𝟐
= //the final expression without a T() term
=Θ(n2)