Assignment 3: Write a program to implement optimal storage tape using greedy approach.

Problem Statement: Write a program to implement optimal storage tape using greedy approach.

Objective- To find required order and Minimum Retrieval Time.

Theory:

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. 

Greedy algorithms try to find a localized optimum solution, which may eventually lead to globally optimized solutions. However, generally greedy algorithms do not provide globally optimized solutions.

Let’s suppose that the retrieval time of program i is T_i. Therefore, T_i=∑ⁱ _j=1  L_i
MRT is the average of all such T_i  is 1/n(∑ⁿ _i=1  T_i).

The sequential access of data in a tape has some limitations. Order must be defined in which the data/programs in a tape are stored so that least MRT can be obtained. Hence the order of storing becomes very important to reduce the data retrieval/access time.

Time complexity for sorting is O(nlogn) if std::sort() used. If you use bubble sort instead of std::sort(), it will take O(n^2).

Code

#include<iostream>

using namespace std;

void sort(int A[], int n){

for(int i=0;i<n-1;i++){

for(int j=0; j<n-i-1;j++){

if(A[j]>A[j+1]){

int temp = A[j];

A[j] = A[j+1];

A[j+1] = temp;

}

}

}

}

int OST(int A[], int n){

sort(A,n);

int RT = 0 ,sum = 0;

for(int i=0;i<n;i++){

sum = 0;

for(int j=0; j<=i;j++){

sum += A[j]; 

}

RT += sum; 

}

return RT;

}

int main(){

int n;

cout<<"\n Enter no. of Files ";

cin>>n;

int A[n];

for(int i=0;i<n;i++)

{

cout<<"\n Enter File size of ["<<i+1<<"] ";

cin>>A[i];

}

float RT = OST(A,n);

cout<<"\n Retrival Time is = "<<RT;

cout<<"\n MRT "<<RT/n;

cout<<endl;

return 0;

}

OUTPUT