Fundamental Algorithms: Design and Analysis
Solution of Assignment: 4
1. In DFS, if you implement it using an iterative approach, which data
structure would you use?
(a) Queue
(b) Stack
(c) Linked List
(d) Heap
Answer (b)
Explanation: In Depth-First Search (DFS), the algorithm explores
as far down one branch as possible before backtracking. This behavior
mimics the Last In, First Out (LIFO) principle, which is naturally
supported by a stack data structure.
2. What would be the number of zeros in the adjacency matrix of the
given graph?
2 3
5 4
(a) 17
(b) 13
(c) 9
(d) 14
Answer - (a)
To determine the number of zeros in the adjacency matrix of the given
graph, we need to follow these steps:
Step 1: Understand the Graph The graph has: - 5 nodes: 1, 2, 3, 4, 5 -
Edges: 1 ↔ 2, 2 ↔ 3, 3 ↔ 5, 5 ↔ 4.
Step 2: Construct the Adjacency Matrix
1
An adjacency matrix for a graph with n nodes is an n×n matrix where:
- Entry (i, j) = 1 if there is an edge between node i and node j.
- Entry (i, j) = 0 if there is no edge between node i and node j.
Adjacency Matrix for the Given Graph:
0 1 0 0 0
1 0 1 0 0
0 1 0 0 1
0 0 0 0 1
0 0 1 1 0
Step 3: Count the Zeros The adjacency matrix has 5 × 5 = 25 total
entries. - Non-zero entries represent edges. The graph has 4 edges, and
since the matrix is symmetric, there are 2 × 4 = 8 non-zero entries.
Number of zeros = 25 − 8 = 17.
Final Answer: a) 17
3. Which of the following is false in the case of a spanning tree of a graph
G?
(a) It is tree that spans G.
(b) It is a sub-graph of the G.
(c) It includes every vertex of the G.
(d) It can be either cyclic or acyclic.
The correct answer is:
d) It can be either cyclic or acyclic.
Explanation: A spanning tree of a graph G is a subgraph that satisfies
the following properties:
1. It is a tree, which means it is acyclic (contains no cycles).
2. It spans G, meaning it includes all the vertices of G.
3. It is a subgraph of G, using only the edges present in G.
4. If G has n vertices, a spanning tree of G has exactly n − 1 edges.
Why Option (d) is False:
2
A spanning tree is always acyclic by definition. If it contains a cycle, it
would not be a tree anymore. Thus, a spanning tree cannot be cyclic.
Why Other Options Are True:
1. Option (a): A spanning tree spans G, meaning it includes all the
vertices of G.
2. Option (b): A spanning tree is a subgraph of G.
3. Option (c): A spanning tree includes every vertex of G.
Thus, option (d) is false.
4. The time complexity of BFS for a graph with V vertices and E edges
is:
(a) O(V + E)
(b) O(V log V )
(c) O(V E)
(d) O(V log E)
Answer-(a)
5. In a graph with 5 vertices, what is the number of comparisons per-
formed by the Floyd-Warshall algorithm?
(a) 5
(b) 25
(c) 125
(d) 625
The correct answer is:
c) 125
Explanation:
The Floyd-Warshall algorithm is used to find the shortest paths be-
tween all pairs of vertices in a graph. Its time complexity is O(V 3 ),
where V is the number of vertices.
Number of Comparisons:
3
For a graph with V = 5 vertices:
- The algorithm involves three nested loops:
1. Outer loop (intermediate vertex k): Runs V = 5 times.
2. Middle loop (source vertex i): Runs V = 5 times for each k.
3. Inner loop (destination vertex j): Runs V = 5 times for each i and
k.
- Total comparisons = 5 × 5 × 5 = 125.
Thus, the number of comparisons performed by the Floyd-Warshall
algorithm in this case is 125.
Final Answer: c) 125
6. The following matrix shows the shortest distances between every pair
of vertices?
0 4 5 5 7
3 0 1 4 6
2
(a) 6 0 3 6
3 7 1 0 2
1 5 5 4 0
0 4 5 5 7
3 0 1 4 6
2
(b) 6 0 3 5
3 7 1 0 2
1 5 5 4 0
4
0 4 5 5 7
3 7 1 0 2
2
(c) 6 0 3 5
3 0 1 4 6
1 5 5 4 0
3 0 1 4 6
2 6 0 3 5
3
(d) 7 1 0 2
1 5 5 4 0
0 4 5 5 7
Answer: b
7. Consider the following graph:
Among the following sequences:
I. a b c d e f
II. a b f c e d
III. a b f e d c
IV. a f d e b c
Which are the depth-first traversals of the above graph starting from
vertex a?
5
(a) I, II and IV only
(b) I and IV only
(c) II, III and IV only
(d) I, II and III only
Answer: d
8. Breadth-First Search Algorithm is equivalent to which of the traversals
in trees?
(a) Pre-order traversal
(b) Post-order traversal
(c) In-order traversal
(d) Level-order traversal
Answer: d
Explanation: In level-order traversal of trees, we process the root first
and then child from level wise.
9. The time complexity of Prim’s algorithm using an adjacency matrix is:
(a) O(V + E)
(b) O(V log V )
(c) O(V E)
(d) O(V 2 )
Answer-(d)
10. In MST, Prims algorithm selects an edge
(a) with maximum number of vertices connected to it so that MST
has least diameter.
(b) that adds new vertices to partially constructed tree with minimal
increment in cost and that does not introduce a cycle.
(c) with minimum weight so that cost of MST is always minimum.
6
(d) that introduces a cycle.
The correct answer is:
b) That adds new vertices to the partially constructed tree with mini-
mal increment in cost and that does not introduce a cycle.
Explanation:
Prim’s Algorithm is a greedy algorithm that constructs a Minimum
Spanning Tree (MST) by:
1. Starting with an arbitrary vertex.
2. Selecting the edge with the smallest weight that connects a vertex
in the partially constructed tree to a vertex outside the tree.
3. Ensuring no cycles are introduced in the process.
4. Repeating until all vertices are included in the MST.
Why Other Options Are Incorrect:
1. Option (a): Prim’s algorithm does not consider the number of ver-
tices connected or the diameter of the MST.
2. Option (c): While it chooses edges with minimum weight, it also
ensures they connect new vertices and avoid cycles. Hence, this is
incomplete.
3. Option (d): Prim’s algorithm explicitly avoids introducing cycles.
Final Answer:
b) That adds new vertices to the partially constructed tree with mini-
mal increment in cost and that does not introduce a cycle.
