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 
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows
a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21/A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? 110111100111010
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 
We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.
Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3What is the maximum profit earned?
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 
We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time. We can execute one task at a time. Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.
Task T1 T2 T3 T4 T5 T6 T7 T8 T9 Profit 15 20 30 18 18 10 23 16 25 Deadline 7 2 5 3 4 5 2 7 3Are all tasks completed in the schedule that gives maximum profit?
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.