2. Consider the area enclosed by the x-axis, the line r = 1, and the curve...

 

Transcribed Image Text:

2. Consider the area enclosed by the x-axis, the line r = 1, and the curve y = r. Assume that n points are uniformly distributed randomly inside it. (The n points can be represented by n pairs of real numbers (1.91). (2.92)..... (xn. Yn).) (a) Show that you can sort the points by their distance to the y-axis in average-case linear time. You can assume that bucket sort works in average-case linear time. (b) Give the pseudo-code for your algorithm. 2. Consider the area enclosed by the x-axis, the line r = 1, and the curve y = r. Assume that n points are uniformly distributed randomly inside it. (The n points can be represented by n pairs of real numbers (1.91). (2.92)..... (xn. Yn).) (a) Show that you can sort the points by their distance to the y-axis in average-case linear time. You can assume that bucket sort works in average-case linear time. (b) Give the pseudo-code for your algorithm.