$[$Landing the slides at SlideWorld$]2+5+5+2$

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 Figure $1$ for an example of the possible slides when

n $=3.$

$5$

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 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 $($b $->$ e$)$ or by taking two slides $($b $->$ m$)$ and $($m $->$ e$).$

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 $\backslash$Theta $($n log n$)$

slides while ensuring that any customer can get from any landing b to any

landing e $>$ b using at most two slides.

$1.$ For the base cases n $=1,2,$ design a system using at most $1$ slide.