Dynamic Programming
Q11.
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?Q12.
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?Q13.
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?Q14.
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?Q15.
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)?Q16.
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)?Q17.
Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?