Algorithm

[bags]

32. Consider the following two problems.

Nearest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the

numbers that are closest in value to each other.

Farthest Neighbors: Given an unsorted array of n floating-point numbers as input, return two of the

numbers that are farthest in value from each other.

Assume that the only operations allowed on the data are

• comparing the values of two entries in the array and identifying the larger value;

• comparing the distance between two array entries (the absolute value of the difference between the two

array entries) with the distance between two other array entries;

• swapping two entries in the array.

Further assume that each allowed operation has unit cost. What are the worst-case optimal asymptotic running

times for algorithms that solve the two problems?

Nearest Neighbors Farthest Neighbors

(A) Theta(n log n) Theta(n)

(B) Theta(n log n) Theta(n log n)

© Theta(n^2) Theta(n)

(D) Theta(n^2) Theta(n log n)

(E) Theta(n^2) Theta(n^2)

 

How to solve this?

Ans :A

[m0pilot]

Hi bags,

 

for the Farthest Neighbors, simply go through the array in order and keep track of the largest and smallest values so far encountered (this can be done using operation 1 and takes linear time in each step). Once you're done you have the largest and smallest number in the array, which are by definition the farthest away from one another. Clearly this can be done in O(n) time.

 

For the nearest neighbor, the solution is similar, except you have to sort the array first - this can be done on O(n log n) time with the operations provided using e.g. heapsort. Then like before you go through the array in order, and keep track of the shortest distance between any two adjacent nodes. Again this will take O(n) time. So in total you need O((n log n) + n) = O(n log n) time.

 

You could now check that indeed no algorithm could do better than that - but these are already the smallest value given, so you can skip that step - assuming that the answers given include the correct one, it has to be (A). (And indeed, Farthest Neighbor cannot conceivably be solved in less than O(n) time as you have to look at each element at least once. Nearest neighbor is less straightforward, but I guess an argument similar to the proof that any comparison sort needs at least O(n log n) time might work.)

 

 

So, are you doing the test next week as well?

 

 

Good luck,

Matt