Exercise 7.8. There are n programs that are to be stored in some order on a computer tape of length `. Associated with each program i is a length `(i), 1 6 i 6 n. Assume that all programs can be stored in the tape (i. e., Pn i=1 `(i) 6 `). To retrieve a particular program from the tape the time needed is proportional to the distance from the beginning of the tape to the position where the program begins plus the length of the program. That is, if the programs are stored in the order I = i1, i2, . . . , in, the time tj needed to retrieve program ij is proportional to P 16k6j `(ik). We assume that all programs are retrieved equally often and hence we want to reduce the mean retrieval time (MRT) which is 1 n ( P 16j6n tj ). Our goal is to find a permutation for the n programs so that when they are stored on the tape in this order the MRT is minimized. Note that minimizing MRT is equivalent to minimizing d(I) = Pn j=1 Pj k=1 `(ik). (a) Consider the following example where we have 3 programs and (l1, l2, l3) = (5, 10, 3). What is the (optimal) ordering of these 3 programs that will minimize the MRT and what is the optimal value of MRT ? (b) Give a greedy algorithm to find the optimal order assuming that we have n programs and length of program i is `i , 1 6 i 6 n. What is the running time of your algorithm? (c) Prove that your greedy algorithm always gives the optimal ordering