Question: Explain Optimal storage on tape example.
0

Subject: Analysis Of Algorithm

Topic: Greedy Method

Difficulty: High

aoa(14) • 25k views
 modified 15 months ago by maneesh.sake • 0 written 3.4 years ago by satishmanje93 • 40
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: 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             

We organize the program as:

Length 3 4 5 6 7 8 9 10 11 12 18 26 32
Program             
 written 3.4 years ago by satishmanje93 • 40

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

 written 20 months ago by nayaktusarika26 • 0
0

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

 written 2.5 years ago by satishmanje93 • 40

 written 20 months ago by nayaktusarika26 • 0
 written 15 months ago by maneesh.sake • 0