Question: Explain Optimal storage on tape example.
0

Subject: Analysis Of Algorithm

Topic: Greedy Method

Difficulty: High

aoa(14) • 25k views
ADD COMMENTlink
modified 15 months ago by gravatar for maneesh.sake maneesh.sake0 written 3.4 years ago by gravatar for satishmanje93 satishmanje9340
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]
ADD COMMENTlink
written 3.4 years ago by gravatar for satishmanje93 satishmanje9340

The answer to the above question is is available on the video given below

https://www.youtube.com/watch?v=lISTAmCqh4A

ADD REPLYlink
written 20 months ago by gravatar for nayaktusarika26 nayaktusarika260
0

Optimal storage on 3 tapes with values as 10,15,7,2,11,18,22,9,27,20

ADD COMMENTlink
written 2.5 years ago by gravatar for satishmanje93 satishmanje9340

You can follow the link given below and follow the method to solve this problem

https://www.youtube.com/watch?v=lISTAmCqh4A

ADD REPLYlink
written 20 months ago by gravatar for nayaktusarika26 nayaktusarika260
0

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

ADD COMMENTlink
written 15 months ago by gravatar for maneesh.sake maneesh.sake0
Please log in to add an answer.