(Solved): answer in python Problem 2: Fast k-NN in 1D. In Problem 1, even if we use quickselect, we need to do ...

Problem 2: Fast k-NN in 1D. In Problem 1, even if we use quickselect, we need to do a whole pass over the training dataset for each test point. This means that it requires \( 0(n) \) cost per prediction where \( n \) is the number of training points and it is not realistic in practice where we wish to run \( \mathrm{kNN} \) in millions of test points. One way to go about this is preprocessing the training data. Suppose input data is 1-dimensional floating numbers i.e. X_train is a list of numpy floats. If you sort X_train, you can run k-NN in logarithmic time via bisection search. Your task is to implement \( k-\mathrm{NN} \) classification on a test dataset \( \mathrm{X}_{-} \)test by first sorting \( X_{-} \)train, \( y_{-} \)train and then running \( \mathrm{k}-\mathrm{NN} \) over \( \mathrm{X}_{-} \)test to output list of predictions \( \mathrm{Y}_{-} \)pred. Unlike Problem 1 where \( x_{-} \)test is a single input, \( X_{-} \)test might contain millions of inputs and your output \( Y_{-} \)pred should be a list with same size. The distance between two numbers is their absolute difference, i.e. dist \( (x 1, x 2)=|x 1-x 2| \). Remark: You need to implement everything yourself however you can use codes from earlier HWs. def fast_kNN (k, \( X_{-} \)train, \( y_{-} \)train, \( X_{-} \)test): return Y_pred