Greedy-approach

Question 1

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below: 

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I);

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.

A
Theory Explanation.
       Algorithms       Greedy-approach       GATE 1994
Question 2

E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulkerson algorithm is bounded by :

A
O(E∗f)
B
O(E2∗f)
C
O(E∗f2)
D
None of the above
       Algorithms       Greedy-approach       UGC-NET CS 2018 JUNE Paper-2
Question 2 Explanation: 
****Excluded for evaluation***
→ The Ford-Fulkerson method or Ford-Fulkerson algorithm (FFA) is a greedy algorithm that computes the maximum flow in a flow network.
→ It is called a "method" instead of an "algorithm" as the approach to finding augmenting paths in a residual graph is not fully specified or it is specified in several implementations with different running times.
→ the runtime of Ford-Fulkerson is bounded by O(E*f), where E is the number of edges in the graph and f is the maximum flow in the graph. This is because each augmenting path can be found in O(E) time and increases the flow by an integer amount of at least 1, with the upper bound f.
→ The variation of the Ford-Fulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the Edmonds-Karp algorithm, which runs in O(VE2)time.
Question 3

Consider the following terminology and match List 1 and List 2 and choose the correct answer from the code given below

    b = branch factor
    d = depth of shallowest solution
    M = Maximum depth of the search tree
    l = depth limit
    List 1                          List 2
(a) BFS                          i) O(bd)
(b) DFS                         ii) O(bd)
(c) Depth- Limited Search      iii) O(bm)
(d) Iterative deepening Search  iv) O(bl)
Code:
A
(a)-(iii), (b)-(ii), (c)-(iv), (d)-(i)
B
(a)-(ii), (b)-(iii), (c)-(iv), (d)-(i)
C
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
D
(a)-(i), (b)-(iii), (c)-(iv), (d)-(ii)
       Algorithms       Greedy-approach       UGC-NET CS 2018 DEC Paper-2
Question 3 Explanation: 
BFS → O(bd) worst case space complexity
DFS → O(bm) worst case space complexity
Depth - Limited Search → O(bl)
Iterative deepening Search → O(bd)
Note:
Based upon BFS and DFS we can find the solution.
Question 4
Six files F1, F2, F3, F4, F5 and 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
A
F3, F4, F1, F5, F6, F2
B
F2, F6, F5, F1, F4, F3
C
F1, F2, F3, F4, F5, F6
D
Ordering is immaterial as all files are accessed with the same frequency.
       Algorithms       Greedy-approach       ISRO CS 2015       Video-Explanation
Question 4 Explanation: 
Optimal merge pattern will give the optimal result after performing sorted order. Every time it will take least frequency elements and performing merging.
→ Final order is F3, F4, F1, F5, F6, F2
Question 5
The number of spanning tree for a complete graph with 7 vertices are:
A
25
B
75
C
35
D
22×5
       Algorithms       Greedy-approach       ISRO CS 2015       Video-Explanation
Question 5 Explanation: 
To find number of spanning trees of a complete graph is nn-2.
Here, there are 7 nodes.
=77-2
=75
=16,807
Question 6

What is the total number of spanning trees of a complete graph of 4 vertices (K4)?

A
16
B
8
C
4
D
15
       Algorithms       Greedy-approach       JT(IT) 2018 PART-B Computer Science
Question 6 Explanation: 
To find total number of spanning trees for complete graph using standard formula
nn-2 = 42 = 16
Question 7
Which of the following algorithms solves the single-source shortest paths ?
A
Prim’s algorithm
B
Floyd - Warshall algorithm
C
Johnson’s algorithm
D
Dijkstra’s algorithm
       Algorithms       Greedy-approach       UGC NET CS 2018 JUNE Paper-2
Question 7 Explanation: 
Dijkstra’s algorithm is a Single source shortest path algorithm used to find the shortest path using Greedy approach.
There are 7 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access