Data Structure and Algorithm Analysis Set 1

Data Structure and Algorithm Analysis

Questions 1 to 10

1.	If all c(i, j )’s and r(i, j)’s are calculated, then OBST algorithm in worst case takes one of the following time. (a)  O(n log n)           (b)  O(n3)                  (c)  O(n2)                   (d)  O(log n)              (e)  O(n4).
2.	The following is a weighted binary tree, then what is the weighted array for the TVS problem? (a)  [9, 2, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 4]   (b)  [9, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 4, 6] (c)  [9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 6, 7, 4]   (d)  [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 6, 4] (e)  [9, 2, 0, 0, 0, 7, 0, 0, 0, 0, 6, 4, 0, 0].
3.	What are the entries of the array TREE[ ] for the above weighted binary tree for the TVS problem. (a)   [1, 2, 3, 4, 5, 6, 0, 0] (b)   [1, 2, 0, 0, 0, 3, 0, 0, 0, 0, 0, 0, 4, 5, 6] (c)   [1, 2, 3, 0, 0, 0, 0, 4, 5, 6] (d)   [1, 2, 3, 0, 0, 0, 0, 0, 4, 5, 6] (e)   [1, 2, 3, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 5, 6].
4.	For a 15-puzzle problem let the initial arrangement be the following one, then answer the questions 4 – 7 with the following arrangement. 10 13 15 7 9 1 4 14 12 8 6 11 2 5 3 What is the value of ‘x’ used to find the reachability of the solution? (a)  1                        (b)  0                        (c)  8                        (d)  10                      (e)  13.
5.	The values for the position(i), position(j) where i = 14 and j =11, are (a)  2, 8                    (b)  8, 2                    (c)  8, 13                  (d)  2, 13                  (e)  13, 8.
6.	The values for less(i), less(j) where i =5, j =7 are (a)  0, 6                    (b)  6, 0                    (c)  2, 4                    (d)  2, 6                    (e)  1, 6.
7.	What is the value to find the reachability of the problem with which you can say the solution is reachable or not? (a)  71                      (b)  72                     (c)  73                      (d)  69                      (e)  68.
8.	The upper bound on the time complexity of the nondeterministic sorting algorithm is (a)  O(n)                   (b)  O(n log n)           (c)  O(1)                   (d)  O( log n)            (e)  O(n2).
9.	The worst case time complexity of the nondeterministic dynamic knapsack algorithm is (a)  O(n log n)           (b)  O( log n)            (c)  O(n2)                  (d)  O(n)                   (e)  O(1).
10.	For the LCBB solution of knapsack problem with the data (p1–p4) = (10,10,12,18) and (w1–w4) = (2, 4, 6, 9) and m = 18, then the values of u(1) and ĉ(1) respectively are (a)  -38, -44               (b)  -44, -38              (c)  -44, -32               (d)  -32, -44              (e)  -32, -38.

Set 1  Set 2  Set 3  Set 4  Set 5  Set 6  Set 7  Set 8  Set 9  Set 10  Set 11  Set 12  Set 13  Set 14  Set 15  Set 16  Set 17  Set 18  Set 19  Set 20  Set 21  Set 22  Set 23  Set 24  Set 25  Set 26  

Set 27  Set 28  Set 29  Set 30 

Answers

1.	Answer : (b) Reason:  As we have to calculate c(i,j), w(i,j) and r(i,j).
2.	Answer : (d) Reason:  If we create a full binary tree then the non existing nodes will have the corresponding edge values to zero.
3.	Answer : (e) Reason:  If we create a full binary tree then the non existing nodes will have the corresponding node values to zero.
4.	Answer : (a) Reason:  ‘x’ takes the value 0 if it is there in shaded position which starts from second square and goes across every alternative square in the initial arrangement, otherwise it takes one. In this question it is there in shaded square.
5.	Answer : (c) Reason:  position( x ) = the square number with in which value ‘x’ is there.
6.	Answer : (e) Reason:  less( x ) is  the number of all js, such that  j < x and  position( j ) > position(x).
7.	Answer : (b) Reason:  The value to define reachable is  “sum of less(i) + x”, where i takes the values from 1 to 15, and ‘x’ is value defined in question(4).
8.	Answer : (a) Reason:  In the algorithm there is only one for loop which runs from 1 to n.
9.	Answer : (d) Reason:  In the algorithm there is only one for loop which runs from 1 to n.
10.	Answer : (d) Reason:  u(1) is the negation of sum of all profits so long as the weights as whole can be taken [ -(10+10+12)]. ĉ(1) is the value of u(1) and the negation  of profit of  the fraction of the next element taken to fill the knapsack [ u(1) + -( 6/9*18) ].

Set 1  Set 2  Set 3  Set 4  Set 5  Set 6  Set 7  Set 8  Set 9  Set 10  Set 11  Set 12  Set 13  Set 14  Set 15  Set 16  Set 17  Set 18  Set 19  Set 20  Set 21  Set 22  Set 23  Set 24  Set 25  Set 26  Set 27  Set 28  Set 29  Set 30