designing an algorithm(java or pseudo code)
Page 1 of 114 Replies  4153 Views  Last Post: 05 April 2011  12:27 AM
#1
designing an algorithm(java or pseudo code)
Posted 03 April 2011  06:55 PM
• 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 BigO 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
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
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 BigO.
#3
Re: designing an algorithm(java or pseudo code)
Posted 03 April 2011  08:22 PM
#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
#6
Re: designing an algorithm(java or pseudo code)
Posted 04 April 2011  02:22 AM
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
#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
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
#11
Re: designing an algorithm(java or pseudo code)
Posted 04 April 2011  09:48 AM
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
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:
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
#15
Re: designing an algorithm(java or pseudo code)
Posted 05 April 2011  12:27 AM
