Homework answers / question archive / Consider the the one-dimensional closest pair problem, defined as follows: Given a set n points x1, x2,

Consider the the one-dimensional closest pair problem, defined as follows: Given a set n points x1, x2,

Psychology

Share With

Consider the the one-dimensional closest pair problem, defined as follows: Given a set n points x1, x2, . . . , xn on R, give the minimum distance between any two points?

Ques 1. Give a brute-force algorithm to solve this problem, with time complexity analysis.

Ques 2. Give a faster algorithm than the brute-force method, with time complexity analysis. You may call algorithms covered in class or CSC212 without having to explicitly write them.

Ques 3. Consider the problem of finding the maximum distance between two points. Does it have an even faster algorithm than the minimization version? If so, give the algorithm and time analysis. If not, explain why