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

# designing an algorithm(java or pseudo code)

Page 1 of 1## 14 Replies - 7408 Views - Last Post: 05 April 2011 - 12:27 AM

##
**Replies To:** designing an algorithm(java or pseudo code)

### #2

## Re: designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 07:04 PM

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.

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.

### #3

## Re: designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 08:22 PM

can you tell me how to use hashmap??

### #4

## Re: designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 08:26 PM

### #5

## Re: designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 08:30 PM

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

### #6

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 02:22 AM

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.

The hashmap is a better general solution for this though.

### #7

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 09:12 AM

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?

### #8

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 09:13 AM

### #9

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 09:34 AM

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?

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?

### #10

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 09:41 AM

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.

### #11

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 09:48 AM

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?

and for second question, the total running time is n^2

*n^3= n^5 ... so which big oh notation would that be?

### #12

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 11:38 AM

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

### #13

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 02:54 PM

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 ?

### #14

## Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 10:23 PM

yes it should be boolean

### #15

## Re: designing an algorithm(java or pseudo code)

Posted 05 April 2011 - 12:27 AM

Page 1 of 1