Consider the followin code fragment with missing statements at ????. Assume that
ID: 3905110 • Letter: C
Question
Consider the followin 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. int x- A[O]; int count- 1; int i-1; while (i N/2) f if (xAC]) count++ else ???? if (count > N/2) then ansver- x; Consider also an invariant describing the relationship between A and count as the loop iterates: array A has at least count items with value A[i-1] in A[0...i-1] (Recall that ACo.. 1-1 identifies the portion of the array containing indices between O and 1-1.) a. (3 marks) Show that the invariant is satisfied after x and count have been initialised b. (3 marks) Complete the code at ???? so that the invariant is maintained. (That is, if it Do not introduce any new variables, and do not change the code in any other place. c. (3 marks) What extra condition on array A is needed so that answer is always set to the 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 (c) holds, then is satisfied prior to an iteration, then it should remain true at the end of the iteration.) majority item in A if such a value exists? the invariant can be used to show that the code finds the majority item e. (4 marks) Give an example to show that the assumption in (c is necessaryExplanation / Answer
a)
As x and count are initialised , the invariant is satisfied as array A is non empty and would contain atleat one element ,so it will atleast one similar element,so count turns to be atleat 1 and as first element has been considered ,so variable i has been used for the rest of the array A,so it is initialized to one leaving element at a[0],and this will hold after the iterations to,so invariant is satsfied.
Explanation:
let array a={1},i=1,count=1;
so there is an element 1,and as it has been considered too and will be maintained after the loop too,so the invariant has been satisfied.
b)
if(i>N/2 && count==1)
break;
if(count>N/2)
break;
c)'
Extra condition required on array A to get an value that occurs majority of time i.e more than n/2 times is that:
According to given code:
the first element should be the element which is repeated most number of times,else no result will be obtained.
Logically:
a loop has to initialized to check if values occuring in array till (N/2-1) are repeating majority of time or not as the elements encountered after n/2 can not repeat more than n/2 times simply.So this check is necessary to get the value repeating majority number of times.
for better efficieny the array can be sorted,which will make it efficient while iterating.
d)invariant changes have been shown in e)
e)
for(int i=0;i<n-1;i++)
{
for(j=i+1;j<n-(i+1);j++)
{
if(a[j]>a[j+1])
{
int temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
int max,element;
for(int i=0;i<N/2;i++)
{
int chk=a[i];
count=1;
for(int j=i+1;j<N;j++)
{
if(chk==a[j]) //count if equal
count++;
else //as elements are sorted so the numbers will appear together else there would be no more apperances
break;
}
if(i==0)
{
max=count;
element=a[0];
}
else
{
if(max<count)
{
max=count;
element=a[i];
}
}
if(max>(N/2))
{
cout<<element;//value with majority appearances
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.