points$)$ There are $\text{'}$n$\text{'}$ programs that are to be stored on a computer tape of total length $\text{'}$X$\text{'}.$ Associated with each

programi is length Li $1<=$i $<=$n$.$ Clearly all the programs can be stored on the tape if and only if the sum of the lengths of

the programs is at most X$.$ We shall assume that whenever a program is to be scanned to on the tape, the tape is initially

positioned at the front. Hence, if programs are stored in the order program$1,$program$2,$program$3,...$programn the time tj

needed to scan to programj is proportional to how far along the tape programj is$,$ which depends on the lengths of the

programs before programj on the tape. For example, if the programs are stored on the tape in the following order

program$4,$ program$1,$ program$2,$ program$3$ ; then the time t$4$ needed to scan to the fourth program in the list $($program$3)$ is

proportional to L$4+$L$1+$L$2.$ If all programs are scanned to equally often $($each program has the same chance of being

scanned to$,$ then the expected or mean retrieval time $($MRT$)$ is

In the optimal storage on tape problem, we are required to find a permutation $($ordering$)$ for the $\text{'}$n$\text{'}$ programs so that when

they are stored on the tape the MRT is minimized.

$4$a$)$ Give an example of three programs $($n$=3)$ with different integer lengths $($L$1,$L$2,$L$3).$ Show all the permutations

$($orderings$)$ possible to store the programs on the tape. Calculate the mean retrieval time for each permutation and find the

optimal ordering. This should give you an indication of a possible greedy choice strategy.

$4$b$)$ Discuss and prove optimal substructure for the optimal storage on tape problem.

$4$c$)$ Discuss and prove the greedy choice property for the optimal storage on tape problem.