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?
weighted binary tree

(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) ].







8 comments :

  1. hello sir, the questions were very helpful in my revision and I want to send my gratitudes to you for the good work.
    thanks again

    ReplyDelete
  2. Sir,i couldn't understand the 5th question while checking its solution.
    kindly explain the 5th questions solution in detail.
    (The values for the position(i), position(j) where i = 14 and j =11, are)

    ReplyDelete
  3. It's really a great and http://magnum4dlive.com/tag/reinobarrack helpful piece of info. I'm happy that you just shared this helpful information with us. Please keep us up to date like this. Thanks for sharing. The Gaming Club bears a license from the meting out of Gibraltar, and claims to be one of a pick few casinos that have a license from the Gibraltar government. A believer of the Interactive Gaming Council (IGC), The Gaming Club follows every the guidelines laid next to by the organization, something that has following a long habit in it mammal approved as a great place to gamble online.

    Everything very nearly The Gaming Club feels good; be it the promotions, the big number of games, the multiple banking options on offer, the militant security measures, or the fair and responsible gaming practices the casino adopts.

    The Gaming Club motors along upon software developed by one of the giants of online gaming software press forward Microgaming. The software it uses is advocate and has a range of features expected to add up your online gambling experience and make you want to arrive put up to after every circular of gambling you pull off here.

    Another hallmark of a fine casino is the vibes of its customer support team, and The Gaming Club does not disappoint upon this front.
    http://magnum4dlive.com/tag/reinobarrack/


    ReplyDelete
  4. This is such a great resource that you are providing and you give it away for free. I love seeing blog that understand the value of providing a quality resource for fre
    คาสิโน

    ReplyDelete

  5. I like your post. I appreciate your blogs because they are really good. Please go to this website for Data Science course in Bangalore. These courses are wonderful for professionalism.

    ReplyDelete
  6. informative blog , thanks for sharing also i learnt this What Are the Career After Data Science Course

    ReplyDelete