## 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
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
 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
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   3```
What is the maximum profit earned?
 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
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   3```
Are all tasks completed in the schedule that gives maximum profit?
 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.