Reference no: EM131171557
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?
|
How important are stakeholder relationship
: Organizations must ensure a proper balance in differing stakeholder values by exercising good corporate citizenship. Companies should first take inventory of why they are vested in the company and how well they align or misalign with the company's..
|
|
Group policy on windows servers
: 1. What are some of the advantages of using Group Policy? What are some of the things that can be managed with it?
|
|
Evaluate strategies for contract negotiation
: Synthesize knowledge and concepts from advanced practice nursing with supporting disciplines as a foundation for APN/specialty nurse practitioner practice that is culturally competent and population-specific
|
|
Audience visualize how the security team functions
: Create a 4- to 5-slide narrated presentation in response to the request from the CEO. Include an organizational chart to help the audience visualize how the security team functions. Include detailed speaker notes or transcription of narration.
|
|
Election to choose new leader
: 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..
|
|
The economic argument for protectionism
: The economic argument for protectionism is that it preserves jobs, protects a nation's political security, discourages dependency on other countries, and:
|
|
Reflect the chicanao latino experience in the local society
: Write an outline for persuasive speech (choose any essay that reflect the topics listed below and write an outline on). The topic for the persuasive speech outline must reflect the Chicana/o Latino Experience in the local and global society.
|
|
Petty cash register available to record all outflow of funds
: Which one of the following is a key report that a new business owner should be prepared to generate? Which of the following accounts requires both a cash register and a petty cash register available to record all outflow of funds? A small business ow..
|
|
How do you plan to deliver training: face-to-face or online
: Imagine that you must make a proposal to your supervisor to create a training workshop for new hires in your field to help them acclimate to their jobs. Write a 500-word essay explaining your proposal to a colleague. Include a description of the p..
|