Test: Greedy Method

# Test: Greedy Method

Test Description

## 10 Questions MCQ Test Question Bank for GATE Computer Science Engineering | Test: Greedy Method

Test: Greedy Method for Computer Science Engineering (CSE) 2022 is part of Question Bank for GATE Computer Science Engineering preparation. The Test: Greedy Method questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Greedy Method MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Greedy Method below.
Solutions of Test: Greedy Method questions in English are available as part of our Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) & Test: Greedy Method solutions in Hindi for Question Bank for GATE Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Greedy Method | 10 questions in 30 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study Question Bank for GATE Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Greedy Method - Question 1

### 6 files F1, F2, F3, F4, F5and F6 have 100, 200, 50, 80, 120, 150 records respectively. In what order should they be stored so as to optimize act. Assume each file is accessed with the same frequency.

Detailed Solution for Test: Greedy Method - Question 1

Since the access is sequential, greater the distance, greater will be the access time. Since all the files are referenced with equal frequency, overall access time can be reduced by arranging them as then ascending order of record as in option (a).

Test: Greedy Method - Question 2

### Which of the following algorithms solves the all pair shortest path problem?

Detailed Solution for Test: Greedy Method - Question 2

Dijkstra’s algorithm solves single source shortest path problem.
Warshall’s algorithm finds transitive closure of a given graph.
Prim’s algorithm constructs a minimum cost spanning tree for a given weighted graph.

Test: Greedy Method - Question 3

### Consider the graph in figure:​ Which of the following is a valid topological sorting?

Detailed Solution for Test: Greedy Method - Question 3

In topological sorting we have to list out all the nodes in such a way that whenever there is an edge connecting i and j, i should precede j in the listing, For some graphs, this is not at all possible, for some this can be done in more than one way.

Test: Greedy Method - Question 4

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m edges has the time complexity of

Detailed Solution for Test: Greedy Method - Question 4

Kruskal’s algorithm time complexity
= O(e log v)
= O(m log n)

Test: Greedy Method - Question 5

Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum weight and emin the edge with minimum weight. Which of the following statements is false?

Detailed Solution for Test: Greedy Method - Question 5

All edges are distinct weights.
Removal of emax may not disconnect G, because other edges may cover the vertices incident with emax.

Test: Greedy Method - Question 6

Consider the undirected graph below:

Using Prim’s algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

Detailed Solution for Test: Greedy Method - Question 6

Prim’s algorithm having special property which is, while finding minimum cost spanning tree, graph always be connected.

Now for correct options, we need to check while entry for any edge except for 1st edge only one vertex match from all left side (i.e. visited edges) edges.
(a) (E, G), (C, F ) : here for edge (C, F) no vertex match to (E, G). So not possible using Prim’s.
(b) (A, D), (A, B), (A, C), (C, F), (G, E ) : here for edge (G, E) no vertex match to any edge present left side of it so not possible using Prim’s.
(c) (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) not violated rule i.e. always connected in construction of MST.
So True.

Test: Greedy Method - Question 7

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.

Detailed Solution for Test: Greedy Method - Question 7

Bellman-Ford algorithm: O{nm)
Kruskal’s algorithm : O(mlog n)
Floyd-Warshall algorithm: O(n3)

Topological sorting : O(n + m)

Test: Greedy Method - Question 8

Let G{V, E) an undirected graph with positive edge weights. Dijkstra’s single source-shortest path algorithmn can be implemented using the binary heap data structure with time complexity?

Detailed Solution for Test: Greedy Method - Question 8

Dijkstra’s implementation for single source shortest path

(i) Using binary heap takes

(ii) .Using Fibonacci heap takes

Test: Greedy Method - Question 9

Consider the polynominal p(x) = a0 + a1x + a2x2 + a3x3, where  The minimum number of multiplications needed to evaluate p on an input x is

Detailed Solution for Test: Greedy Method - Question 9

So, 3 minimum number of multiplications needed to evaluate p on an input x.

Test: Greedy Method - Question 10

Consider a weighted complete graph G on the vertex set {v1, v2, .... vn} such that the weight of the edge (vi, vj) is 2 | i - j | .The weight of a minimum

Detailed Solution for Test: Greedy Method - Question 10

In the case of minimum spanning tree of a graph G we will add up to ( n - 1) vertices, so the weight of a minimum spanning tree of G

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests
 Use Code STAYHOME200 and get INR 200 additional OFF Use Coupon Code
Information about Test: Greedy Method Page
In this test you can find the Exam questions for Test: Greedy Method solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Greedy Method , EduRev gives you an ample number of Online tests for practice

## Question Bank for GATE Computer Science Engineering

61 videos|7 docs|102 tests