Problem $3(2+5+5+2=14)$ LANDING THE SLides AT SLIDEWORLD

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 $(ij)$ connects a landing $i$ to a landing $j>i,$ which means that slide $(ij)$ goes from landing $i$

directly to landing $j.$ See Figure $1$ for an example of the possible slides when $n=3.$

Figure $1$: An example of all possible slides when $n=3.$ The slides are $(1,2),(1,3),$ and $(2,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 $(\frac{n}{2})$ 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 $(be)$ or by

taking two slides $(bm)$ and $(me).$ To be clear, a solution of your algorithm is a set of slides.

Using divide$-$and$-$conquer, we will find a solution that uses only $(nlogn)$ 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 ${|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|$ landings and slides connecting the last 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

for solving the recurrence that we have discussed in class.

I can not for the life of me figure out what the pattern is for drawing the slides between landing points. Each slide is one way for clarification.