My instructor has given us an assignment which *should* be relatively easy except for the fact that the instructor's instructions are not clear, sometimes ungrammatical, and she refuses to answer any questions or fix any mistakes. Here are the instructions for the assignment:
"Let A[1..n] be of n elements. Let k belong to N-{0, 1}. We are interested in an element x which satisfies |{ i | A = x}| > n/k.
(a) Show that any algorithm that can decide whether a given array includes such an element, and if so find it must check all the elements in the array."
Can anyone tell me what this means?
My interpretation (which the instructor says is wrong) follows:
I have interpreted the first part to mean that given some list of n items and a natural number k, such that k > 1, we are interested in whether the list has some x n/k times, i.e. this condition may be understood as follows: let S be the set of all list index values such that for every i in S, A = x. For the condition to be satisfied, the cardinality of S must be greater than the value given by n/k. The expression n/k may be understood as the length of the list A divided by some natural number k (where k > 1).
However, my instructor has very unhelpfully told me that I am not correct. And given some of the other parts of the assignment (namely that I should write an algorithm with worst case O(n lg n) time without any assumption of an order relation between items in the list), my interpretation is likely wrong.
My basic (naive) C implementation follows, which doesn't include any optimizations:
int find_x (int A[], int k, int n)
{
int i;
int j;
int r;
int d;
d = n/k;
for (i=0; i<n; i++)
{
r=0;
for (j=0; j<n; j++)
{
if (A[i] == A[j])
r++;
if (r>d) return 1;
}
}
return 0;
}I appreciate any help (since none is forthcoming from my instructor) that anyone can give me. She even argued that the sentence following (a) in the assignment is grammatical!
Cheers,
Madcapjack[/tex]
