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.
Theory Explanation. |
Question 2 |
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?
(E, G), (C, F), (F, G), (A, D), (A, B), (A, C) | |
(A, D), (A, B), (A, C), (C, F), (G, E), (F, G) | |
(A, B), (A, D), (D, F), (F, G), (G, E), (F, C) | |
(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)
|
Question 2 Explanation:
(A) and (B) produce disconnected components with the given order in options which is never allowed by Prim's algorithm.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 3 |
Which of the following algorithms solves the single-source shortest paths ?
Prim’s algorithm | |
Floyd - Warshall algorithm | |
Johnson’s algorithm | |
Dijkstra’s algorithm
|
Question 3 Explanation:
Dijkstra’s algorithm is a Single source shortest path algorithm used to find the shortest path using Greedy approach.
Question 4 |
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 :
O(E∗f)
| |
O(E2∗f)
| |
O(E∗f2)
| |
None of the above |
Question 4 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.
→ 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 5 |
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)-(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 5 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.
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 6 |
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 6 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 7 |
The number of spanning tree for a complete graph with 7 vertices are:
25 | |
75 | |
35 | |
22×5 |
Question 7 Explanation:
To find number of spanning trees of a complete graph is nn-2.
Here, there are 7 nodes.
=77-2
=75
=16,807
Here, there are 7 nodes.
=77-2
=75
=16,807
Question 8 |
What is the total number of spanning trees of a complete graph of 4 vertices (K4)?
16 | |
8 | |
4 | |
15 |
Question 8 Explanation:
To find total number of spanning trees for complete graph using standard formula
nn-2 = 42 = 16
nn-2 = 42 = 16
There are 8 questions to complete.