Test: Greedy Techniques- 2 - Computer Science Engineering (CSE) MCQ

(a) and (b) are always true. (c) is false because (b) is true. (d) is true because all edge weights are distinct for G.

Using Topological Sort, we can find single source shortest paths in O(V+E) time which is the most efficient algorithm. See following for details. Shortest Path in Directed Acyclic Graph

A and B are False  : The idea behind Prim’s algorithm is to construct a spanning tree - means all vertices must be connected but here vertices are disconnected C. False. Prim's is a greedy algorithm and At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. In this option weight of AB<AD so must be picked up first. D.TRUE. It represents a possible order in which the edges would be added to construct the minimum spanning tree. Prim’s algorithm is also a Greedy algorithm. It starts with an empty spanning tree. The idea is to maintain two sets of vertices. The first set contains the vertices already included in the MST, the other set contains the vertices not yet included. At every step, it considers all the edges that connect the two sets, and picks the minimum weight edge from these edges. After picking the edge, it moves the other endpoint of the edge to the set containing MST. 

In the sequence (b, e) (e, f) (b, c) (a, c) (f, g) (c, d) given option D, the edge (a, c) of weight 4 comes after (b, c) of weight 3. In Kruskal's Minimum Spanning Tree Algorithm, we first sort all edges, then consider edges in sorted order, so a higher weight edge cannot come before a lower weight edge.

With BFS, we first find explore vertices at one edge distance, then all vertices at 2 edge distance, and so on.

First we will pick item_4 (Value weight ratio is highest). Second highest is item_1, but cannot be picked because of its weight. Now item_3 shall be picked. item_2 cannot be included because of its weight. Therefore, overall profit by V_greedy = 20+24 = 44 Hence, V_opt - V_greedy = 60-44 = 16 So, answer is 16.

Below diagram shows a minimum spanning tree. Highlighted (in green) are the edges picked to make the MST.

In the right side of MST, we could either pick edge ‘a’ or ‘b’. In the left side, we could either pick ‘c’ or ‘d’ or ‘e’ in MST. There are 2 options for one edge to be picked and 3 options for another edge to be picked. Therefore, total 2*3 possible MSTs.

The shortest path remains same. It is like if we change unit of distance from meter to kilo meter, the shortest paths don't change.

a = 0.11 b = 0.40 c = 0.16 d = 0.09 e = 0.24 we will draw a huffman tree:

now huffman coding for character:

a = 1111
b = 0
c = 110
d = 1111
e = 10
lenghth for each character = no of bits * frequency of occurence:
a = 4 * 0.11
   = 0.44
b = 1 * 0.4
   =  0.4
c = 3 * 0.16
   = 0.48
d = 4 * 0.09
   =  0.36 
e = 2 * 0.24
   = 0.48
Now add these lenght for average length:
 0.44 + 0.4 + 0.48 + 0.36 + 0.48 = 2.16

The minimum weight edge on any s-t cut is always part of MST. This is called Cut Property. This is the idea used in Prim's algorithm. The minimum weight cut edge is always a minimum spanning tree edge. Why B (the weighted shortest path from s to t) is not an answer? See below example, edge 4 (lightest in highlighted red cut from s to t) is not part of shortest path.

There can be more than one paths with same weight. Consider a path with one edge of weight 5 and another path with two edges of weights 2 and 3. Both paths have same weights.

This question is based on the Optimal Storage on Tape problem which uses greedy approach to find the optimal time to retrieve them.
There are n programs of length L that are to be stored on a computer tape. Associated with each program i is a length Li. So in order to
retrieve these programs most optimally, we need to store them in the non-decreasing order of length Li.
So, the correct order is F3, F4, F1, F5, F6, F2

(a,c), (a,d), (d,b), (b,g), (g,h), (h,f), (h,i), (i,j), (i,e) = 31   Background required - Minimum Spanning Tree (Prims / Kruskal) In these type of questions, always go for kruskal’s algorithm to find out the the minimum spanning tree as it is easy and there are less chances of doing silly mistakes. Algorithm: Always pick the minimum edge weight and try to add to current forest (Collection of Trees) if no cycle is formed else discard. As soon as u have added n-1 edges to the forest, stop and you have got your minimum spanning tree. See the below image for construction of MST of this question.

Weight of minimum spanning tree = Sum of all the edges in Minimum Spanning tree = 31

Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.

There are 3 choices for the first slot, and then 2 for the third slot. That leaves one letter out of I,A,C unchosen and there are 2 slots that one might occupy. After that, the L′s must go in the 2 unfilled slots. Hence the answer is,
3×2×1×2 = 12 
Option (A) is correct.

d(r, u) and d(r, v) will be equal when u and v are at same level, otherwise d(r, u) will be less than d(r, v)

When shortest path shortest path from v1 (one of the vertices in V1) is computed. G1 is connected if the distance from v1 to any other vertex in V1 is greater than 0, otherwise G1 is disconnected.

According to given data,
Number of pieces    Possible max profits with combination of rod size 
7    7 (1, 1, 1, 1, 1, 1, 1)
6    10 (2, 1, 1, 1, 1, 1)
5    13 (2, 2, 1, 1, 1)
4    16 (2, 2, 2, 1)
3    18 (2, 2, 3)
2    18 (6, 1)
1    18 (7)
Therefore, Option (A) and (C) are correct.

In every cycle, the weight of an edge that is not part of MST must by greater than or equal to weights of other edges which are part of MST. Since all edge weights are distinct, the weight must be greater. So the minimum possible weight of ED is 7, minimum possible weight of CD is 16 and minimum possible weight of AB is 10. Therefore minimum possible sum of weights is 69.

Note that the given graph is undirected, so an edge (u, v) also means (v, u) is also an edge. Since a shorter path can always be obtained by using edge (u, v) or (v, u), the difference between d(u) and d(v) can not be more than 1.