Data Structure and Algorithm Analysis Set 27

Data Structure and Algorithm Analysis

Questions 261 to 270

261.	Which of the following formulas in Omega notation best represent the expression n²+35n+6? (a)  Ω (n³)                (b)  Ω (n²)                (c)  Ω (n)                 (d)  Ω (35)               (e)  Ω (6).
262.	What term is used to describe an O(n) algorithm? (a)  Constant                                          (b)  Non Polynomial Deterministic           (c)  Logarithmic                                      (d)  Quadratic                                        (e)  Linear.
263.	Express the formula (n - 2)*(n - 4) using θ notation: (a)  θ (n2)                 (b)  θ (8)                  (c)  θ (log n)            (d)  θ (n)                  (e)  θ (1).
264.	Read the following statements carefully and pick the right most option. I.     A linear algorithm to solve a problem must perform faster than a quadratic algorithm to solve the same problem. II.     An algorithm with worst case time behavior of 3n takes at least 30 operations for every input of size n=10. (a)   Both (I) and (II) are TRUE    (b)   Both (I) and (II) are FALSE (c)   Only (I) is true but (II) depends upon the instance size. (d)   (I) is TRUE but (II) is FALSE            (e)   (I) is FALSE and (II) is TRUE.
265.	Which of the following are essential statement types for describing algorithms? (a)  Sequence                                        (b)  Selection           (c)  Repetition (d)  All the above                                   (e)  A and B only.
266.	When we say an algorithm has a time complexity of O (n), what does it mean? (a)   The algorithm has ‘n’ nested loops (b)   The computation time taken by the algorithm is proportional to n (c)   The algorithm is ‘n’ times slower than a standard algorithm (d)   There are ‘n’ number of statements in the algorithm (e)   The computation time taken by the algorithm is less than ‘n’ seconds.
267.	Can we read a data item at any location of a list within a constant time (i.e. O(1))? (a)   Yes (b)   Yes, only if the list is implemented by pointers (i.e. linked-list) (c)   Yes, only if the list is implemented by an array (d)   No, we need O(n) computation steps no matter what kind of implementation is used (e)   No, as constant time is not possible for algorithms.
268.	Sequential search has a time complexity of O(n), and binary search has a time complexity of O(log(n)). What difference will it make when the size n is 1000? (a)   You would not notice much difference because computers run very fast anyway (b)   As n is 1000, binary search is twice as fast as sequential search (c)   As n is 1000, binary search is 10 times as fast as sequential search (d)   As n is 1000, binary search is 10 times as slow as sequential search (e)   As n is 1000, binary search is 100 times as fast as sequential search.
269.	Read the following statements carefully, and choose the correct answer. I.     The Ω notation is Anti Symmetric. II.     The big Oh notation is Semi Equivalence. (a)  (I) is FALSE but (II) is TRUE              (b)  Both (I), (II) are TRUE (c)  (I) is TRUE but (II) is FALSE              (d)  Both (I), (II) are FALSE (e)  (II) is TRUE and (I) cannot be defined.
270.	Find the odd one out. (a)  Bin-Packing Problem                        (b)  TVSP Problem                    (c)  Knap Sack Problem (d)  OBST Problem                                (e)  Sum of Sub Sets Problem.

Answers:

261.	Answer : (b) Reason:  As the given expression is a quadratic equation of degree 2, then by ignoring the constants and lower order terms, the highest term is n2, and hence it is Ω(n2).
262.	Answer : (e) Reason:  Because it is a single term of degree one. And all the remaining options are wrong.
263.	Answer : (a) Reason:  Again this is a polynomial of degree 2 i.e. n2 – 6n + 8. And hence n2 according to above reason of Question (21).
264.	Answer : (d) Reason:  As the first statement is true according to the definition of linear algorithms, the second is false as 30 operations are not needed.
265.	Answer : (d) Reason:  Because all are essential for the algorithm to state the solution of a given problem.
266.	Answer : (b) Reason:  As all the other options are meaning less and are wrong.
267.	Answer : (c) Reason:  For an array implementation, we can find the given location straightway with the index value and hence it takes constant time. But for a linked list, we have to follow the pointers one by one. The cost of this is proportional to the size of the list.
268.	Answer : (e) Reason:  log(1024) = 10,  1000/log(1000) is roughly equal to 1000/10 = 100
269.	Answer : (b) Reason:  According to the definitions of Omega, Big Oh notations.
270.	Answer : (a) Reason:  As Bin-Packing problem belongs to NP ( Non Deterministic Polynomial) hard problems and the remaining all are Deterministic polynomial time algorithms.

<< Prev 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  Next >>