[goonjv]

Consider the problem of deciding whether or not there was a winner in multi-party election. You are given an array containing n votes (each element of the array is the name of a candidate), and you have to determine if a candidate got more than n/2 votes. In this question, we look at the problem of designing an algorithm (Java code or Pseudo-code) that takes in the array of votes, and returns one of the following:

• The name of the candidate that obtained more than n/2 votes, if there is one, or
• The value false if every candidate obtained less than n/2 votes.

a. Design the algorithm that solves the problem in O(n) time, assuming the array is already sorted by candidate.
b. Show that your algorithm is correct, and runs in O(n) time.

Kindly help me out.. if not, answer the full question..atleast give me enough hints to work upon it.

Another problem i have-
1) For the following program fragment, give the detailed running time analysis and then write down the final answer in Big-O notation:

for ( int j = 0; j < 2*n; j++){
for ( int k = 0; k < n * n * n; k += 3)
sum++;
}

according to me i think-
line 1- 0+(2n+1)+n
line 2- 0+ ( ) + 3
line 3- n^2
Finaly big oh notation- confused

[macosxnerd101]

For your algorithm, you can use a HashMap to relate politicians to the number of votes they received. Every time a politician receives a vote, put the politician and the total number of votes they have into the Map. Since Maps store only unique keys, the new entry for the given politician will overwrite the old one.

As for your second algorithm, the outer loop is n^2, and the inner loop is n^3. For the inner loop, k is incremented by 3 on each iteration, which is a linear value and does not affect T(n). So just multiple n^2 * n^3 to get the Big-O.

[goonjv]

can you tell me how to use hashmap??

[pbl]

http://download.orac...il/HashMap.html

[macosxnerd101]

The Java Data Structures Resource Thread has some snippets which demonstrate Map usage as well.

[cfoley]

Aaah but in this case the array is sorted by candidate so all the votes for a particular candidate will be together. All you need to do is go through the array with a for loop and keep a running total of the number of votes. If the name of the candidate changes, reset the counter or if the counter goes over n/2 you have found the winner!

The hashmap is a better general solution for this though.

[goonjv]

can you tell me how do i make this algorithm? im very confused.. and how do i prove my algorithm is correct and runs in O(n) time?

[macosxnerd101]

Check out KYA's tutorial on Determining the Big-O notation.

[goonjv]

question 1. It's possible to do this with just one loop. I kept two string variables: winner and currentCandidate; two integer variables: winnerVotes and currCandidateVotes. Hint Hint! Remember that the candidates appear in sorted order. Think about keeping a running total for each candidate, which is [possibly] saved when we arrive at a new candidate.

Another thing to note about the requirements , i can't return a boolean value and a string value. But i cn return a string with the value "false." e.g. return "false";
I have understood the concept if im not wrong.. but how do i make the code for this?

[macosxnerd101]

Based on your questions in KYA's thread as well as your questions here, it is obvious you have no intent of writing the code yourself. You MUST show some effort. We have offered valid ideas. We will not simply give you the code.

[goonjv]

im not intentionally, not writing the code. im not really familiar with java coding.. that is the reason im not able to figure out .. atleast provide me the basic steps to do it.. like i know what all variables i shud be taking.. but how to code them? i dnt know

and for second question, the total running time is n^2
*n^3= n^5 ... so which big oh notation would that be?

[goonjv]

k i have tried to do the pseudo-code, atleast tell me where im wrong ;(

Algorithm WinningCandidate(n,currCandidate): 
Input: An integer winnerVotes and currCandidateVotes
A string variable Winner and currentCandidate
Ouput: The value n
If    currCandiateVotes>n/2
Return currentCandidate
Else 
Return false

[pbl]

goonjv, on 04 April 2011 - 01:38 PM, said:

k i have tried to do the pseudo-code, atleast tell me where im wrong ;(

Algorithm WinningCandidate(n,currCandidate): 
Input: An integer winnerVotes and currCandidateVotes
A string variable Winner and currentCandidate
Ouput: The value n
If    currCandiateVotes>n/2
Return currentCandidate
Else 
Return false

A method can only return ONE type of value. In your code on certain condition you return a String (currentCandidate) on another condition you return a boolean (false)
That can't work
Think of the logic when calling that method
xxx = WinningCandidate(n, candidate);

should xxx be a String or a boolean ?

[goonjv]

yes it should be boolean

[pbl]

goonjv, on 05 April 2011 - 12:23 AM, said:

yes it should be boolean

If you say so. So it can't return currentCandidate.