[Cs4800] Interview question hypotheses

[Karl Lieberherr]

Based on an experience by one of you, I have created "Interview Question"
hypotheses.
If you have not chosen yet your hypothses, you can choose this one and
prepare for your next interview.

I added it also to the hypotheses market directory.

A reminder: The textbook is self contained. If you encounter a name that you
don't remember, look it up in the index.

We use now a slightly different submission procedure: As before, you bring a
printed copy to the class in addition, you download your protocols to
Blackboard so that we can share them:

CS4800 31223 ALGORITHMS & DATA SEC 01 - SPRING 2010
(CS4800.31223.201030)<http://blackboard.neu.edu/bin/common/course.pl?course_id=_127537_1>>
ASSIGNMENTS

-- Karl

Consider this problem:

Find 3 numbers with sum 0 from a list of n numbers.
i.e. given a list of n numbers, you have to find three numbers
a,b,c such that a+b+c=0 or prove that such a combination does not
exist.

Hypothesis 1:
I claim to have an algorithm A that is faster than enumerating all
triples which is O(n^3). I claim my algorithm to be O(log(n) * n^2).

Hypothesis 2:
I claim to have an algorithm A that is faster than enumerating all
triples which is O(n^3). I claim my algorithm to be O(n^2) assuming
answering the question: "is an element in the list?"
takes constant time (after a O(n) preprocessing step).

Hypothesis 3:
I claim to have an algorithm A that is faster than enumerating all
(n choose 3) triples.
I claim my algorithm, after some preprocessing that takes less than O(n^2),
to check only ((n/2) choose 2) pairs.

For all three hypotheses:

The problem is the algorithm A.
The solution is a list of n numbers.

Refutation protocol:
The hypothesis is refuted if the algorithm A gives the wrong answer
or if it executes more steps than claimed.
-------------- next part --------------
HTML attachment scrubbed and removed