3. (15 marks) Suppose that n files with lengths L1, L2, ... Ln are to...

  

Transcribed Image Text:

3. (15 marks) Suppose that n files with lengths L1, L2, ... " Ln are to be stored on a ... " tape, so that access to them is sequential. If the files are stored in the order i, in, then the time to retrieve file ik is the sum of the file lengths of all files before and including ik: k Tk = Lij Lij j=1 (1) We would like to order the files to minimize the average retrieval time, so we want to minimize n Ik n k=1 (2) (a) Design and write a greedy algorithm that will find the minimum average retrieval time for the files. (b) Analyse your algorithm's running time. (c) Prove that your algorithm works correctly. 3. (15 marks) Suppose that n files with lengths L1, L2, ... " Ln are to be stored on a ... " tape, so that access to them is sequential. If the files are stored in the order i, in, then the time to retrieve file ik is the sum of the file lengths of all files before and including ik: k Tk = Lij Lij j=1 (1) We would like to order the files to minimize the average retrieval time, so we want to minimize n Ik n k=1 (2) (a) Design and write a greedy algorithm that will find the minimum average retrieval time for the files. (b) Analyse your algorithm's running time. (c) Prove that your algorithm works correctly.

Answer rating: 100% (QA)

a Greedy Algorithm 1 Sort the files in nondecreasing order of length 2 Calculate the total retrieval time as follows Initialize total time T to 0 For ... View the full answer