# Optimal Storage on Tapes – Solving using Greedy Approach

**Optimal Storage on Tapes Problem: **Given n programs P_{1}, P_{2}, …, P_{n} of length L_{1}, L_{2}, …, L_{n} 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 P_{j} 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.

Ordering | Mean Retrieval Time (MRT) |

P_{1}, P_{2}, P_{3} | ( (5) + (5 + 10) + (5 + 10 + 2) ) / 3 = 37 / 3 |

P_{1}, P_{3}, P_{2} | ( (5) + (5 + 2) + (5 + 2 + 10) ) = 29 / 3 |

P_{2}, P_{1}, P_{3} | ( (10) + (10 + 5) + (10 + 5 + 2) ) = 42 / 3 |

P_{2}, P_{3}, P_{1} | ( (10) + (10 + 2) + (10 + 2 + 5) ) = 39 / 3 |

P_{3}, P_{1}, P_{2} | ( (2) + (2 + 5) + (2 + 5 + 10) ) = 26 / 3 |

P_{3}, P_{2}, P_{1} | ( (2) + (2 + 10) + (2 + 10 + 5) ) = 31 / 3 |

- 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**
T_{j} ← T_{j} + L[j]
**end**
**end**
MRT ← T_{j}/ 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(n^{2})

This algorithm runs in O(n^{2}) 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 :

P_{i} | P_{1} | P_{2} | P_{3} | P_{4} | P_{5} | P_{6} | P_{7} | P_{8} | P_{9} | P_{10} | P_{11} | P_{12} | P_{13} |

L_{i} | 12 | 34 | 56 | 73 | 24 | 11 | 34 | 56 | 78 | 91 | 34 | 91 | 45 |

First sort the programs in increasing order of their size.

Sorted data:

P_{i} | P_{6} | P_{1} | P_{5} | P_{2} | P_{7} | P_{11} | P_{13} | P_{3} | P_{8} | P_{4} | P_{9} | P_{10} | P_{12} |

L_{i} | 11 | 12 | 24 | 34 | 34 | 34 | 45 | 56 | 56 | 73 | 78 | 91 | 91 |

Now distribute the files among all three tapes.

Tape 1 | P_{6} | P_{2} | P_{13} | P_{4} | P_{12} |

Tape 2 | P_{1} | P_{7} | P_{3} | P_{9} | |

Tape 3 | P_{5} | P_{11} | P_{8} | P_{10} |

MRT_{Tape1} = ((11) + (11 + 34) + (11 + 34 + 45) + ((11 + 34 + 45 + 73)) + (11 + 34 + 45 + 73 + 91) ) / 4

= 563 / 5

= 112.6

MRT_{Tape2} = ((12) + (12 + 34) + (12 + 34 + 56) + (12 + 34 + 56 + 78) ) / 4

= 340 / 4

= 85

MRT_{Tape3} = ((24) + (24 + 34) + (24 + 34 + 56) + (24 + 34 + 56 + 91) ) / 4

= 353 / 4

= 88.25

MRT = (MRT_{Tape3}+ MRT_{Tape3}+ MRT_{Tape3}) / 3

= (112.6 + 85 + 88.25) / 3

= 95.28

## Some Popular Problems Solved by Greddy Algorithm

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

- Binary Knapsack Problem
- Fractional Knapsack Problem
- Job Scheduling Problem
- Activity Selection Problem
- Huffman Coding
- Optimal Storage on Tapes
- Optimal Merge Pattern
- Prim’s Algorithm
- Kruskal’s Algorithm
- Dijkstra’s Algorithm

Additional Reading: Read on Ques10