topic – RBR

Greedy-Algorithm

Please wait while the activity loads.
If this activity does not load, try refreshing your browser. Also, this page requires javascript. Please visit using a browser with javascript enabled.

If loading fails, click here to try again

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

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	T₁ and T₆ are left out
C	T₁ and T₈ are left out
D	T₄ and ₆ are left out

Algorithms Greedy-Algorithm Gate-2005

Question 4 Explanation:

First sort the tasks in descending orderof their profit.
T₃ T₉ T₇ T₂ T₄ T₅ T₈ T₁ T₆
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₃ to T₆, upto their maximum deadline possible.

So T₄ and T₆ 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?

A	3
B	4
C	5
D	6

Algorithms Greedy-Algorithm Gate-2003

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₁→for a
R₂→for b
R₃→for c
a_e, R₁ is free
R₁→for d
c_e, R₃ is free
R₃→for e
R₄→for f
b_e, R₂ is free
d_e, R₁ is free
R₁→for g
e_e, R₃ is free
f_e, R₄ is free
R₂→for h
g_e, R₁ is free
h_e, R₂ is free
Here, total we used is: R₁, R₂, R₃, R₄.
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.