14 Replies - 4896 Views - Last Post: 05 April 2011 - 12:27 AM Rate Topic: -----

#1 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10664
  • View blog
  • Posts: 39,608
  • 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.
Was This Post Helpful? 2
  • +
  • -

#3 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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??
Was This Post Helpful? 0
  • +
  • -

#4 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: designing an algorithm(java or pseudo code)

Posted 03 April 2011 - 08:26 PM

http://download.orac...il/HashMap.html
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10664
  • View blog
  • Posts: 39,608
  • 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. :)
Was This Post Helpful? 1
  • +
  • -

#6 cfoley  Icon User is offline

  • Cabbage
  • member icon

Reputation: 2045
  • View blog
  • Posts: 4,233
  • 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.
Was This Post Helpful? 0
  • +
  • -

#7 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10664
  • View blog
  • Posts: 39,608
  • 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.
Was This Post Helpful? 1
  • +
  • -

#9 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10664
  • View blog
  • Posts: 39,608
  • 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.
Was This Post Helpful? 0
  • +
  • -

#11 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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?
Was This Post Helpful? -1
  • +
  • -

#12 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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): 
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


Was This Post Helpful? 0
  • +
  • -

#13 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: designing an algorithm(java or pseudo code)

Posted 04 April 2011 - 02:54 PM

View Postgoonjv, 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 ?
Was This Post Helpful? 0
  • +
  • -

#14 goonjv  Icon User is offline

  • New D.I.C Head

Reputation: -3
  • View blog
  • 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
Was This Post Helpful? 0
  • +
  • -

#15 pbl  Icon User is offline

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

Reputation: 8342
  • View blog
  • Posts: 31,880
  • Joined: 06-March 08

Re: designing an algorithm(java or pseudo code)

Posted 05 April 2011 - 12:27 AM

View Postgoonjv, on 05 April 2011 - 12:23 AM, said:

yes it should be boolean

If you say so. So it can't return currentCandidate.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1