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,

2
Contributors
1
2
Views
10 Years
Discussion Span
Last Post by Rashakil Fol

You have interpreted the problem correctly. Your instructor is a complete idiot with a personality disorder.

(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."

I would add and remove commas: "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 of the array."

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.