3/13/2021 Download PDF

Exam Result of Algorithms Topic Test – 3 (Greedy Algorithms)

Score Card For Algorithms Topic Test – 3 (Greedy Algorithms)

Total No. of 1387 My Marks 0.00 Correct 0 Incorrect 0

Student Question Question

Total Marks of 25.00 My Percentile 1.37% Right Marks 0 Negative 0

Test Marks

Total Question in 15 Total Answered Question 0 Left Question 15 Left Question 25.00
Test in Test Marks

Total Time of 45 My Time 16 My Rank 1368th Result FAILED

Test Mins Sec

Performance Report For Algorithms Topic Test – 3 (Greedy Algorithms)

Question & Marks Wise Report For Algorithms Topic Test – 3 (Greedy Algorithms)
Subject Report For Algorithms Topic Test – 3 (Greedy Algorithms)

Name Total Questions Correct/ Marks Scored/ Unattempted Questions/

Incorrect Question Negative Marks Marks

Algorithms Topic Test – 15 0/0 0/0 15/25.00

3

Grand Total 15 0/0 0.00/0.00 15/25.00

Graphical Report For Algorithms Topic Test – 3 (Greedy Algorithms)

Time Management For Algorithms Topic Test – 3 (Greedy Algorithms)

Name Total Correct/ Marks Percentage Unattempted Total

Questions Incorrect Scored/ Questions/ Time
Question Negative Marks
Marks

Algorithms Topic 15 0/0 0/0 0.00% 15/25.00 15 Sec

Test – 3

Grand Total 15 0/0 0.00/0.00 0.00% 15/25.00 15 Sec

Question Report For Algorithms Topic Test – 3 (Greedy Algorithms)

Q.No. Question Your Correct Max. Your Your Level

Answer Answer Marks Score Time

1 Suppose we have 6 sorted lists and each of 255 1.00 15 Easy

sizes 5, 10, 15, 20, 25, 30 respectively, which Sec
need to be merged into a combined sorted
list, but we can merge only two at a time. Find
the total record movements of optimal merge
pattern.

testseries.ravindrababuravula.com/crm/Results/printresult/166956 1/28
3/13/2021 Download PDF

2 Which of the following algorithm is not using U and V 1.00 - Easy

greedy technique?

P) Hu man coding

Q) Optimal merge pattern

R) Prim’s algorithm

S) Kruskal’s algorithm

T) Dijkstra’s algorithm

U) Bellman Ford algorithm

V) Floyd Warshall algorithm

3 The following Knapsack bag. The Knapsack 114 1.00 - Easy

bag maximum Capacity is 30. Find out the
maximum pro t for Greedy Knapsack___?

4 What is the time complexity of Dijkstra’s O((V+E)logV) 1.00 - Easy

algorithm if it is implemented using AVL Tree
instead of Priority Queue over a graph G=
(V,E)?

5 Given undirected graph G=(V,E) to nd the A-C, C-G, C-E, 1.00 - Easy
correct sequence order for minimum cost E-F, B-D, B-G,
spanning tree(MST) using kruskal’s E-H
algorithms.

testseries.ravindrababuravula.com/crm/Results/printresult/166956 2/28
3/13/2021 Download PDF

6 The most appropriate matching for the P:4, Q:4, R:1, 2.00 - Easy
following pairs S:3, T:1, U:2,
V:2, W:5, X:6,
Y:2, Z:1, A:7

X: Dijkstra’s algorithm using Min Heap

Y: DFS

Z: Fractional knapsack problem

A: Job sequencing with deadlines

7 Anand having total 24 chocolates of the 1.75 2.00 - Easy

following brands. 12 Cadbury, 8 Ferrero
Rocher, 2 Ghirardelli, 1 Hershey's and 1
Toblerone. Seshu picks a chocolate randomly
from a total, and messages to Shiva its color
using string of 0’s and 1’s. Seshu replaces the
chocolates in the total, and repeats this
experiment, many times. What is the
minimum expected length of the message
Seshu has to convey to Shiva per experiment
[Note:Use 2 numbers after fraction part ] ?

testseries.ravindrababuravula.com/crm/Results/printresult/166956 3/28
3/13/2021 Download PDF

8 Ravindrababu Ravula and Anand started new 82 2.00 - Easy

website. The website contains all computer
science(CS) questions and detailed
explanations given by expert faculties. Till the
date they given explanations for GATE, ISRO,
DRDO, UGC-NET, KVS, AAI, NIELIT and PHD
entrance exams conducted by di erent
universities. If students are sending questions
papers to our team, we will give explanations
within 15 days and will be upload to our
website. The website name contains di erent
characters.

SOLUTIONSADDA

Website name of 26 characters over X is

encoded using Hu man coding. Then the
expected length of the encoded website name
in bits is____

9 Suppose we have Single Source Shortest Path 29 2.00 - Easy

on the following Adjacency list with vertex 0 as
the source.

Find out total cost for reaching source node to

all other vertices for which the shortest path
distances are nalized(Note: No need to
calculate In nity cost vertices) ____

testseries.ravindrababuravula.com/crm/Results/printresult/166956 4/28
3/13/2021 Download PDF

10 Suppose we have 8 tasks to execute. The T1 and T8 2.00 - Easy

execution of each task takes 1 unit of time.
The following table contains, each task Ti has
pro t Pi and deadline di. if task Ti is
completed before dith unit of time then we
can earn pro t Pi.

What are the tasks are not completed within

deadline?

11 Consider the following graph 29 2.00 - Easy

Find a spanning tree with minimal total weight

containing the edges {e, i} and {g, k} in the
given weighted graph.

12 Use Hu man coding to encode the following 2.45 2.00 - Easy

symbols with the frequencies listed A : 0.08, B
: 0.10, C : 0.12, D : 0.15, E : 0.20, F : 0.35. What
is the average number of bits used to encode
a character?

testseries.ravindrababuravula.com/crm/Results/printresult/166956 5/28
3/13/2021 Download PDF

13 Given a graph, nd total number of strongly 5 2.00 - Easy

connected components

14 Given a graph, nd the correct topological 0-4-3-1-2-5- 2.00 - Easy

sequence using indegree elimination method 6-7

testseries.ravindrababuravula.com/crm/Results/printresult/166956 6/28
3/13/2021 Download PDF

15 Which of the following statement(s) is/are Both (i) and 2.00 - Easy
TRUE? (ii)

(i). Suppose that Dijkstra’s algorithm is run

using a priority queue data structure for
which insert and decrease key operations take
O(log log V) time, extract-min operation take
O(√V) time then the running time of Dijkstra’s
algorithm on a directed weighted graph G =
(V, E) containing non-negative edges will be
 O(V √V + Elog log V)

(ii). If a topological sort exists for the vertices

in a directed graph, then a DFS on the graph
will produce no back edges.

Solution For Algorithms Topic Test – 3 (Greedy Algorithms)

Question: 1  
Suppose we have 6 sorted lists and each of sizes 5, 10, 15, 20, 25, 30 respectively, which need to be merged into
a combined sorted list, but we can merge only two at a time. Find the total record movements of optimal merge
pattern.

Not Attempt Correct Answer : 255

Max Marks :  1.00 Marks Scored :   Time Taken :  15 Sec

testseries.ravindrababuravula.com/crm/Results/printresult/166956 7/28
3/13/2021 Download PDF

Solution :  
30, 25, 20, 15, 10, 5

=(2*30)+(4*10)+(4*5)+(3*15)+(2*20)+(2*25)

=255

testseries.ravindrababuravula.com/crm/Results/printresult/166956 8/28
3/13/2021 Download PDF

Question: 2  
Which of the following algorithm is not using greedy technique?

P) Hu man coding

Q) Optimal merge pattern

R) Prim’s algorithm

S) Kruskal’s algorithm

T) Dijkstra’s algorithm

U) Bellman Ford algorithm

V) Floyd Warshall algorithm

1.

U and V

2.

S,T and U

3.

only V

4.

P,Q and R

Not Attempt Correct Answer : Option1

Max Marks :  1.00 Marks Scored :   Time Taken :  -

Solution :  
Bellman ford and oyd warshall algorithm is follows Dynamic Programming(DP) technique. Even though
bellman ford algorithm uses for Single Source Shortest Path(SSSP) problem it follows DP technique. We know
that Floyd warshall algorithm uses DP technique for solving All Pair Shortest Path(APSP) problem.

Question: 3  
The following Knapsack bag. The Knapsack bag maximum Capacity is 30. Find out the maximum pro t for
Greedy Knapsack___?

Not Attempt Correct Answer : 114

Max Marks :  1.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 9/28
3/13/2021 Download PDF

Solution :  
We sort the objects based on pro t/Weight Ratio in descending order and place it accordingly in the knapsack.

The objects are in sorted order according to their pro ts are: R,V,T,Q,S,P

Object R, Knapsack Capacity  = 30-4=26, Pro t=20

Object V, Knapsack Capacity = 26-5=21, Pro t=25

Object T, Knapsack Capacity  = 21-7=14,  Pro t=27

Object Q, Knapsack Capacity  = 14-8=6,  Pro t=24

Object S, Knapsack Capacity  = 6-6=0,  Pro t=(3*6=18)

Then the total pro t= 20+25+27+24+18=114

Question: 4  
What is the time complexity of Dijkstra’s algorithm if it is implemented using AVL Tree instead of Priority Queue
over a graph G=(V,E)?

1.

O(VlogE)

2.

O(VE)

3.

O(V2)

4.

O((V+E)logV)

Not Attempt Correct Answer : Option4

Max Marks :  1.00 Marks Scored :   Time Taken :  -

Solution :  
Using AVL Trees, both Decrease key and Extract-min operation can implemented in O(log V) time, So over all time
complexity is O((V+E)logV)

testseries.ravindrababuravula.com/crm/Results/printresult/166956 10/28
3/13/2021 Download PDF

Question: 5  
Given undirected graph G=(V,E) to nd the correct sequence order for minimum cost spanning tree(MST) using
kruskal’s algorithms.

1.

A-C, C-G, C-E, E-F, B-D, B-G, E-H

2.

A-C, C-G, C-E, E-F, B-G, B-D, E-H

3.

A-C, C-G, C-E, E-F, B-D, B-G, B-E

4.

A-C, C-G, C-E, E-F, B-G, B-D, B-E

Not Attempt Correct Answer : Option1

Max Marks :  1.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 11/28
3/13/2021 Download PDF

Solution :  
To nd kruskal’s algorithm, First we have to sort all edge weights and based on the least weights we are forming
spanning tree.

Sorted order= 3,4,4,4,5,6,7,7,8,8,9,9,9,9,10,10

We have to connect the edges from same ascending order.

Sequence= A-C, C-G, C-E, E-F, B-D, B-G, E-H

Note: If same edge weights we can take any order. So that we can get number of spanning trees for single MST.

Question: 6  
The most appropriate matching for the following pairs

X: Dijkstra’s algorithm using Min Heap

Y: DFS

Z: Fractional knapsack problem

A: Job sequencing with deadlines

testseries.ravindrababuravula.com/crm/Results/printresult/166956 12/28
3/13/2021 Download PDF

1.

P:4, Q:4, R:1, S:3, T:1, U:2, V:3, W:6, X:5, Y:3, Z:7, A:7

2.

P:4, Q:4, R:1, S:3, T:1, U:2, V:2, W:5, X:6, Y:2, Z:1, A:7

3.

P:4, Q:3, R:1, S:3, T:1, U:2, V:2, W:5, X:6, Y:2, Z:7, A:1

4.

P:4, Q:6, R:1, S:3, T:1, U:2, V:3, W:6, X:5, Y:2, Z:2, A:1

Not Attempt Correct Answer : Option2

Max Marks :  2.00 Marks Scored :   Time Taken :  -

Solution :  
P: Prim’s Algorithm→ O(ElogV)

Q: Kruskal’s algorithm→ O(ElogV)

R: Hu man Coding→ O(nlogn)

S: Bellman Ford→ O(V*E)

T: Optimal Merge Pattern→ O(nlogn)

U: BFS → O(V+E)

V: Topological Sort→ O(V+E)

W: Prim’s algorithm using Fibonacci heap → O(E+VlogV)

X: Dijkstra’s algorithm using Min Heap → O((V+E)logV)

Y: DFS → O(V+E)

Z: Fractional knapsack problem → O(nlogn)

A: Job sequencing with deadlines worst case time complexity → O(n2)

Question: 7  
Anand having total 24 chocolates of the following brands. 12 Cadbury, 8 Ferrero Rocher, 2 Ghirardelli, 1
Hershey's and 1 Toblerone. Seshu picks a chocolate randomly from a total, and messages to Shiva its color using
string of 0’s and 1’s. Seshu replaces the chocolates in the total, and repeats this experiment, many times. What is
the minimum expected length of the message Seshu has to convey to Shiva per experiment [Note:Use 2
numbers after fraction part ] ?

Not Attempt Correct Answer : 1.75

Max Marks :  2.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 13/28
3/13/2021 Download PDF

Solution :  
Using static Hu man compression you can encode the more common chocolates in fewer bits than the rare
chocolates, that being the case on can expect that common chocolates will usually be chosen.

Eg:

Cadbury: 1

Ferrero Rocher: 01

Ghirardelli: 001

Hershey's: 0001

Toblerone: 0000

The number of bits required for representing each chocolate is

12 blue = (1*12=12)

8 red = (2*8=16)

2 white = (3*2=6)

1 yellow = (4*1=4)

1 orange = (4*1=4)

For total of 42/24

               = 21/12

              = 1.75

Question: 8  
Ravindrababu Ravula and Anand started new website. The website contains all computer science(CS) questions
and detailed explanations given by expert faculties. Till the date they given explanations for GATE, ISRO, DRDO,
UGC-NET, KVS, AAI, NIELIT and PHD entrance exams conducted by di erent universities. If students are sending
questions papers to our team, we will give explanations within 15 days and will be upload to our website. The
website name contains di erent characters.

SOLUTIONSADDA

Website name of 26 characters over X is encoded using Hu man coding. Then the expected length of the
encoded website name in bits is____

Not Attempt Correct Answer : 82

Max Marks :  2.00 Marks Scored :   Time Taken :  -

Solution :  

2   2 2   2 1 1   1 1   1

testseries.ravindrababuravula.com/crm/Results/printresult/166956 14/28
3/13/2021 Download PDF

= (2*2 + 2*3 + 2*3 + 2*3 + 1*3 + 1*4 + 1*4 + 1* 4 + 1*4)

testseries.ravindrababuravula.com/crm/Results/printresult/166956 15/28
3/13/2021 Download PDF

= (4 + 6 + 6 + 6 + 3 + 4 + 4 + 4 + 4)  

= 41

→  We have to nd for 26 characters

→ 41 for 13 characters

→ then for 26 characters it should be = 82

Question: 9  
Suppose we have Single Source Shortest Path on the following Adjacency list with vertex 0 as the source.

Find out total cost for reaching source node to all other vertices for which the shortest path distances are
nalized(Note: No need to calculate In nity cost vertices) ____

Not Attempt Correct Answer : 29

Max Marks :  2.00 Marks Scored :   Time Taken :  -

Solution :  
Step-1: Convert adjacency list into undirected graph

testseries.ravindrababuravula.com/crm/Results/printresult/166956 16/28
3/13/2021 Download PDF

Step-2: Single source shortest path is

Step-3: The logical representation is

Total cost is 5+4+1+3+7+6+3

                = 29

testseries.ravindrababuravula.com/crm/Results/printresult/166956 17/28
3/13/2021 Download PDF

Question: 10  
Suppose we have 8 tasks to execute. The execution of each task takes 1 unit of time. The following table contains,
each task Ti has pro t Pi and deadline di. if task Ti is completed before dith unit of time then we can earn pro t
Pi.

What are the tasks are not completed within deadline?

1.

T1 and T4

2.

Only T8

3.

T1 and T8

4.

T4 and T8

Not Attempt Correct Answer : Option3

Max Marks :  2.00 Marks Scored :   Time Taken :  -

Solution :  
 

Sort the pro ts in decreasing order.

T1 and T8 are not complete within deadline.

testseries.ravindrababuravula.com/crm/Results/printresult/166956 18/28
3/13/2021 Download PDF

Question: 11  
Consider the following graph

Find a spanning tree with minimal total weight containing the edges {e, i} and {g, k} in the given weighted graph.

1.

30

2.

29

3.

28

4.

27

Not Attempt Correct Answer : Option2

Max Marks :  2.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 19/28
3/13/2021 Download PDF

Solution :  
The minimum spanning tree of graph {e, i} and {g, k}

Total weight = 1 + 1 + 1 + 1 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 3 + 4

                   = 29

Question: 12  
Use Hu man coding to encode the following symbols with the frequencies listed A : 0.08, B : 0.10, C : 0.12, D :
0.15, E : 0.20, F : 0.35. What is the average number of bits used to encode a character?

1.

3.45

2.

1.45

3.

2.75

4.

2.45

Not Attempt Correct Answer : Option4

Max Marks :  2.00 Marks Scored :   Time Taken :  -

Solution :  
 

testseries.ravindrababuravula.com/crm/Results/printresult/166956 20/28
3/13/2021 Download PDF

testseries.ravindrababuravula.com/crm/Results/printresult/166956 21/28
3/13/2021 Download PDF

Average number of bits used to encode a symbol using this encoding is

= (3 * 0.08) + (3 * 0.10) + (2 * 0.20) + (3 * 0.12) + (3 * 0.15) + (2 * 0.35)

= 2.45

Question: 13  
Given a graph, nd total number of strongly connected components

Not Attempt Correct Answer : 5

Max Marks :  2.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 22/28
3/13/2021 Download PDF

Solution :  
A directed graph is strongly connected if there is a path between all pairs of vertices. A strongly connected
component (SCC) of a directed graph is a maximal strongly connected subgraph.

More information about strongly connected components are

1. Time complexity is O(V+E) because using DFS

2. We can nd strongly connected components using kosaraju algorithm and Trojan’s algorithm

Kosaraju’s algorithm:

1) Create an empty stack ‘S’ and do DFS traversal of a graph. In DFS traversal, after calling recursive DFS for
adjacent vertices of a vertex, push the vertex to stack. 

2) Reverse directions of all arcs to obtain the transpose graph.

3) One by one pop a vertex from S while S is not empty. Let the popped vertex be ‘v’. Take v as source and do DFS
(call DFSUtil(v)). The DFS starting from v prints strongly connected component of v. 

Tarjan Algorithm:

1. DFS search produces a DFS tree/forest

2. Strongly Connected Components form subtrees of the DFS tree.

3. If we can nd head of such subtrees, we can print/store all the nodes in that subtree (including head) and that
will be one SCC.

4. There is no back edge from one SCC to another (There can be cross edges, but cross edges will not be used
while processing the graph).

testseries.ravindrababuravula.com/crm/Results/printresult/166956 23/28
3/13/2021 Download PDF

Question: 14  
Given a graph, nd the correct topological sequence using indegree elimination method

1.

0-3-1-5-6-7-2-4

2.

0-1-3-6-7-2-4-5

3.

0-4-3-1-2-5-6-7

4.

0-1-2-3-4-6-7-5

Not Attempt Correct Answer : Option3

Max Marks :  2.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 24/28
3/13/2021 Download PDF

Solution :  
Here, we have to take the sequence when indegree becomes ‘0’.

Step-1:

Question: 15  
Which of the following statement(s) is/are TRUE?

(i). Suppose that Dijkstra’s algorithm is run using a priority queue data structure for which insert and decrease
key operations take O(log log V) time, extract-min operation take O(√V) time then the running time of Dijkstra’s
algorithm on a directed weighted graph G = (V, E) containing non-negative edges will be  O(V √V + Elog log V)

(ii). If a topological sort exists for the vertices in a directed graph, then a DFS on the graph will produce no back
edges.

1.

Only (ii)

2.

None of the above

3.

Only (i)

4.

Both (i) and (ii)

Not Attempt Correct Answer : Option4

Max Marks :  2.00 Marks Scored :   Time Taken :  -

testseries.ravindrababuravula.com/crm/Results/printresult/166956 25/28
3/13/2021 Download PDF

Solution :  
(i). There are V extract-min operations, and E decrease key operations for the Dijkstra’s algorithm using priority
queue. So, time complexity is O(V √V + Elog log V)

(ii). Both parts of the statement hold if and only if the graph is acyclic.

ompare Report For Algorithms Topic Test – 3 (Greedy Algorithms)

Total Ques. Total Score 0.00/25.00

Maximum Marks 25.00 Percentage 0.00%

Attempted Ques. 0 Percentile 1.37%

Unattempted Ques. 15 Total Time 16 Sec

Correct Ques. 0 Rank

Incorrect Ques. 0 1368th

Total Ques. 15 Total Score 25.00/25.00

Maximum Marks 25.00 Percentage 100.00%

Attempted Ques. 15 Percentile 99.93%

Unattempted Ques. 0 Total Time 36 Mins 45 Sec

Correct Ques. 15 Rank

Incorrect Ques. 0 1st

gate2020deepanker

Total Ques. 15 Total Score 25.00/25.00

Maximum Marks 25.00 Percentage 100.00%

Attempted Ques. 15 Percentile 99.86%

Unattempted Ques. 0 Total Time 34 Mins 17 Sec

Correct Ques. 15 Rank

Incorrect Ques. 0 2nd

live.shaktipratap

Total Ques. 15 Total Score 25.00/25.00

Maximum Marks 25.00 Percentage 100.00%

Attempted Ques. 15 Percentile 99.78%

testseries.ravindrababuravula.com/crm/Results/printresult/166956 26/28
3/13/2021 Download PDF

Unattempted Ques. 0 Total Time 36 Mins 12 Sec

Correct Ques. 15 Rank

Incorrect Ques. 0 3rd

Namrita Varshney

Total Ques. 15 Total Score 23.00/25.00

Maximum Marks 25.00 Percentage 92.00%

Attempted Ques. 15 Percentile 99.71%

Unattempted Ques. 0 Total Time 22 Mins 24 Sec

Correct Ques. 14 Rank

Incorrect Ques. 1 4th

Priyanka Mall

Total Ques. 15 Total Score 23.00/25.00

Maximum Marks 25.00 Percentage 92.00%

Attempted Ques. 15 Percentile 99.64%

Unattempted Ques. 0 Total Time 44 Mins 50 Sec

Correct Ques. 14 Rank

Incorrect Ques. 1 5th

reddyvamsi150

Total Ques. 15 Total Score 23.00/25.00

Maximum Marks 25.00 Percentage 92.00%

Attempted Ques. 15 Percentile 99.57%

Unattempted Ques. 0 Total Time 43 Mins 57 Sec

Correct Ques. 14 Rank

Incorrect Ques. 1 6th

Akash Kumar

Total Ques. 15 Total Score 23.00/25.00

Maximum Marks 25.00 Percentage 92.00%

Attempted Ques. 14 Percentile 99.50%

Unattempted Ques. 1 Total Time 45 Mins 1 Sec

Correct Ques. 14 Rank

testseries.ravindrababuravula.com/crm/Results/printresult/166956 27/28
3/13/2021 Download PDF

Incorrect Ques. 0 7th

Subham

Total Ques. 15 Total Score 22.00/25.00

Maximum Marks 25.00 Percentage 88.00%

Attempted Ques. 15 Percentile 99.42%

Unattempted Ques. 0 Total Time 44 Mins 28 Sec

Correct Ques. 13 Rank

Incorrect Ques. 2 8th

Prakhar Omar

Total Ques. 15 Total Score 21.00/25.00

Maximum Marks 25.00 Percentage 84.00%

Attempted Ques. 14 Percentile 99.35%

Unattempted Ques. 1 Total Time 42 Mins 58 Sec

Correct Ques. 13 Rank

Incorrect Ques. 1 9th

Balaji Chundi

Total Ques. 15 Total Score 20.34/25.00

Maximum Marks 25.00 Percentage 81.36%

Attempted Ques. 15 Percentile 99.28%

Unattempted Ques. 0 Total Time 38 Mins 10 Sec

Correct Ques. 13 Rank

Incorrect Ques. 2 10th

jayduttpatel1729

testseries.ravindrababuravula.com/crm/Results/printresult/166956 28/28