GREEDY METHOD EXAMPLES





 

OPTIMAL STORAGE ON TAPES
 

There are 'n' programs that are to be stored on a computer tape of length 'l'.

Associated with each other i is the length li, 1<=i<=n. All the programs can only be written on the tape if the sum of all the lengths of the program is at most l.

Assumption: that whenever a program is to be retrieved from the tape , the tape is positioned at the front.
Now if the programs are stored in the order as I=i
1,i2,i3,i4.........,in, then the time tj needed to retrieve program (i,j) is proportional to ?1?k?j lik.
So the problem is that we have to store them in the tape in such an order that the M.R.T (mean retrieval time) is minimum.
A greedy approach to build such an algorithm requires such a permutation that chooses the next program on the basis of some optimization measure. In this we take the optimization measure to be 'd' (which is the current length of the tape that is written with the program)
So now every time when we write onto the disk, we keep in mind that the increment in the length of 'd' is minimum.
So this greedy method requires us to just sort the lengths of the programs or to assign them in a non-decreasing order, so that they can be directly written into disk on their length basis. So it in turns takes the complexity equal to O(n logn) just to sort the length of the programs.
Here's a sample pseudo code for the program if we have multiple disks on which we have to write the data
Pseudo code

tapes(n,m) // here n is the numbers of programs and m is the numbers of tapes
{
j=0;
for(i=1 to n do)
{
write ("append", i "to the permutation of the tape", j)
j=(j+1) mod m
}
}
REFERENCE BOOK
1.Ellis Horowitz and Sartaj Sahni,
Fundamentals of Computer Algorithms, Computer Science Press, Maryland, 1978, 626 pages

Non-profit Tax ID # 203478467