Select (A: Array [1..n] of distinct integers, k: integer between 1 and n) 1 for
ID: 3600704 • Letter: S
Question
Select (A: Array [1..n] of distinct integers, k: integer between 1 and n)
1 for i=n down to k
2 position=i
3 for j=1 to (i–1)
4 if A[j]>A[position] then position=j
5 if positioni 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:
Suppose the algorithm is _______________.
That means that for at least one valid input array of n numbers and integer k, 1<=k<=n, (a) either it will not _____ or (b) it will __________________.
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 _________ 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 __________, these will be finite executions also. So the algorithm must eventually halt.
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 _______________.
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).
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.
Therefore, after each execution of this inner loop, position must point to __________________________.
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 _______________________________________.
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 __________ will be in cell with index _____.
In the second execution of the outermost for loop, i=_______, position=________ initially, and the inner for loop will execute for j from ____ to ______. So by a similar argument, after the second execution of the outermost loop, the largest number in the array cells _______ will be in cell with index ________.
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).
By a similar argument, after the k-th execution of the outermost loop, _______________ in the array will be in cell with index ___________.
Line 9 prints this number. So for any array of numbers of size n and integer k where 1<=k<=n, the algorithm will __________________________.
This contradicts step _____ of the proof.
So our assumption in step 1 must be wrong, i.e. the algorithm has to be correct.
Explanation / Answer
ANSWER
Suppose the algorithm is false
That means that for at least one valid input array of n numbers and integer k, 1<=k<=n, (a) either it will not maximum or (b) it will maximum among all n 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 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 1<-k<=n , these will be finite executions also. So the algorithm must eventually halt.
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 exist .
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).
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.
Therefore, after each execution of this inner loop, position must point to maximum value index .
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 maximum value index .
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[position] will be in cell with index position.
In the second execution of the outermost for loop, i= 2 , position= 2 initially, and the inner for loop will execute for j from 1 to 1 . So by a similar argument, after the second execution of the outermost loop, the largest number in the array cells A[position] will be in cell with index position.
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).
By a similar argument, after the k-th execution of the outermost loop, maximum value in the array will be in cell with index (k-1).
Line 9 prints this number. So for any array of numbers of size n and integer k where 1<=k<=n, the algorithm will gives maximum value at (k-1).
This contradicts step 1 of the proof.
So our assumption in step 1 must be wrong, i.e. the algorithm has to be correct.
IF ANY DOUDTS PLEASE GET BACK TO ME
THANK YOU FOR THE OPPURTUNITY