0
Explain Optimal storage on tape example.
optimal storage on tape • 28k  views
0
1

Optimal storage problem:

Input: We are given ‘n’ problem that are to be stored on computer tape of length L and the length of program i is Li

Such that 1 ≤i≤ n and Σ 1≤k≤j Li≤ 1

Output: A permutation from all n! For the n programs so that when they are stored on tape in the order the MRT is minimized.

Example:

Let n = 3, (l1, l2, l3) = (8, 12, 2). As n = 3, there are 3! =6 possible ordering.

All these orderings and their respective d value are given below:

Ordering d (i) Value
1, 2, 3 8 + (8+12) + (8+12+2) 50
1, 3, 2 8 + 8 + 2 + 8 + 2 + 12 40
2, 1, 3 12 + 12 + 8 +12 + 8 + 2 54
2, 3, 1 12 + 12 +2 +12 + 2 + 8 48
3, 1, 2 2 + 2 + 8 + 2 + 8+ 12 34
3, 2, 1 2 + 2 +12 + 2 + 12 + 8 38

The optimal ordering is 3, 1, 2.

The greedy method is now applied to solve this problem. It requires that the programs are stored in non-decreasing order which can be done in O (nlogn) time.

Greedy solution:

i. Make tape empty

ii. Fori = 1 to n do;

iii. Grab the next shortest path

iv. Put it on next tape.

The algorithm takes the best shortest term choice without checking to see whether it is a big long term decision.

Algorithm:

enter image description here

For example, find an optimal placement for 13 programs on 3 tapes T0, T1 & T2 where the program are of lengths 12, 5, 8, 32, 7, 5, 18, 26, 4, 3, 11, 10 and 6.

Given problem:

Length 12 5 8 32 7 5 18 26 4 3 11 10 6
Program [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12]

We organize the program as:

Length 3 4 5 6 7 8 9 10 11 12 18 26 32
Program [8] [9] [1] [5] [12] [4] [2] [11] [10] [0] [6] [7] [3]
1

You can also watch this on youtube to understand this problem better.

Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more