Algorithm
Q61.
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?Q62.
The subset-sum problem is defined as follows. Given a set of n positive integers, S={a_{1},a_{2},...,a_{n}} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X[i,j], 1\leq i\leq n, 0\leq j \leq W, is TRUE if and only if there is a subset of {a_{1},a_{2},...,a_{i} }whose elements sum to j. Which of the following is valid for 2\leq i\leq n and a_{i} \leq j \leq W?Q63.
The subset-sum problem is defined as follows. Given a set of n positive integers, S={a_{1},a_{2},...,a_{n}} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X[i,j], 1\leq i\leq n, 0\leq j \leq W, is TRUE if and only if there is a subset of {a_{1},a_{2},...,a_{i} }whose elements sum to j. Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?Q64.
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence (LCS) of x[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of the LCS of x[m] and Y[n] is given below: l(i, j) 0, if either i=0 or j=0 = expr1, if i,j>0 and x [i-1] Y [j -1] = expr2, if i,j>0 and x [i-1] Y [j -1] Which one of the following options is correct?Q65.
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?Q66.
Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1). How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?Q67.
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?Q68.
Let U = \{1, 2, 3\}. Let 2^U denote the powerset of U. Consider an undirected graph G whose vertex set is 2^U. For any A,B \in 2^U, (A,B) is an edge in G if and only if (i) A \neq B, and (ii) either A \subseteq B or B \subseteq A. For any vertex A in G, the set of all possible orderings in which the vertices of G can be visited in a Breadth First Search (BFS) starting from A is denoted by B(A). If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.Q69.
An articulation point in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?Q70.
G is an undirected graph with vertex set {v1, v2, v3, v4, v5, v6, v7} and edge set {v1v2, v1v3, v1v4 ,v2v4, v2v5, v3v4, v4v5, v4v6, v5v6, v6v7 }. A breadth first search of the graph is performed with v1 as the root node. Which of the following is a tree edge?