Data Structure and Algorithm Analysis
Questions 261 to 270
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).
|
|
What term is used to describe an O(n) algorithm?
(a) Constant (b) Non Polynomial Deterministic
(c) Logarithmic (d) Quadratic (e) Linear.
|
|
Express the formula (n - 2)*(n - 4) using θ notation:
(a) θ (n2) (b) θ (8) (c) θ (log n) (d) θ (n) (e) θ (1).
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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.
|
|
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:
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).
|
|
Answer : (e)
Reason: Because it
is a single term of degree one. And all the remaining options are wrong.
|
|
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).
|
|
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.
|
|
Answer : (d)
Reason: Because all
are essential for the algorithm to state the solution of a given problem.
|
|
Answer : (b)
Reason: As all the
other options are meaning less and are wrong.
|
|
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.
|
|
Answer : (e)
Reason: log(1024) =
10, 1000/log(1000) is roughly equal to 1000/10 = 100
|
|
Answer : (b)
Reason: According to
the definitions of Omega, Big Oh notations.
|
|
Answer : (a)
Reason: As
Bin-Packing problem belongs to NP ( Non Deterministic Polynomial) hard
problems and the remaining all are Deterministic polynomial time algorithms.
|
Consider the following piece of code extracted from a function for deleting a node in an unordered
ReplyDeleteone-way linked list. The execution of this code results in ….