GATE CSE 1999 | Question: 2.20

Question

The minimum number of record movements required to merge five files A (with $10$ records), B (with $20$ records), C (with $15$ records), D (with $5$ records) and E (with $25$ records) is:

• A. $165$
• B. $90$
• C. $75$
• D. $65$

Comments

Can someone please explain why we can also use the Huffman coding total bit length logic here?
It gives the same answer, 165, as the optimal merge pattern.
I'm not understanding the connection between Huffman coding and this.

---

@ruchirjain

Take a look at my answer : https://gateoverflow.in/466/gate-cse-1999-question-2-20?show=489815#a489815 

---

@P0535_Yedidyah_Sagar
Thanks!

Answer 1

Arrange files in increasing order of records:

$\overset{\boxed5}{\text{D}}\quad \overset{\boxed{10}}{\text{A}}\quad\overset{\boxed{15}}{\text{C}}\quad\overset{\boxed{20}}{\text{B}}\quad\overset{\boxed{25}}{\text{E}}$


$\qquad\qquad\qquad\qquad\color{blue}{75}$

$\qquad\qquad\quad\color{blue}{30}\qquad\qquad\qquad\color{blue}{45}$

$\qquad\quad\color{blue}{15}\qquad\overset{\boxed{\text{C}}}{15}\qquad\qquad\overset{\boxed{\text{B}}}{20}\qquad\overset{\boxed{\text{E}}}{25}$

$\quad\overset{\boxed{\text{D}}}{5}\qquad\overset{\boxed{\text{A}}} {10}$

No. of movements $=15+30+45+75=165.$

Correct Answer: $A$

Comments

For those who are wondering why records should be in sorted order as it’s not mentioned in question to merge the files in sorted order, “ The files are merged in "sorted order of number of records" just to ensure minimum moves while merging ( you can try merging files in any random order to check other cases ) assuming there is no enough space to merge one file inside another file” .

Hence, the sequence of records inside the files and their comparison is of no significance here simply appending records or one file followed by records of another file won’t change the number of moves.

---

When we have to use the comparison formula..does it mentioned in the questions as like hoow many num of comparisons needed?? actually i am confused between  minimum num ber of record movements and comaparison

---

can i take first sorted 2 and next sorted 3 and then compare?

Answer 2

No of movements=15+30+45+75=165

Comments

What are those files m, n

---

@ramswaroop

for getting the number of comparisons we need to use formula (m+n-1).

here m,n is the size of the file.

for example,

m=b=5;

n=a=10;

when we merge these two files we need to do the comparison  between the elements of b and a so it takes

10+5-1=14(comparison requires ), here why we subtract 1 bczz we need not to compare the last element.

---

The maximum number of comparisons needed when merging two sorted lists of sizes m and n and is: m+n-1.

Answer 3

Try to implement it like Huffman coding.

Sorted files 5,10,15,20,25

1) merge min two -- 15,15,20,25 | merges=5+10=15

2) next two -- 30,20,25 -> reordering -- 20,25,30 | merges = merges+15+15=15+(15+15) = 45

3) next two -- 45,30 --> reordering -- 30,45 | merges= merges+ 20+25 = 45+(20+25) = 45+45= 90

4) last two -- 75 | merges = merges+45+30 = 90+(45+30) = 90+75 = 165

so, 165 is the answer

Answer 4

This question is based on the concept of Optimal Merge Pattern (OMP), which is actually the same greedy logic used in Huffman coding.

 

We are given 5 files:  

- A = 10 records  

- B = 20 records  

- C = 15 records  

- D = 5 records  

- E = 25 records  

 

We want to merge them into one file with the minimum number of record movements.  

The cost of merging two files = sum of their sizes (since every record must be copied once).

 

Optimal Merge Pattern

The greedy rule:  

- Always merge the two smallest files first.  

- Put the merged file back into the set.  

- Repeat until only one file remains.  

 

It ensures larger files are not copied repeatedly

 

Similarity with Huffman coding

Huffman coding works in the exact same way:  

- Always combine the two smallest frequency symbols.  

- Make a parent node with weight equal to the sum of the two.  

- Repeat until a single root remains.  

 

The total weighted path length of the Huffman tree = minimum cost of encoding.  

 

So in both cases:  

- File sizes ↔ frequencies  

- Merge cost ↔ parent node weight  

- Total movements ↔ total weighted path length  

 

This is why the mathematics is identical.

 

Given question:

Files: 5, 10, 15, 20, 25

 

Steps:  

1. Merge 5 + 10 = 15 (cost = 15)  

2. Merge 15 + 15 = 30 (cost = 30)  

3. Merge 20 + 25 = 45 (cost = 45)  

4. Merge 30 + 45 = 75 (cost = 75)  

 

Total cost = 15 + 30 + 45 + 75 = 165

Answer 5

Sort the files: 5, 10, 15, 20, 25.
Merge the smallest two records 15, 15, 20, 25
Merge 30, 20, 25
Sort 20, 25, 30
Merge 45, 30
75. So C is the answer

Comments

Your answer is not correct.Correct ans is 165 !

---

whats the diffrence between no.of movement  and comparisions ?????????

@AkashKanase

---

if you will count no of comparison it will come out to be 165-4=161 and nos of movement= 165, because no of comparison on merging two nodes will be m+n-1, but the record movement will be m+n..because you have to move entire records of both nodes to newly created node