Question

Question 3. [15 marks in total Consider the following code fragment with missing statements at ????. Assume that A is a nonempty array of integers and has length N. Assume that it has already been initialised. Refer to this code in parts (a-e) below. A [0] int count 1; int i- 1 while (i< NI1 count> N/2 ) if (xAi]) count++ int x else ???? i+ if (count> N/2) then answer-x Consider also an invariant describing the relationship between A and count as the loop iterates: array A has at least count items vith value A[i-11 in A[o...1-1 (Recall that A [O..i-1] identifies the portion of the array containing indices between 0 and i-1.) (3 marks) Show that the invariant is satisfied after x and count have been initialised a. b. (3 marks) Complete the code at ???? so that the invariant is maintained. (That is, if it is satisfied prior to an iteration, then it should remain true at the end of the iteration.) Do not introduce any new variables, and do not change the code in any other place (3 marks) What extra condition on array A is needed so that answer is always set to the majority item in A if such a value exists? C. Recall that the majority is the (unique) value that occurs in A more than N/2 times d. (2 marks) Modify the invariant above so that if the condition identified in (e) holds, then the invariant can be used to show that the code finds the majority item (4 marks) Give an example to show that the assumption in (c) is necessary e.

no other details are given, its asking for the invariant

programming language: Java

Answer 1

A) At the start x = A[0] and it's count is 1. Invariant: Array has at least 1 element equal to A[0] in A[0... 0] is true because there exactly one element equal to A[0], itself.
B) ???? -->> x = A[i], count = 1; Let;s proof that invariant will stay true after iteration if we know that it is already true. we know that at the moment we have at least count elements equal to x. If "if condition" is held then count is incremented by one, but one element equal to x is added too so if we had numberOf(x) >= count than numberOf(x)+1 >= count+1 is true too. If else condition is held than we get count equal to one and x will be new element, it is similar to the base case explained in question A.
C) Majority item should be last element of the Array.
D) New Invariant will be: "array A has at least count items with value A[i-1] in A[0....i-1] and A[N-1] is majority item if such exists"
E) Let's say our array is {2 1 2 2 3}, here majority element is 2, but our while cycles last element will be 3, because before the last step x is equal to 2 and count is 2, at the last step x is not equal to 3, so else condition is held and x will became 3 and count will be 1. So final x will be 3 not 2.

Note: While condition is not correct, imagine array filled with entirely ones. {1, 1, 1, 1, 1, 1, 1, 1}. At the last step when i is equal to N-1, count will be 8 and after this step in while condition we have (i < N || count > N/2), i is equal to N so first part is false but count is equal to N and N > N/2, so we get (false || true) which is true and while cycle will continue without stop and we will get run time error.

Comment down for any queries

Please give a thumb up