Meiju.Video Autigers.org This question is kind of hard for me. Please do this qu
ID: 3880977 • Letter: M
Question
Meiju.Video Autigers.org This question is kind of hard for me. Please do this question with caution. Thank you very much.
(8. 5pts) Computational problem solving: Proving Correctness Let A be an algorithm that finds the kth largest of n elements by a sequence of comparisons. Prove by contradiction that A collects enough information to determine which elements are greater than the kth largest and which elements are less than it. In other words, you can partition the set around the kth largest element without making more comparisons.Explanation / Answer
Proof by contradiction:-
Let suppose A finds the kth largest element ( call it e ) in the array by making some n number of comparisons such that it can't partition the array into 2 halves, where the elements of one half are smaller and the other half are larger than e .
Hence, there exists some element x belonging to one partition where it is larger than e and other elements are smaller than it
AND
there exists some element y belonging to the other partition where it is smaller than e and other elements are larger than it.
This indicates that, e is NOT the kth largest element of the array as there are elements x and y that disrupt this order.
In other words, we can say that if THE ORIGINAL PARTITION WAS MADE SUCH THAT THE LEFT HALF HAD ALL ELEMENTS SMALLER THAN E AND RIGHT HALF HAD ALL ELEMENTS LARGER THAN E , THEN,
THE EXISTENCE OF ELEMENTS X AND Y VIOLATES THIS ORDER.
This is a contradiction to the assumed fact that e is the kth largest element of the array,
Hence, the algorithm successfully partitions the array into 2 halves such that one half has all elements larger than e and other half has all elements smaller than it.