GATE CS 1999 Q2.20 — Algorithm Design: Greedy Techniques

This problem can be solved using the Optimal Merge Pattern algorithm, which uses a greedy approach similar to Huffman coding. To minimize the total number of record movements, we repeatedly merge the two smallest files at each step.

The initial file sizes are: {5, 10, 15, 20, 25}.

1. Step 1: Merge the two smallest files of sizes $5$ and $10$.
   New file size = $5 + 10 = 15$.
   Cost of this merge = $15$.
   Remaining files: {15, 15, 20, 25}.
2. Step 2: Merge the two smallest files of sizes $15$ and $15$.
   New file size = $15 + 15 = 30$.
   Cost of this merge = $30$.
   Remaining files: {20, 25, 30}.
3. Step 3: Merge the two smallest files of sizes $20$ and $25$.
   New file size = $20 + 25 = 45$.
   Cost of this merge = $45$.
   Remaining files: {30, 45}.
4. Step 4: Merge the remaining two files of sizes $30$ and $45$.
   New file size = $30 + 45 = 75$.
   Cost of this merge = $75$.

The total minimum number of record movements is the sum of the costs of all merge operations:

$$\text{Total Cost} = 15 + 30 + 45 + 75 = 165$$