I didn't get why this problem is NP...Can you give me more details..
I think 0/1 kanpsack should work for this problem...
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this
0/1 kanpsack is NP problem ;-)
On 11/1/06, cooljunta [EMAIL PROTECTED] wrote:
I didn't get why this problem is NP...Can you give me more details..I think 0/1 kanpsack should work for this problem...
--~--~-~--~~~---~--~~
You received this message because you are
you make no mention of time requirements, so you can do the following:
Since it seems you are using the first element as the root of the tree,
you can partition the list into two separate lists on either side of
the pivot - do the same on the other list, if the sub-lists have equal
numbers do
Dear all,
I have worked out the following algorithm for finding the majority
element(the element occurs more than n/2 times) of an array of n
elements :
Suppose that I have a subroutine that could find the median of an array
in theta(n) time, then:
the algorithm will be:
1.find the median of
I think the straightforward method it as followed:
Suppose n = 2, m = 7
Check the 2-th ,4-th,6-th elements
For general n m, there will be at most m/n such elements, by check them
one by one, u just need
O(m/n * m) time
If n = theta(m), of course, the algorithm is O(m).
Otherwise, if n m,
I think there should be an algorithm that uses the theta(n) finding
median subroutine. Somehow we divide and conquer, i.e. some
generalization of n/2 majority element case.
Thanks
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the
