GreedyAlgorithm
Question 1 
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______.
358  
359  
360  
361 
Question 1 Explanation:
The implementation of optimal algorithm for merging sequences is as follows.
In the above implementation, total number of comparisons is
(441) + (941) + (651) + (1591) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n1.
In the above implementation, total number of comparisons is
(441) + (941) + (651) + (1591) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n1.
Question 2 
fdheg  
ecgdf  
dchfg  
fehdg 
Question 2 Explanation:
Huffman's tree is as follows. The two least frequently characters are taken as the children of a newly made node and the frequency of the newly made node is made equal to the sum of those two child nodes. Then the same procedure is repeated till all nodes are finished.
∴ 110111100111010 = fdheg
∴ 110111100111010 = fdheg
Question 3 
147  
165  
167  
175 
Question 3 Explanation:
We will now add the profits of the tasks we have put in the array.
30+25+23+20+18+16+15 = 147
30+25+23+20+18+16+15 = 147
Question 4 
All tasks are completed  
T_{1} and T_{6} are left out
 
T_{1} and T_{8} are left out
 
T_{4} and _{6} are left out

Question 4 Explanation:
First sort the tasks in descending orderof their profit.
T_{3} T_{9} T_{7} T_{2} T_{4} T_{5} T_{8} T_{1} T_{6}
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T_{3} to T_{6}, upto their maximum deadline possible.
So T_{4} and T_{6} are left out.
T_{3} T_{9} T_{7} T_{2} T_{4} T_{5} T_{8} T_{1} T_{6}
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T_{3} to T_{6}, upto their maximum deadline possible.
So T_{4} and T_{6} are left out.
Question 5 
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “a_{s} b_{s} c_{s} a_{e} d_{s} c_{e} e_{s} f_{s} b_{e} d_{e} g_{s} e_{e} f_{e} h_{s} g_{e} h_{e}”. Here, x_{s} denotes the starting time and x_{e} denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?
3  
4  
5  
6 
Question 5 Explanation:
Given order is “a_{s} b_{s} c_{s} a_{e} d_{s} c_{e} e_{s} f_{s} b_{e} d_{e} g_{s} e_{e} f_{e} h_{s} g_{e} h_{e}”
Where x_{s}→Starting time, x_{e}→ Ending time.
R_{1}→for a
R_{2}→for b
R_{3}→for c
a_{e}, R_{1} is free
R_{1}→for d
c_{e}, R_{3} is free
R_{3}→for e
R_{4}→for f
b_{e}, R_{2} is free
d_{e}, R_{1} is free
R_{1}→for g
e_{e}, R_{3} is free
f_{e}, R_{4} is free
R_{2}→for h
g_{e}, R_{1} is free
h_{e}, R_{2} is free
Here, total we used is: R_{1}, R_{2}, R_{3}, R_{4}.
Therefore, total no. of rooms we required = 4(minimum).
Where x_{s}→Starting time, x_{e}→ Ending time.
R_{1}→for a
R_{2}→for b
R_{3}→for c
a_{e}, R_{1} is free
R_{1}→for d
c_{e}, R_{3} is free
R_{3}→for e
R_{4}→for f
b_{e}, R_{2} is free
d_{e}, R_{1} is free
R_{1}→for g
e_{e}, R_{3} is free
f_{e}, R_{4} is free
R_{2}→for h
g_{e}, R_{1} is free
h_{e}, R_{2} is free
Here, total we used is: R_{1}, R_{2}, R_{3}, R_{4}.
Therefore, total no. of rooms we required = 4(minimum).
Question 6 
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:
165  
90  
75  
65 
Question 6 Explanation:
Always merge two files with minimum no. of records.
10, 20, 15, 5, 25
Merge 5 & 10:
5+10=15 movements
Now the list is
15, 20, 15, 25
Merge 15 & 15:
15+15=30 movements
Now the list is
30, 20, 25
Merge 20 & 25:
20+25=45 movements
Now the list is
30, 45
Merge 30 & 45:
30+45=75 movements
∴ Total no. of movements
= 15+30+45+75
= 165
10, 20, 15, 5, 25
Merge 5 & 10:
5+10=15 movements
Now the list is
15, 20, 15, 25
Merge 15 & 15:
15+15=30 movements
Now the list is
30, 20, 25
Merge 20 & 25:
20+25=45 movements
Now the list is
30, 45
Merge 30 & 45:
30+45=75 movements
∴ Total no. of movements
= 15+30+45+75
= 165
There are 6 questions to complete.