= Problem 4. (2 +5+ 8 + 5 = 20 points) Landing the slides at Slide World You have won a contract for the design of a new theme park, SlideWorld. The primary attraction of the park is to consist of n landings, numbered 1 through n, which will be connected by a number of slides. Each slide (i j) connects a landing i to a landing j>i, which means that slide (i j) goes from landing i directly to landing j. See below for an example of the possible slides when n= - 3. 3 Slideworld wants to let the customers begin their trip at any landing b and end at any other landing e > b. Putting in all the (m) slides in the park is going to break the bank. So you have been asked to determine a set of slides so that any customer can get from any landing b to any landing e > b using at most two slides. That is, it should be possible to get from any b to any e > b either by taking a direct slide (b e) or by taking two slides (b m) and (m e). A solution to your algorithm is a set of slides. Using divide-and-conquer, we will find a solution that uses only (nlog n) slides while ensuring that any customer can get from any landing b to any landing e > b using at most two slides. (a) For the base cases n = 1,2 design a system using at most 1 slide. (b) For n > 2 we will use divide-and-conquer. Assume that we already put in place slides connecting the first [n/2] landings and slides connecting the last [n/27 landings so that if i and j both belong to the same half, we can get from i to j in at most 2 slides. Show how to add (n) additional slides so that if i is in the first half and j is in the second half we can get from i to j using only two slides. (c) Using part (b), write (in pseudocode) a divide-and-conquer algorithm that takes as input the number of landings n and outputs the list of all the slides used by your attraction. (d) Write the recurrence for the number of slides your solution uses and solve it. You may use any method to solve the recurrence relation. = Problem 4. (2 +5+ 8 + 5 = 20 points) Landing the slides at Slide World You have won a contract for the design of a new theme park, SlideWorld. The primary attraction of the park is to consist of n landings, numbered 1 through n, which will be connected by a number of slides. Each slide (i j) connects a landing i to a landing j>i, which means that slide (i j) goes from landing i directly to landing j. See below for an example of the possible slides when n= - 3. 3 Slideworld wants to let the customers begin their trip at any landing b and end at any other landing e > b. Putting in all the (m) slides in the park is going to break the bank. So you have been asked to determine a set of slides so that any customer can get from any landing b to any landing e > b using at most two slides. That is, it should be possible to get from any b to any e > b either by taking a direct slide (b e) or by taking two slides (b m) and (m e). A solution to your algorithm is a set of slides. Using divide-and-conquer, we will find a solution that uses only (nlog n) slides while ensuring that any customer can get from any landing b to any landing e > b using at most two slides. (a) For the base cases n = 1,2 design a system using at most 1 slide. (b) For n > 2 we will use divide-and-conquer. Assume that we already put in place slides connecting the first [n/2] landings and slides connecting the last [n/27 landings so that if i and j both belong to the same half, we can get from i to j in at most 2 slides. Show how to add (n) additional slides so that if i is in the first half and j is in the second half we can get from i to j using only two slides. (c) Using part (b), write (in pseudocode) a divide-and-conquer algorithm that takes as input the number of landings n and outputs the list of all the slides used by your attraction. (d) Write the recurrence for the number of slides your solution uses and solve it. You may use any method to solve the recurrence relation