Let F1, F2,...,Fn be a collection of n files to be stored on a tape. File Fi requires li bytes of space. The tape has enough storage space to contain all the n files. On average, a fraction pi, 0 pi 1, of requests to the tape are for file Fi. A file on a tape can only be accessed by first reading all the files that precede it. After a file is loaded from the tape, the tape is rewound. Give a greedy algorithm that determines the optimal ordering of the files on the tape such that the expected retrieval time is minimized. Prove your algorithms correctness. (Show that a non-greedy ordering cannot be optimal by showing how to decrease the expected access time by swapping an appropriate pair of files on the tape.) Note that the expected time of accessing a file is proportional to: ( ) 1 1 = = = n j j k ij ik T P l where i1, i2, . . . , in denote the final order in which files are stored on tape

Problem 3. Let Fi, F2... ,Fn be a collection of n files to be stored on a tape. File Fi requires bytes of space. The tape has enough storage space to contain all the n files. On average, a fraction Pi, 0 s pi s 1, of requests to the tape are for file Fi. A file on a tape can only be accessed by first reading all the files that precede it. After a file is loaded from the tape, the tape is rewound. Give a greedy algorithm that determines the optimal ordering of the files on the tape such that the expected retrieval time is minimized. Prove your algorithm' s correctness. (Show that a non-greedy ordering cannot be optimal by showing how to decrease the expected access time by swapping an appropriate pair of files on the tape.) Note that the expected time of accessing a file is proportional to where /2, . . ., h denote the final order in which files are stored on tape