Explain optimal storage on tapes and find the optimal order for given instance.

n = 3, and (1, 12, 13) = (5, 10, 3).

1. Given n programs to be stored on tape, the lengths of these programs are i1, i2….in respectively. Suppose the programs are stored in the order of i1, i2…in. 2 We have a tape of length L i.e. the storage capacity of the tape is L. We are also given n programs where length of each program is i is Li.
2. Let Tj be the time to retrieve program ij.
3. It is now required to store these programs on the tape in such a way so that the mean retrieval time is minimum. MRT is the average tome required to retrieve any program stored on this tape.
4. Assume that the tape is initially positioned at the beginning.
5. Tj is proportional to the sum of all lengths of programs stored in front of the program ij.
6. The goal is to minimize MRT (Mean Retrieval Time),(1/n) $\sum_{i=0}^nTj$

I.e., want to minimize $∑_{j=1}^n ∑_{k=1}^j Ti$

Problem:

1. Here, n=3 and (L1, L2, L3) = (5, 10, 3). We can store these 3 programs on the tape in any order but we want that order which will minimize the MRT.
2. Suppose we store the programs in order (L1, L2, L3).
3. Then MRT is given as (5+(5+10)+(5+10+3))/3=38/3
4. To retrieve L1 we need 5 units of time. Because a tape is a sequential device we will have to first pass through entire L1 even if we want to retrieve L2.
5. Hence, retrieval time (RT) is 5 for program 1 and (5+10) for program 2.
6. Similarly, if program 3 is also considered then the total RT becomes 5+ (5+10) + (5+10+3) where (5+10+3) is the RT for program 3.
7. Since we want to find the mean retrieval time we add all the RT and then divide the sum by n.
8. The aim over here is to find the minimum MRT. To do this we consider all the possible orderings of these 3 programs. Since there 3 programs we can have at the most 6(3!) combinations.
9. Consider the below table:

1. It should be seen that the minimum MRT of (29/3) is obtained in case of (L1, L2, L3). Hence the optimal solution is achieved if the programs are stored in increasing order of their lengths.

2. Hence, a greedy approach to solving the problem is continuously select programs in increasing order of their lengths.

3. If L is an array having program length in ascending order then the following would be an algorithm to this problem:

   Sum=0;
   For (i=1; i<=n; i ++)
      For (j=1; j<=I; j++)
         Sum = sum+ L[j]
   MRT = sum/n;
   

4. The time complexity of this algorithm including the time to do sorting is $O (n^2)$.