• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

I am smart

M

MAME

Banned
But not smart enough...took my Algorithms Analysis final earlier today and I still can't find the answer to this:
Array T of size n ints is considered a majority array if there is an element x in T such that x occurs more than n/2 times in the array. Write an algorithm that is linear time (theta n) that determines if the array is a majority or not. It does not have to be in place.

I made a second array (of size n/2) composed of pairs. One number for the element in T and the second for the number of occurences. I then updated the new array for each value in T and searched through it afterwards to see if any occurence value was > n/2.

Problem is, you have to iterate through the second array n/2 * n/2 = (n^2)/4 times for the worst case. No one in the class got the right answer and so I ask ATOT, how can you do this in linear time?

Example:
If T = (1,1,2,2,2,2,2,2,4,5) then C = {1,2},{2,6},{4,1},{5,1} and my algorithm would return true since 6 > (5 = n/2)
 
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
 
Forgot everything about college level math...
They really aren't useful since most jobs don't use them at all.
 
Originally posted by: marquee
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
Click to expand...

We never even mentioned hashing, though I thought about making a indexing key array as well. It may work, but how do you know which count is related to which element?
 
Originally posted by: MAME
Originally posted by: marquee
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
Click to expand...

We never even mentioned hashing, though I thought about making a indexing key array as well. It may work, but how do you know which count is related to which element?
Click to expand...
You could probably use the ascii value for the the character as a lookup in the array.
 
Originally posted by: KnightBreed
Originally posted by: MAME
Originally posted by: marquee
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
Click to expand...

We never even mentioned hashing, though I thought about making a indexing key array as well. It may work, but how do you know which count is related to which element?
Click to expand...
You could probably use the ascii value for the the character as a lookup in the array.
Click to expand...

No you can't. Otherwise the array will be huge. For example, the number 87423874 in ascii would be a bit too big
 
Originally posted by: MAME
Originally posted by: KnightBreed
Originally posted by: MAME
Originally posted by: marquee
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
Click to expand...

We never even mentioned hashing, though I thought about making a indexing key array as well. It may work, but how do you know which count is related to which element?
Click to expand...
You could probably use the ascii value for the the character as a lookup in the array.
Click to expand...

No you can't. Otherwise the array will be huge. For example, the number 87423874 in ascii would be a bit too big
Click to expand...
Yikes, sorry about that. For some reason I was thinking of an array of chars, not ints. Not sure where I read that.😕
 
If the int has an upper bound k and memory space isn't an issue then using the values directly as indices to a second array of counts will work fine and will work in time in n +2k

- init array a2 to all 0's
- loop thorugh first array i = 1...n, for each a(i) you increment a2( a(i) ) by +1
- search a2 for any value >= n/2.

This is quite practical for short ints (64K values) or if there is some reasonable upper bound / range. Much less practical for 32-bit ints!
 
This'll EAT memory, but here goes (untested / psuedo C code)

int input_array[input_array_items_count];
int count_array[2^(sizeof(int) * 8)];

int k, maxval, maxcount;
maxval = 0;
maxcount = 0;
for (k=0;k<input_array_items_count;k++) {
if ( (++count_array[input_array[k]]) > maxcount) {
maxcount = count_array[input_array[k]];
maxval = input_array[k];
}
}

if ( (maxcount * 2) >= input_array_items_count) {
cout << "Array is a majority array, with " << maxval << " appearing " << maxcount << " times." << endl;
}
else {
cout << "Array is not a majority array." << endl;
}

Assuming that your machine uses 32-bit integers, it'll take 16GB of RAM (2^32 possible values, each of which has a 32-bit int counter)
to run. But, it has the benefit of only taking one pass through the array! AFAICT, it's theoretically a very fast method 🙂

If your array has definite boundaries as far as input values (IE only accepting a short instead of a full int), it becomes much
more reasonable as far as computing power goes.
 
Originally posted by: DaveSimmons
If the int has an upper bound k and memory space isn't an issue then using the values directly as indices to a second array of counts will work fine and will work in time in n +2k

- init array a2 to all 0's
- loop thorugh first array i = 1...n, for each a(i) you increment a2( a(i) ) by +1
- search a2 for any value >= n/2.

This is quite practical for short ints (64K values) or if there is some reasonable upper bound / range. Much less practical for 32-bit ints!
Click to expand...

well since 2K > n, it's not linear 🙂

The solution she was looking for was more for any ints.

That's how other people did it in the class. They made a new array based on the max value of the first array. But lets say you have an array size 2 with elements 1 and 1,000,000,000. Now you're talking about making a HUGE array and then having to run down it again just to get the the last element.
Not to mention it would totally break if there are negative values in it!
 
Originally posted by: DerMonkeyhauser
This'll EAT memory, but here goes (untested / psuedo C code)

int input_array[input_array_items_count];
int count_array[2^(sizeof(int) * 8)];

int k, maxval, maxcount;
maxval = 0;
maxcount = 0;
for (k=0;k<input_array_items_count;k++) {
if ( (++count_array[input_array[k]]) > maxcount) {
maxcount = count_array[input_array[k]];
maxval = input_array[k];
}
}

if ( (maxcount * 2) >= input_array_items_count) {
cout << "Array is a majority array, with " << maxval << " appearing " << maxcount << " times." << endl;
}
else {
cout << "Array is not a majority array." << endl;
}

Assuming that your machine uses 32-bit integers, it'll take 16GB of RAM (2^32 possible values, each of which has a 32-bit int counter)
to run. But, it has the benefit of only taking one pass through the array! AFAICT, it's theoretically a very fast method 🙂

If your array has definite boundaries as far as input values (IE only accepting a short instead of a full int), it becomes much
more reasonable as far as computing power goes.
Click to expand...


Read above 🙂
That's not linear in relation to n since n may only be a few items. And it won't work with negatives 😉
 
Originally posted by: KnightBreed
Originally posted by: MAME
Originally posted by: KnightBreed
Originally posted by: MAME
Originally posted by: marquee
hmm

create a hash table where the hash function is just h(n) = n.
count the number of collisions for each number in T
you have to iterate through T once.. so O(n)
iterating through the count table is linear as well.

that seemed too simple, is there a hole in my solution?
Click to expand...

We never even mentioned hashing, though I thought about making a indexing key array as well. It may work, but how do you know which count is related to which element?
Click to expand...
You could probably use the ascii value for the the character as a lookup in the array.
Click to expand...

No you can't. Otherwise the array will be huge. For example, the number 87423874 in ascii would be a bit too big
Click to expand...
Yikes, sorry about that. For some reason I was thinking of an array of chars, not ints. Not sure where I read that.😕
Click to expand...

Haha, it's cool though. Good idea!
 
or this (in java terms):

int majority(int array[]) {
int x = median(array); // runtime in O(n)
int counter=0;
for i=1..array.size {
if (array=x) counter++;
}
if (counter>array.size/2) return x;
else return -1;
}

 
well since 2K > n, it's not linear

The solution she was looking for was more for any ints.

That's how other people did it in the class. They made a new array based on the max value of the first array. But lets say you have an array size 2 with elements 1 and 1,000,000,000. Now you're talking about making a HUGE array and then having to run down it again just to get the the last element.
Not to mention it would totally break if there are negative values in it!
Click to expand...
true except the last part, it's easy to map a range of integers [ a, b ] to a counting array of size 1+(b-a).

d'oh! Any kind of sorting / tree-building approach would be at least n log2 n .

When you get the answer, post it here.
 
Originally posted by: DaveSimmons
well since 2K > n, it's not linear

The solution she was looking for was more for any ints.

That's how other people did it in the class. They made a new array based on the max value of the first array. But lets say you have an array size 2 with elements 1 and 1,000,000,000. Now you're talking about making a HUGE array and then having to run down it again just to get the the last element.
Not to mention it would totally break if there are negative values in it!
Click to expand...
true except the last part, it's easy to map a range of integers [ a, b ] to a counting array of size 1+(b-a).

d'oh! Any kind of sorting / tree-building approach would be at least n log2 n .

When you get the answer, post it here.
Click to expand...

nlogn by mergesort first and then using sorted values to find the longest subset of them of length > n/2. But that's as close as you get! I'll get the answer from the teacher and let you know
 
Originally posted by: DaveSimmons
Originally posted by: scottdog81
solution
Click to expand...
<keanu> whoa! </keanu>

That is very clever. It's a pretty tough question to ask on a test though, unless it was in the assigned reading.
Click to expand...

Tell me about it. It might be from the reading, I wouldn't know. I never opened the book the entire semester. She was upset no one talked in class on e day so maybe she took something really hard striaght from the book, dunno.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top