Algorithms MCQ - 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.

Both I and II

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?

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.

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?

So total 4 rooms are required.

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

T₁

T₂

T₃

T₅

T₇

T₈

T₉

T₄ and T₆ are left out

40 What is the maximum profit earned?

Total profit = 15 + 20 + 30 + 18 + 26 + 16 + 25 = 147