Birla Institute of Technology and Science, Pilani
CS F211 (Data Structures and Algorithms) Comprehensive Examination
120 minutes 126 marks
Note: Answer all the parts of each question together
𝑖2
Q1(a) [2 marks]. Number of statements executed is ∑𝑛𝑖=1 . What is the tight asymptotic time
2𝑖
complexity?
Solution: O(1) [0/2Marks]
Q1(b) [2 marks]. A binomial heap with 29 nodes contains _________ binomial trees. Fill in the blank.
Solution: 29 in binary is 1 1 1 0 1
B0, B2, B3, B4 [0/2Marks]
Q1(c) [2 marks]. Consider the Directed Acyclic Graph G shown in Figure 1. How many topological sorts
can G have?
Solution: 8 [0/2Marks]
B E H
A D G J
C F I
Figure 1
Q1(d) [2 marks]. TRUE/FALSE. “To find whether two binary search trees are identical, it is sufficient
to find their inorder traversals and compare the outputs”. If TRUE, justify your answer. If FALSE, give
a counter example.
Solution: False: Counter example is given below:
T1: The root is 4 and its left child is 2
T2: The root is 2 and its right child is 4 [1M for False; 1M for counter example]
Q1(e) [2 marks]. Consider a complete 3-ary tree T with 364 nodes. How many internal nodes T can
have? And, how many leaves T can have?
Solution: Internal nodes: 121; leaves: 243 [1M + 1M]
Q2 [18 marks]. For the graph G shown in Figure 2, run Floyd Warshall algorithm. Show all the
intermediate matrices (i.e. D(0) to D(5) and (0) to (5)).
Figure 2
Solution and Marking Scheme:
Six pi matrices of 1M each.
Six D matrices of 2M each.
Q3 [10 + 10 = 20 marks]. Consider a Red-Black Tree R, where each node contains the following
attributes: key, left-child, right-child, color, parent. Suppose, in addition to these attributes, each node
of a RB tree contains one additional attribute “subtree-size”. “subtree-size” of a node N is the number
of internal nodes in the subtree rooted at N, including N itself. That is, for any node N,
subtree-size (N) = subtree-size(left-child(N)) + subtree-size (right-child(N)) + 1.
You can assume the subtree-size of sentinel node to be zero. Answer the following questions:
a) While inserting a node in a RB-tree, there were two steps. As a first step the new node is
inserted as a child of an existing node. As a second step, we move up the tree (if required)
performing rotations and changing colors to maintain the required properties. With respect
to this, explain how to maintain the subtree-size attribute during first step. In addition, modify
the left-rotation algorithm given in your textbook to maintain the sub-tree size attribute
during left-rotation.
Solution: [0/5 Marks for explaining how to maintain the sub-tree size attribute during the first
step. 0/5 Marks for the modified pseudo code to maintain subtree size information during left
rotation.]
To maintain the subtree sizes in the first phase, we simply increment x.size for each node x on
the simple path traversed from the root down toward the leaves. The new node added gets a
size of 1. Since there are O(lg n) nodes on the traversed path, the additional cost of
maintaining the size attributes is O(lg n).
For left-rotate, referring to the code for LEFT-ROTATE (T, x) in Section 13.2, we add the
following lines:
13 y.size = x.size
14 x.size = x.left.size + x.right.size + 1
b) Using subtree-size attribute, write an O(lg n) time non-recursive algorithm to find the kth
smallest element in the RB-TREE. This algorithm takes the root and k as input parameters.
[Marking Scheme: 4M for correctly searching the kth smallest element towards left child. 4M
for correctly searching the kth smallest element towards right child. 2M for loop and correctly
returning the element. These 2M were given only if traversal towards left and right were
correct.]
Q4 [6 + 10 = 16 marks]. Consider an undirected graph G = (V, E). A special-vertex u V is a vertex of
G such that removing it and all its incident edges divides the graph G into two disconnected graphs.
For example, in the graph shown in Figure 3, vertex D and vertex C are special vertices. Answer the
following questions:
a) What is the maximum number of special-vertices a connected graph of order M can contain?
Justify your answer.
Solution:
(M – 2); (2 marks)
We can justify by using an example of such a graph. A connected graph of order M can have its
vertices arranged in a straight line as shown below:
1 2 3 4 M
2
Except for the vertices 1 and M, the remaining vertices in the graph are articulation points. There
are M-2 such nodes. If we consider an M-order graph G with more edges, the number of special
vertices in G is less than the number vertices in the above graph. Hence, the solution is justified.
(If the justification is clear and completely correct then 4 marks; if justification is
incomplete/unclear/partially correct, then 2 marks; if justification is wrong, then zero marks)
b) Using DFS, write an algorithm to compute all special vertices in a given graph G.
C D F
B A E
Figure 3
Solution:
Global variable: time;
Consider a graph G with n vertices; u is a vertex in G;
Algorithm CutVertices_DFS(G, u, boolean visited[n], int disc[n], int low[n], int parent[n],
boolean ap[n])
{visited: keeps track of visited nodes}
{disc keeps track of discovery time}
{low[u] keeps track of earliest visited vertex that can be reached from subtree rooted with u}
{parent keeps track the parent of each node}
{ap keeps track of special vertices}
{All these arrays are initialized appropriately}
Int children = 0;
visited[u] = true
disc[u] = low[u] = ++time
for each node v adjacent to u
if(!visited[v])
children++
parent[v] = u
CutVertices_DFS(G, v, visited, disc, low, parent, ap) (2 marks)
low[u] = min(low[u], low[v]) (1 marks)
if(parent[u] == NIL && children > 1) (for this if section 2 marks)
ap[u] = true
if(parent[u] != NIL && low[v] >= disc[u]) (for this if section 2 marks)
ap[u] = true;
else if( v != parent[u]) (for this if section 1 marks)
low[u] = min(low[u], disc[v])
(Remaining 2 marks for the remaining code of the algorithm)
Q5 [20 marks]. Assume that you are given a weighted directed graph G, where edge weights
are strictly positive, and a source node S in G. You have to modify Dijkstra’s shortest-path
algorithm to maintain the number of different shortest paths from S to v, for all v, and to
output a shortest path with the smallest number of edges when there exists multiple shortest
paths from S to v. Write the modified algorithm, and prove the correctness of the modified
algorithm.
Solution:
Initialize_Single_Source(G,s) Relax(u,v,w)
{ {
For each vertex vεV[G] If(d[v]>d[u]+w(u,v))
Do d[v]=infinity {
Pi[v]=NIL d[v]=d[u]+w(u,v)
NumPaths[v]=0 NumPaths[v]=NumPaths[u] [2M]
D[s]=0 NumEdges[v]=NumEdges[u]+1 [2M]
NumPaths[s]=1 [1M] Pi[v]=u
NumEdges[s]=0 [1M] }
For each vertex vεG.Adj[s] [2M] Else if(d[v]==d[u]+w(u,v))
NumPaths[v]=1 {
} NumPaths[v]=NumPaths[u]+NumPaths[v]
[2M]
If(NumEdges[v]>NumEdges[u]+1) [2M]
NumEdes[v]=NumEdges[u]+1
Pi[v]=u
}
}
Proof:
Correctness of count of number of paths:
We can prove the correctness of the modified algorithm using proof by contradiction.
Assume that the modified method returns less number of paths than the actual number of paths of
length d[u] from s to u. That implies, there exists a vertex x in adj(u) such that, d[x] + w(x, u) = d[u]. If
this is the case, then while processing node x (since the algorithm considers each node for processing),
this path would have been counted in the else if loop of the modified RELAX method. Hence, our
assumption is wrong. (2M)
Assume that the modified method returns more number of paths than the actual number of paths of
length d[u] from s to u. That implies, there exists at least one vertex x in adj(u) such that, d[x] + w(x,
u) > d[u], but this path was counted as a shortest path with length d[u], which is impossible according
to our modified algorithm. Hence, our assumption is wrong. The modified algorithm returns the
correct result. (2M)
Correctness of returning the shortest path with the smallest number of edges:
Assume that there exists a shortest path “P” of length d[u] with a lower number of edges than the one
returned by the modified algorithm. (1M)
Assume that the nodes on P are: x1, x2, . . ., x, u, x is in adj(u). Since the length of P is d[u], d[x] + w(x,
u) = d[u], and according to our assumption, (NumEdges[x] +1) < NumEdges[u]. (2M)
If so, then while processing x, the modified algorithm would have modified the shortest path with the
smallest number edges as P according to the else if loop of the modified RELAX method. (1M)
Hence, our assumption is wrong. The modified algorithm returns the correct result.
Q6 [8 + 8 + 5 = 21 marks].
a) Consider the below given algorithm which takes a connected graph “G” and a weight function
“w” as inputs and returns a set of edges “Tree” as output.
Algorithm ALT_MST (G, w)
Tree = E {E is the set of edges in G; assume that the edge weights are positive and
distinct}
for each edge e, taken in decreasing order of weights
If e belongs to a cycle in Tree, then
Tree = Tree – {e}
return Tree
Does ALT_MST compute a minimum spanning tree of G? Justify your answer. That is, if your
answer is YES, prove that ALT_MST produces an MST, otherwise prove that ALT_MST does not
produce an MST.
Solution:
Yes (1 mark)
Proof:
To proceed with the actual proof, first we have to prove another property: “if G has a cycle,
then the edge with the greatest cost from that cycle does not belong to any MST”
Assume that G(V, E) is an undirected connected weighted graph. Also, assume that G has at
least one cycle. Choose any one of the cycles. For that cycle, let e be an edge that has greatest
weight than all other edges in the cycle. Now, assume that e does belong to a MST T of G, and
derive a contradiction. Consider the disconnected subgraph with edges T \ {e} which has two
connected components. Since G has a cycle containing e, there must be another edge in the
cycle that connects the two components of T \ {e}. Let this edge be (u,v). This edge has smaller
cost than e. But then we could define a spanning tree of a lower cost by deleting e from T and
adding this (u,v) edge, which contradicts our assumption that e belongs to the MST. Hence, if
G has a cycle, then the edge with the greatest cost from that cycle does not belong to any MST
of G. (2.5 marks)
In kth stage, the algorithm considers the kth largest cost edge, say “x”. If that edge belongs to
a cycle in the remaining graph Tree, then all edges in that cycle and in Tree must have smaller
weight than x. Thus, the edge cannot belong to the MST from the result that was proved in
the previous paragraph. (1.5 marks)
The algorithm cannot terminate with T having a cycle, since the algorithm considers each edge
in each cycle and removes the edge with the largest cost. (1.5 marks)
The algorithm also cannot terminate with T being disconnected, since it remove the edges
only when they belong to a cycle, and removing an edge that belongs to a cycle does not
disconnect the graph. (1.5 marks)
Thus the algorithm terminates by returning the MST.
b) You are given an undirected connected graph G = (V, E). E’ is a subset of E such that for all e
in E’, the weight is positive, and for all f in E-E’ the weight is negative. Modify either of the
MST algorithms discussed in the class so that it outputs an MST for graph G and all such graphs.
Write the modified algorithm and prove its correctness.
Solution: Algorithm Modified_Kruskal(G, w)
Find the edge (u, v) with the smallest edge weight in G (1 mark)
For each edge (x, y) in G (For this for section: 2 marks)
w(x,y) += (absolute value of w(u, v))
Proof:
Consider a graph G with n vertices and m edges with positive edge weights.
Assume that T is the minimum spanning tree of G returned by the Kruskal’s algorithm.
Assume that the order in which edges were added to T is: e1, e2, e3, . . ., en-1; that implies,
w(e1) <= w(e2) <= w(e3) <= . . . <=w(en-1) (1 marks)
Now, add a positive constant “c” to the weight of each edge. (1 mark)
This addition does not change the order in which Kruskal’s algorithm picks the edges to include
in T, since addition of the same constant to each edge weight preserves the order of their
edge weights, that is, w(e1) <= w(e2) <= w(e3) <= . . . <=w(en-1). Thus, after the addition,
Kruskal’s algorithm returns the same tree T but with increased minimum cost. (2 mark)
In the modified Kruskals’s algorithm, we are adding a constant to the weight of each edge.
From the above argument, the modified algorithm returns an MST for the given input graph.
(1 mark)
c) We want to insert the keys 15, 119, 228, 5, 12, 27, 100, and 43 into a hash table H having 8
slots. Assume that the addresses of H starts from 0, the hash function is h(k) = k mod 8, and
collisions are resolved by separate chaining.
Solution: [0/5 marks]
Q7 [10 + 5 + 6 = 21 marks].
a. Consider an array A containing elements 3, 29, 19, 9, 14, 15, 17, 7, in that order. Assume that
A is representing a max-heap in an intermediate state; this state was reached by performing
the following operations: the element at the root, say x, was deleted, and the last element in
the heap was moved to the root. What was the original max-heap before deleting x? What is
an appropriate value for x? How does A change after performing Max-Heapify at the root.
Show all intermediate steps of Max-Heapify.
Solution:
Initial max-heap: [x, 29, 19, 9, 14, 15, 17, 7, 3, 8, 6] (2 marks)
Appropriate value for x: x > 29 (2 marks)
Max-heapify intermediate steps:
[6, 29, 19, 9, 14, 15, 17, 7, 3, 8]
[29, 6, 19, 9, 14, 15, 17, 7, 3, 8] (2 marks)
[29, 14, 19, 9, 6, 15, 17, 7, 3, 8] (2 marks)
[29, 14, 19, 9, 8, 15, 17, 7, 3, 6] (2 marks)
b. Consider a binomial heap H with n elements. Using the size property of binomial trees and the
maximum number of binomial trees in n-node binomial heap, prove that the highest number
of nodes in any binomial tree in H is 2^(floor(log2n)). Here “^” stands for the power operator.
Solution:
Maximum number of binomial trees in a binomial heap H of n nodes is: floor(ln(n)) + 1 (ln is
log2n) (1 mark)
The highest order binomial tree in a binomial heap of n nodes is: Bfloor(ln(n)) (2 marks)
From the size property of binomial trees, a binomial tree of order k has 2k nodes (1 mark)
Hence, the highest number of nodes in any binomial tree in H is: 2^(floor(ln(n))) (1 mark)
c. Let G = (V, E) be a connected directed graph with positive edge weights. Consider the
statement, “Bellman-ford algorithm can be used to find the minimum spanning tree of G”. Is
this statement TRUE or FALSE? Justify your answer.
Solution: [1M + 5M]
False
Counter example: A connected directed graph (that is, a directed graph with one or more
paths between every pair of vertices) and its minimum spanning tree and the spanning tree
produced by the Bellman-Ford algorithm is given below.
b
5 1
5 d
a
1
1
5
c
b
5 1
d
a
1
c
b
5
5 d
a
5
c
