Greedyapproach
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.
Theory Explanation. 
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 FordFulkerson algorithm is bounded by :
O(E∗f)
 
O(E^{2}∗f)
 
O(E∗f^{2})
 
None of the above 
Question 2 Explanation:
****Excluded for evaluation***
→ The FordFulkerson method or FordFulkerson 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 FordFulkerson 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 FordFulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the EdmondsKarp algorithm, which runs in O(VE^{2})time.
→ The FordFulkerson method or FordFulkerson 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 FordFulkerson 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 FordFulkerson algorithm with guaranteed termination and a runtime independent of the maximum flow value is the EdmondsKarp algorithm, which runs in O(VE^{2})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(b^{d}) (c) Depth Limited Search iii) O(bm) (d) Iterative deepening Search iv) O(bl)Code:
(a)(iii), (b)(ii), (c)(iv), (d)(i)
 
(a)(ii), (b)(iii), (c)(iv), (d)(i)
 
(a)(i), (b)(ii), (c)(iv), (d)(iii)
 
(a)(i), (b)(iii), (c)(iv), (d)(ii)

Question 3 Explanation:
BFS → O(b^{d}) 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.
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
F3, F4, F1, F5, F6, F2  
F2, F6, F5, F1, F4, F3  
F1, F2, F3, F4, F5, F6  
Ordering is immaterial as all files are accessed with the same frequency. 
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
→ Final order is F3, F4, F1, F5, F6, F2
Question 5 
The number of spanning tree for a complete graph with 7 vertices are:
2^{5}  
7^{5}  
3^{5}  
2^{2×5} 
Question 5 Explanation:
To find number of spanning trees of a complete graph is n^{n2}.
Here, there are 7 nodes.
=7^{72}
=7^{5}
=16,807
Here, there are 7 nodes.
=7^{72}
=7^{5}
=16,807
Question 6 
What is the total number of spanning trees of a complete graph of 4 vertices (K_{4})?
16  
8  
4  
15 
Question 6 Explanation:
To find total number of spanning trees for complete graph using standard formula
n^{n2} = 4^{2} = 16
n^{n2} = 4^{2} = 16
Question 7 
Which of the following algorithms solves the singlesource shortest paths ?
Prim’s algorithm  
Floyd  Warshall algorithm  
Johnson’s algorithm  
Dijkstra’s algorithm 
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.