Previous Year Questions: Greedy Technique | Algorithms - Computer Science Engineering (CSE) PDF Download

Q1: Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.
Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string? (2021 SET-2)
(a) 21
(b) 23
(c) 25
(d) 30
Ans: (b)
Sol: Given string: abbccddeee
a has the least frequency and should be the leaf of the tree. b, c and d have the same frequency but as per Condition 2 in the questions d should be taken first, followed by c and then b. e has the highest frequency and so must be taken last.

The final Huffman tree looks like:


∴ Minimum length of encoded string: (1 x 3) + (2 x 2) + (2 x 2) + (3 x 2) + (2 x 3) = 23
Option B is correct.

Q2: Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices:
p[1]= 1, p[2] = 5,p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18
which of the following statements is/are correct about R₇?  (2021 SET-1)
(a) R₇ = 18
(b) R₇ = 19
(c) R₇ is achieved by three different solutions.
(d) R₇ cannot be achieved by a solution consisting of three pieces.
Ans: (a, b)
Sol: A & C should be correct

• 1^st Solution: p[2]; p[3]; p[2] = 5 + 8 + 5 = 18
• 2^nd Solution: p[7] = 18
• 3^rd Solution: p[6]; p[1] = 17 + 1 = 18

Q3: Huffman tree is constructed for the following data : {A,B,C,D,E) with frequency (0.17, 0.11, 0.24, 33 and 0.15) respectively. 100 00 01101 is decoded as  (2020)
(a) BACE
(b) CADE
(c) BATH
(d) CADD
Ans: (a)
Sol:

100 - B
00 - A
01 - C
101 - E
BACE
Option A 

Q4: Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by V_opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_greedy. The value of V_opt-V_greedy is ________.    (2018)
(a) 36
(b) 40
(c) 16
(d) 0
Ans: (c)
Sol: V_opt is clearly 60. You can go for brute force or by normal intuition you can get it.
Now solving for V_greedy.

Sort them in descending order of Value/Weight as per the question.

Now start picking items.(Note: You cannot take a fraction of the given weight as per the question). Max weight size is given as 11 (Inclusive).

• Item 4 is picked. Weight remaining = 11 - 2 = 9kg.
• Item 1 cannot be picked as 10kg > 9kg.
• Item 3 can be picked as 4kg < 9kg. Weight Remaining = 9 - 4 = 5kg
• Item 2 cannot be picked as 7kg > 5kg.

So, item 4 and Item 3 are picked. Their values are 24 and 20 respectively.
⇒ V_greedy = 24 + 20 = 44.
V_optimal  - V_greedy = 60 - 44 = 16.

Q5: A message is made up entirely of characters from the set X = {P,Q,R,S,T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is________  (2017 SET-2)
(a) 225
(b) 115
(c) 275
(d) 315
Ans: (a)
Sol: X = {P, Q, R, S, T}


∴ Expected length of an encoded character
= (0.22 x 2) + (0.34 × 2) + (0.17 × 3) + (0.19 × 2) + (0.08 × 3) bits
= 0.44 + 0.68 + 0.51 + 0.38 + 0.24 bits
= 2.25 bits
∴ Expected length of a encoded message of 100 characters in bits = 100 × 2.25 = 225

Q6: Consider the following table:

Match the algorithms to the design paradigms they are based on.  (2017 SET-1)
(a) P-(ii), Q-(iii),R-(i)
(b) P-(iii), Q-(i), R-(ii)
(c) P-(ii), Q-(i), R-(iii)
(d) P-(i), Q-(ii), R-(iii)
Ans: (c)
Sol: In Kruskal, in every iteration, an edge of the most minimum weight (greediest) possible is selected and added to MST construction.
Hence, greedy.
In Quick Sort, we partition the problem into subproblems, solve them and then combine. Hence, it is Divide & Conquer.
Floyd-Warshall uses Dynamic programming.
Hence, correct answer is : OPTION (C).

Q7: 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 ________.  (2014 SET-2)
(a) 362
(b) 358
(c) 456
(d) 320
Ans: (b)
Sol: The optimal algorithm always chooses the smallest sequences for merging.
20 24 - 44, 43 comparisons
30 35 - 65, 64 comparisons
44 50 - 94, 93 comparisons
65 94 - 159, 158 comparisons
so, totally 43 + 64 + 93 + 158 = 358 comparisons.
PS: In merge operation we do a comparison of two elements and put one element in the sorted output array.
So, every comparison produces one output element. But for the last element we won't need a comparison and we simply insert it to the output array. So for n output elements we need (n - 1) comparisons.

Q8: Consider a job scheduling problem with 4 jobs J₁, J₂, J₃ and J₄ with corresponding deadlines:
(d₁, d₂, d₃, d₄) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?  (2007)
(a) J₂, J₄, J₁, J₃
(b) J₄, J₁, J₂, J₃
(c) J₄, J₂, J₁, J₃
(d) J₄, J₂, J₃, J_1
Ans: (b)
Sol: To optimize and to get a feasible solution we have to finish all the jobs with in their dead line.
since the deadline of j2 and j4 are 2.so they must be completed by 2.so we can schedule any one
that is j2 or j4..
in option c,d j4 is scheduled first and then j2 and
in option a, first j2 then j4 so we can able to schedule other 2 jobs
now consider option b
j4 is scheduled and need to be completed ....by 2 ---no problem
j1 is scheduled and need to be completed ....by 4 --no problem
but now as j2 should come before time 2..but we scheduled j1....so j2 cant be scheduled
leads to a unfeasible sol.

Q9: Consider n jobs J₁, J₂... J_n such that job J_i has execution time t_i and a non-negative integer weight w_i. The weighted mean completion time of the jobs is defined to be, where T_i is the completion time of job J_i. Assuming that there is only one processor available, in what order must the jobs be executed in order to minimize the weighted mean completion time of the jobs?(2007)
(a) Non-decreasing order of t_i
(b) Non-increasing order of w_i
(c) Non-increasing order of w_it_i
(d) Non-increasing order of w_i/t_i
Ans: (d)
Sol: Lets take an example:

For option 1 non decreasing t_i
= (3 x 2 + 1 × 5 + 4 × 9 + 2 × 14)/10 = (6 + 5 + 36 + 28)/10 = 7.5
For option 2 non increasing w_i
=(4 x 4 + 3 × 6 + 2 × 11 + 1 × 14)/10 = (16 + 18 + 22 + 14)/10 = 7
For option 3 non increasing w_it_i
=(16 + 2 × 9 + 3 × 11 + 1 × 14)/10 = (16 + 18 + 33 + 14)/10 = 8.1
For option 4 non increasing w_i/t_i
= (3 x 2 + 4 x 6 + 2 × 11 + 1 × 14)/10 (6 + 10 + 22 + 14)/10 = 6.6
Minimum weighted mean obtained from non increasing w_i/t_i (option D)
The solution above is a classical example of greedy algorithm - that is at every point we choose the best available option and this leads to a global optimal solution. In this problem, we require to minimize the weighted mean completion time and the denominator in it is independent of the order of execution of the jobs. So, we just need to focus on the numerator and try to reduce it. Numerator here is a factor of the job weight and its completion time and since both are multiplied, our greedy solution must be

• to execute the shorter jobs first (so that remaining jobs have smaller completion time) and
• to execute highest weighted jobs first (so that it is multiplied by smaller completion time)

So, combining both we can use w_i/t_i to determine the execution order of processes - which must then be executed in non-increasing order.

Q10: Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
What is the average length of the Huffman code for the letters a, b, c, d, e, f?  (2007)
(a) 3
(b) 2.1875
(c) 2.25
(d) 1.9375
Ans: (d)
Sol: 



Avg length

Correct Answer: D

Q11: Suppose the letters a, b, c, d, e, f have probabilities 1/2, 1/4, 1/8, 1/16, 1/32, 1/32 respectively.
Which of the following is the Huffman code for the letter a, b, c, d, e, f?  (2007)
(a) 0, 10, 110, 1110, 11110, 11111
(b) 11, 10, 011, 010, 001, 000
(c) 11, 10, 01, 001, 0001, 0000
(d) 110, 100, 010, 000, 001, 111
Ans: (a)
Sol: Based on the probabilities, we can say the probable frequency of the letters will be
16, 8, 4, 2, 1, 1
Now, the Huffman tree can be constructed as follows:


So, A is the answer for 76.

Q12: 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?  (2006)
110111100111010  
(a) fdheg
(b) ecgdf
(c) dchfg
(d) fehdg
Ans: (a)
Sol: Huffman's tree is as follows. The two least frequent 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 = 110 11110 0 1110 10 = fdheg

Q13: In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.  (2005)

(a) 1→C, 2→A, 3 → B, 4 → D
(b) 1→B, 2→D, 3 → C, 4 → A
(c) 1→C, 2→D, 3 → A, 4 → B
(d) 1→B, 2→A, 3 → C, 4 → D
Ans: (a)
Sol: Bellman-Ford algorithm option(C), O(nm). Assuming n as edges, m as vertices, for every vertex we relax all edges. m * n, O(mn).
Kruskal's algorithm ⇒ Remaining Option (A): O(m log n).
Floyd-Warshall algorithm ⇒ option (B), Dynamic Programming Algo, O(N³).
Topological sorting ⇒ option(D), boils down to DFS, O(V + E).

Q14: 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.

What is the maximum profit earned?  (2005)
(a) 147
(b) 165
(c) 167
(d) 175
Ans: (a)
Sol: The most important statement in question is
each task requires one unit of time
This shows that we can greedily choose the better task and that should give us the optimal solution. The best task would be the one with maximum profit. Thus we can sort the tasks based on deadline and then profit as follows:

Thus, T₄ and T₆ are left.
So, maximum profit will not include those of T4 and T6 and will be = 15 + 20 + 30 + 18 + 16 + 23 + 25 = 147
A is answer

Q15: 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.

Are all tasks completed in the schedule that gives maximum profit?  (2005)
(a) All tasks are completed
(b) T1 and T6 are left out
(c) T1 and T8 are left out
(d) T4 and T6 are left out
Ans: (d)
Sol:
 

Step -1 Sort the tasks in decreasing order of profit and if any conflict arises between two or more tasks, resolve them by sorting them on basis of having greater deadline first(Because we have more time to complete the task with greater deadline and same profit).
Step 2 - Since Maximum deadline given is 7, so we consider we have 7 time slots ranging from 0 - 7 where a task T_i having deadline say 2 can be filled in slots either 0 - 1 or 1 - 2 and not beyond 2 because this task has deadline of 2 time units, so this task has to be completed by at most time T = 2.
Now according to question, since Each task completes in Unit time, so a single tasks takes only one slot as shown.
Now Take the first task in the list i.e. T₃ which has a deadline of 5, so it can be completed in maximum 5 time units, so place it in slot 4 - 5 which is the maximum deadline by which this task can be completed.
Task T₉ with deadline 3 is similarly placed in slot 2 - 3.
Task T₇ with deadline 2 is placed in slot 1 - 2.
Now for task T₂ having deadline 2 can be placed in either 0 -1 or 1 - 2 (Occupied by T₇).
So T₂ will occupy slot 0 - 1.
Task T₅ with deadline 4 is placed in slot 3 - 4.
Now comes task T₄ which has deadline 3 can be put in slots 0 - 1 or 1 - 2 or 2 - 3 and not beyond that. Unfortunately, all such slots are occupied so T₄ will be left out.a
Task T₈ with deadline 7 goes in slot 6 - 7.
Task T₁ with deadline 7 can be placed in slot 5 - 6.
Now all time slots are full.
So, Task T₆ will be left out.
So, option (d) is the answer.

Q16: 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:  (1999)
(a) 165
(b) 90
(c) 75
(d) 65
Ans: (a)
Sol: Sorted files 5,10,15,20,25
1) merge min two -- 15,15,20,25 | merges = 5 + 10 = 15
2) next two -- 30,20,25 -> reordering -- 20,25,30 | merges = merges + 15 + 15 = 15 + (15 + 15) = 45
3) next two -- 45,30 --> reordering -- 30,45 | merges= merges + 20 + 25 = 45 + (20 + 25) = 45 + 45 = 90
4) last two -- 75 | merges = merges + 45 + 30 = 90 + (45 + 30) = 90 + 75 = 165
so, 165 is the answer