# Optimal Storage on Tapes – Solving using Greedy Approach

Optimal Storage on Tapes Problem: Given n programs P1, P2, …, Pn of length L1, L2, …, Ln respectively, store them on a tap of length L such that Mean Retrieval Time (MRT) is a minimum. The retrieval time of the jth program is a summation of the length of first j programs on tap. Let Tj be the time to retrieve program Pj. The retrieval time of Pj is computed as,

Mean retrieval time of n programs is the average time required to retrieve any program. It is required to store programs in an order such that their Mean Retrieval Time is minimum. MRT is computed as,

Optimal storage on tape is minimization problem which,

## Storage on Single Tape

• In this case, we have to find the permutation of the program order which minimizes the MRT after storing all programs on single tape only.
• There are many permutations of programs. Each gives a different MRT. Consider three programs (P1, P2, P3) with a length of (L1, L2, L3) = (5, 10, 2).
• Let’s find the MRT for different permutations. 6 permutations are possible for 3 items. The Mean Retrieval Time for each permutation is listed in the following table.
• It should be observed from the above table that the MRT is 26/3, which is achieved by storing the programs in ascending order of their length.
• Thus, greedy algorithm stores the programs on tape in non-decreasing order of their length, which ensures the minimum MRT.

## Algorithm for Optimal Storage on Tapes

Let L be the array of program length in ascending order. The greedy algorithm finds the MRT as following:

Algorithm Algorithm MRT_SINGLE_TAPE(L)
// Description : Find storage order of n programs to such that mean retrieval time is minimum
// Input : L is array of program length sorted in ascending order
// Output : Minimum Mean Retrieval Time

Tj ← 0
for i ← 1 to n do
for j ← 1 to i do
Tj ← Tj + L[j]
end
end
MRT ← Tj/ n

## Complexity analysis of Optimal Storage on Tapes

Primitive operation in above algorithm is the addition of program length, which is enclosed within two loops. The running time of algorithm is given by,

T(n) = O(n2)

This algorithm runs in O(n2) time.

## Storage on Multiple Tapes

• This is the problem of minimizing MRT on retrieval of the program from multiple tapes.
• Instead of a single tape, programs are to be stored on multiple tapes. Greedy algorithm solves this problem in a similar way. It sorts the programs according to increasing length of program and stores the program in one by one in each tape.
• The working of this approach is explained in the following example.

## Example

Example: Given the program lengths L = {12, 34, 56, 73, 24, 11, 34, 56, 78, 91, 34, 91, 45}. Store them on three taps and minimize MRT

Solution:

Given data :

First sort the programs in increasing order of their size.

Sorted data:

Now distribute the files among all three tapes.

MRTTape1 = ((11) + (11 + 34) + (11 + 34 + 45) + ((11 + 34 + 45 + 73)) + (11 + 34 + 45 + 73 + 91) ) / 4

= 563 / 5

= 112.6

MRTTape2 = ((12) + (12 + 34) + (12 + 34 + 56) + (12 + 34 + 56 + 78) ) / 4

= 340 / 4

= 85

MRTTape3 = ((24) + (24 + 34) + (24 + 34 + 56) + (24 + 34 + 56 + 91) ) / 4

= 353 / 4

= 88.25

MRT = (MRTTape3+ MRTTape3+ MRTTape3) / 3

= (112.6 + 85 + 88.25) / 3

= 95.28

Greedy algorithms are used to find an optimal or near-optimal solution to many real-life problems. A few of them are listed below : Additional Reading: Read on Ques10