Reference no: EM131184637
A community of N pirates has recently conducted an election to choose their new leader. All pirates vote, and any pirate may run as a candidate. There is no preferential system, each pirate simply writes the number of their preffered leader on the ballot paper. If a single pirate gets more than 50% of the votes, then that pirate is declared the new leader. If no pirate gets more than 50% of the votes, then the old leader is retained. N pirates have voted, and their choices have been collected in an array A. Your task is to determine whether there will be a new leader and, if there will, who the new leader will be.
For example, given the array 4, 4, 7, 1, 7, 7, 2, 7, 7 pirate 7 has 5 votes out of 9, and becomes the new leader, whereas given the array 4, 4, 7, 1, 4, 7, 2, 4 pirate 4 has 4 votes out of 8 but doesn't manage to get over 50% so the old leader 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 candidate that could possibly have more than 50% of the votes. To find a possible winner in the array, A, create a second array, 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 a possible winner on the array B, stopping when the array has less than 2 elements. If a possible winner has been found, scan through the array and count the number of votes received by the possible winner. If the possible winner has more than N/2 votes, print the possible winner out as the winner. If no possible winner is found, or the possible winner does not have enough votes, print that the old leader is retained.
(a) What is the worst case space complexity for this algorithm (consider the array(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 all function calls.
(d) What problem occurs when the array size is odd? Propose a fix for this problem, or describe an alternative algorithm.
(e) What are the (Big-Oh) time and space1 complexities of your new algorithm? Compare this to the previous algorithm and explain under what circumstances would you use one algorithm or the other?
|
What affect will that have on the performance of the filter
: When calculating the attenuation of an L-filter, it is usually assumed that the circuit into which the filter is inserted has a low source impedance and a high load impedance.
|
|
Identify disorder that usually diagnosed first in childhood
: Identify a disorder that is usually diagnosed first in childhood/adolescence, and provide a thorough explanation of the characteristics of the disorder.
|
|
Which has the largest effect on the maximum value
: Which has the largest effect on the maximum value of the common-mode conducted emission from a switched-mode power supply, the switching frequency or the rise time of the switching transistor?
|
|
How decision help and potentially harm african-american
: The Peckham Decision dictates that school psychologists in California may not use intelligence testing on African-American children to determine special-education placement. This is due to a cultural bias because a large percentage of African-Amer..
|
|
What is the worst case space complexity for algorithm
: What is the worst case space complexity for algorithm - and Give the O, ? and, if possible, T time complexities for this algorithm. Explain your reasoning.
|
|
Is there significant safety concerns for decreased mobility
: Create a list of injuries that would adversely affect activities for daily living (ADLs) Is there significant safety concerns for decreased mobility
|
|
What is the accounts receivable turnover for danielle
: The financial statements of Danielle Manufacturing Company report net sales of $750,000 and accounts receivable. What is the accounts receivable turnover for Danielle?
|
|
What two parameters of a switched-mode power supply
: What two parameters of a switched-mode power supply, other than the switching frequency and peak current rating, have the most effect on the differential-mode conducted emission?
|
|
Did the authors use the correct statistical test
: Did the authors use the correct statistical test? In other words, what was their rationale for using this test (i.e., were the variables discrete or continuous and was the test appropriate for this type of data?)
|