Analysis & Design of Algorithms

Q.3: Find the optimal binary merge tree (pattern) for ten files whose length are. 28, 32, 12,5,84,53,91, 35, 3 and 11 also find its weighted external path length.

Answer:
For obtaining optimal binary merge pattern merge two smallest size files at each step
Figure shows a binary image pattern representing the optimal merge pattern obtained for the above 10 files

optimal binary merge tree 28, 32, 12,5,84,53,91, 35, 3 and 11
Weighted external path length
Where di = distance from the route to the external node
Qi = the length of Xi
Here n = 10
Therefore ∑diqi=d1q1+d2q2+….+d10q10

=(4x28) + (3x32)+(5x12)+(7x5)+(2x84)+(3x53)+(2x91)+(3x35)+(7x3)+(6x11)

=112+96+60+35+168+159+182+105+21+66

=1004 (Answer)


notes For Error Please Whatsapp @9300930012