Algorithms - Algorithm Design Techniques

Avatto > > GATE COMPUTER SCIENCE > > Practice Questions > > Computer Science And Information Technology > > Algorithms > > Algorithm Design Techniques

36. G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTS) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e.
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.

Answer
Comment
Array

Option : C
Explanation :
Both I and II

You must be logged in to post a comment.

You must be logged in to post a comment.

37. 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?

Answer
Comment
Array

Option : D
Explanation :
Option “A” and “B” produce disconnected components which is never allowed by primes algorithm In option “C” if vertex “A” is randomly chosen, then first edge must be (A,D) so option “D” is correct.

You must be logged in to post a comment.

You must be logged in to post a comment.

38. The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “a_sb_sc_sa_ed_sc_ee_sf_sb_ed_eg_se_ef_eh_sg_eh_e”
Here, x_s denotes the starting time and x_e denotes the ending time of activity X. W 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?

Answer
Comment
Array

Option : B
Explanation :
So total 4 rooms are required.

You must be logged in to post a comment.

You must be logged in to post a comment.

39. Are all tasks completed in the schedule that gives maximum profit?

Answer
Comment
Array

Option : D
Explanation :
T₁ T₂ T₃ T₅ T₇ T₈ T₉
T₄ and T₆ are left out

You must be logged in to post a comment.

You must be logged in to post a comment.

40. What is the maximum profit earned?

Answer
Comment
Array

Option : A
Explanation :
Total profit = 15 + 20 + 30 + 18 + 26 + 16 + 25 = 147

You must be logged in to post a comment.

You must be logged in to post a comment.

Related Quiz.
Algorithm Design Techniques

Forgot your password?

I agree with the Terms.