Greedy-Algorithm

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 ______.
A
358
B
359
C
360
D
361
       Algorithms       Greedy-Algorithm       Gate 2014 Set -02
Question 1 Explanation: 
The implementation of optimal algorithm for merging sequences is as follows.

In the above implementation, total number of comparisons is
(44-1) + (94-1) + (65-1) + (159-1) = 358
Hint: The number of comparisons for merging two sorted sequences of length m and n is m+n-1.
Question 2
A
fdheg
B
ecgdf
C
dchfg
D
fehdg
       Algorithms        Greedy-Algorithm       Gate 2006-IT
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
Question 3
   
A
147
B
165
C
167
D
175
       Algorithms        Greedy-Algorithm       Gate-2005
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
Question 4
 
A
All tasks are completed
B
T1 and T6 are left out
C
T1 and T8 are left out
D
T4 and 6 are left out
       Algorithms        Greedy-Algorithm       Gate-2005
Question 4 Explanation: 
First sort the tasks in descending orderof their profit.
T3 T9 T7 T2 T4 T5 T8 T1 T6
Now the maximum deadline given is 7.
So we will take Array of 7 elements. And will try to put the tasks starting from T3 to T6, upto their maximum deadline possible.

So T4 and T6 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: as bs cs ae ds ce es fs be de gs ee fe hs ge he. Here, xs denotes the starting time and xe 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?
A
3
B
4
C
5
D
6
       Algorithms        Greedy-Algorithm       Gate-2003
Question 5 Explanation: 
Given order is “as bs cs ae ds ce es fs be de gs ee fe hs ge he
Where xs→Starting time, xe→ Ending time.
R1→for a
R2→for b
R3→for c
ae, R1 is free
R1→for d
ce, R3 is free
R3→for e
R4→for f
be, R2 is free
de, R1 is free
R1→for g
ee, R3 is free
fe, R4 is free
R2→for h
ge, R1 is free
he, R2 is free
Here, total we used is: R1, R2, R3, R4.
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:
A
165
B
90
C
75
D
65
       Algorithms        Greedy-Algorithm       Gate-1999
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
There are 6 questions to complete.