Problem 6. Professor I. M. Nuts of the Math Department is scratching his head over the...

Transcribed Image Text:

Problem 6. Professor I. M. Nuts of the Math Department is scratching his head over the following problem. Given two sequences of numbers X (x1,...,xn) and Y = (y₁,..., yn) he must find the m≤ √n largest values of the sums xi + Yj, 1 ≤ i, j≤n in SORTED ORDER (smallest to largest). One may assume that m≤ √√n but one must not assume that m is a constant. The proposed algorithm should have worst-case running time that is o(n²). He requests the assistance of the CS Department in dealing with this problem. (a) Give an algorithm whose worst-case running time is o(n²) that solves this problem; an (n²2) time algorithm will not get you any points. (b) Does there exist an algorithm whose worst-case performance is O(n) ? Explain, i.e. show/prove that such an algorithm does not exist or give the algorithm and analyze its performance, if such an algorithm exists. Example. If X = (2,0, -2, -3, 1, 100, 290, 300, 4) and Y (-20, -19,-8, -200, 11, 1, 10, -7,0) and m = 3 then the answer is (301, 310, 311). Note that 301 can result either as the sum of 290 + 11 or 300 + 1. = - Problem 6. Professor I. M. Nuts of the Math Department is scratching his head over the following problem. Given two sequences of numbers X (x1,...,xn) and Y = (y₁,..., yn) he must find the m≤ √n largest values of the sums xi + Yj, 1 ≤ i, j≤n in SORTED ORDER (smallest to largest). One may assume that m≤ √√n but one must not assume that m is a constant. The proposed algorithm should have worst-case running time that is o(n²). He requests the assistance of the CS Department in dealing with this problem. (a) Give an algorithm whose worst-case running time is o(n²) that solves this problem; an (n²2) time algorithm will not get you any points. (b) Does there exist an algorithm whose worst-case performance is O(n) ? Explain, i.e. show/prove that such an algorithm does not exist or give the algorithm and analyze its performance, if such an algorithm exists. Example. If X = (2,0, -2, -3, 1, 100, 290, 300, 4) and Y (-20, -19,-8, -200, 11, 1, 10, -7,0) and m = 3 then the answer is (301, 310, 311). Note that 301 can result either as the sum of 290 + 11 or 300 + 1. = -

Answer rating: 100% (QA)

a Algorithm 1 Initialize a twodimensional array Anm where n is the size of both X and Y and m is the ... View the full answer