# designing an algorithm(java or pseudo code)

Page 1 of 1

## 14 Replies - 7463 Views - Last Post: 05 April 2011 - 12:27 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=225885&amp;s=cbac662a4bf3119ad10911e88e621e42&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

# designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 06:55 PM

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

Is This A Good Question/Topic? 0

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

### #2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11792
• Posts: 44,315
• Joined: 27-December 08

## 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.

### #3 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

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

Posted 03 April 2011 - 08:22 PM

can you tell me how to use hashmap??

### #4 pbl

• There is nothing you can't do with a JTable

Reputation: 8370
• Posts: 31,956
• Joined: 06-March 08

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

Posted 03 April 2011 - 08:26 PM

### #5 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11792
• Posts: 44,315
• Joined: 27-December 08

## 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 cfoley

• Cabbage

Reputation: 2338
• Posts: 4,889
• Joined: 11-December 07

## 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.

### #7 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

## 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 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11792
• Posts: 44,315
• Joined: 27-December 08

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

Posted 04 April 2011 - 09:13 AM

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

### #9 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

## 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?

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11792
• Posts: 44,315
• Joined: 27-December 08

## 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 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 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?

### #12 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

## 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):
A string variable Winner and currentCandidate
Ouput: The value n
Return currentCandidate
Else
Return false

```

### #13 pbl

• There is nothing you can't do with a JTable

Reputation: 8370
• Posts: 31,956
• Joined: 06-March 08

## 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):
A string variable Winner and currentCandidate
Ouput: The value n
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 goonjv

Reputation: -3
• Posts: 21
• Joined: 31-March 11

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

Posted 04 April 2011 - 10:23 PM

yes it should be boolean

### #15 pbl

• There is nothing you can't do with a JTable

Reputation: 8370
• Posts: 31,956
• Joined: 06-March 08

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

Posted 05 April 2011 - 12:27 AM

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

yes it should be boolean

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