A community of N pirates has recently conducted an election to choose their newl

Question

A community of N pirates has recently conducted an election to choose their newleader. All piratesvote, and any pirate may run as a candidate. There is no preferential system,each pirate simplywrites the number of their preffered leader on the ballot paper. If a singlepirate gets more than50% of the votes, then that pirate is declared the new leader. If no pirate getsmore than 50% of thevotes, then the old leader is retained.N pirates have voted, and their choices have been collected in an array A. Yourtask is to determinewhether there will be a new leader and, if there will, who the new leader willbe. For example, giventhe array4, 4, 7, 1, 7, 7, 2, 7, 7pirate 7 has 5 votes out of 9, and becomes the new leader, whereas given thearray4, 4, 7, 1, 4, 7, 2, 4pirate 4 has 4 votes out of 8 but doesn t manage to get over 50% so the oldleader is retained.Your team has proposed the following algorithm to determine which, if any,candidate wins:First, a possible winner must be found. This possible winner the only candidatethat could possiblyhave more than 50% of the votes. To find a possible winner in the array, A,create a secondarray, B. Compare A[0] and A[1]. If they are equal, put one of them in B;otherwise do nothing.Then compare A[2] and A[3]. Again if they are equal, add one of these to B;otherwise do nothing.Continue like this until the entire array A has been used. Recursively find apossible winner on thearray B, stopping when the array has less than 2 elements. If a possible winnerhas been found, scanthrough the array and count the number of votes received by the possible winner.If the possiblewinner has more than N/2 votes, print the possible winner out as the winner. Ifno possible winneris found, or the possible winner does not have enough votes, print that the oldleader is retained.(a) What is the worst case space complexity for this algorithm (consider thearray(s) B only)?Explain your reasoning.(b) Give the O, ? and, if possible, T time complexities for this algorithm.Explain your reasoning.(c) Why does this algorithm work? You may assume the array size is even for allfunction calls.(d) What problem occurs when the array size is odd? Propose a fix for thisproblem, or describean alternative algorithm.(e) What are the (Big-Oh) time and space1complexities of your new algorithm? Compare this tothe previous algorithm and explain under what circumstances would you use onealgorithm orthe other?

Explanation / Answer

Let' consider the given algorithm:

1. First, take pairs of element as A[0] and A[1] ; A[2] and A[3] ; and so on...

2. Compair the pairs

3. If they are same add them to secondary array.

4. Else do nothing.

5. Recursively repeat above steps for generated secondary array, until only one element left.

6. Now count the votes in favour of the element, if >50% new leader, else old leader.

(a) What is the worst case space complexity for this algorithm (consider thearray(s) B only)?Explain your reasoning.

The worst case of space complexity will occur if for each compqarision we do we need to add element in secondary array.

Let's take an example: 7, 7, 7, 7, 7, 7, 7, 7.(8 votes all 7)

Now on comparing and forming second array: A[0]=7, A[1]=7 => B[0]=7, and so on...

Thus the B-array foormed => 7, 7, 7, 7.

Now recursively again performing operatiions on B-array

The new array generated => 7, 7.

Again performing as still 2 elements left. New array => 7.

This completes the algorithm and we count 7 in A-array = 8/8, hence 7 is the winner.

Hence from above trend we can say that after each iteration the number elements is half.

Thus space complexity (two cases)=>

(i) If only same B-array is maintained in each iteration. => O(n/2) (As a new space is only formed in first iteration).

(ii) If every iteration new array is created => n/2 + n/4 + n/8 + ... + 1. => O(n).

Thus in both cases space complexity is O(n).

(b) Give the O, ? and, if possible, T time complexities for this algorithm.Explain your reasoning.

The time complexity can calculated as from above example,

In first iteration we compare total n elements, thus complexity for first iteration is kn.

Similarly for next iteration there are n/2 elements in comparision, thus complexity for second iteration is kn/2.

and so on..

Thus total time complexity => O(2n). Sum of individual.

Thus, time complexity for given algorithm is O(n).

(c) Why does this algorithm work? You may assume the array size is even for all function calls.

This algorithm only works if size of array is n=2k, thus for any other sizes we have to assume things, this can be tackle using two ways:

i. push the vote directly.

ii. Ignore the vote.

This algorithm isn't the best but it works only for certain cases where no. of element is a factor of 2, as only that votes goes to next iteration which come in pairs that also in even-odd places (A[0]-A[1]). So every time we iterate only those votes are counted which come in pair and other votes are discarded, after many iterations only those elements left which have most votes, and hence the result, can be achieved.

This algorithm works, as if there is a majority, then it is confired that at least one pair is atleast same, thus going to next iteration.

Ex: 7, 4, 7, 1, 7, 3, 7. In second interation no element passes. Thus, old leader retained.

As you can see 7 has 50% votes, hence 7 does not win, and old leader retained.

Ex: 7, 7, 4, 7, 1, 7.

Now in, above iteration yields 7, and its votes count up to 66.66%, hence new leader.

Thus algorithm works as you can see from above example, but only if n = 2k.

(d) What problem occurs when the array size is odd? Propose a fix for thisproblem, or describe an alternative algorithm.

When odd elements appear, we cannot compare the last element as we cannot find it's paired element. This could be tackled using:

i. push the vote directly.

ii. Ignore the vote.

Alternative algorithm is to maintain a 2*voted members array or a map(if you know about it).

Where, the M[0][] will conatin the member which stands in election and M[1][] holds no. of votes he recieved.

Then we can check for no.of votes greater than 50%, thus resulting in answer.

Ex: Votes: 4, 4, 7, 1, 7, 7, 2, 7, 7. Odd elements thus above given algo fails.

But alternative algo:

M=> {4:2; 7:5; 1:1; 2:1} hence, this specifies that 4 received 2 votes, 7 received 5 votes and so on.

Hence 7 with more the 50% votes becommes new leader.

Alternative algorithm works in each and every case, no exception.

(e) What are the (Big-Oh) time and space1complexities of your new algorithm? Compare this tothe previous algorithm and explain under what circumstances would you use onealgorithm orthe other?

Time Complexity: O(n) : As we are iterating A-array or votes array once for n-elements and then checking no. of votes array once, both in O(n) complexity, thus combined to O(n).

Space Complexity: O(n) :This can occur when each vote is different that is each person has one vote, thus the new array required is 2*n size.

Now, as we can see comlexities are almost similar but, the first one being a bit more fast.

Thus, use first one if n=2k, else use alternative algorithm.

This completes my answer, for queries do post in comment section.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.