Algorithms Interview Question Part 5

27. An algorithm which is given the entire sequence of inputs in advance. (practice test question)
a.On-line algorithm
b.Off line algorithm
c.Adversary algorithm
d.Deterministic algorithm
Ans:b
An algorithm that must process each input in turn, without detailed knowledge of future inputs is called on-line algorithm.
28. To combine multiple sorted data streams into a single sorted stream using external storage.
a.External merge
b.Internal merge
c.both
d.none
Ans:a
29 .Let m,n be positive integers.Define Q(m,n) as Q(m,n)=0, if mQ(m,3) is (a div b, gives the quotient when a is divided by b)
a.a constant b.p*(m mod 3) c.p*(m div 3) d. 3*p
Ans:c
Let m>n .Let m/n yield a quotient x and remainder y. So, m=n*x+y and y30. _________ is the number of times a key operation will execute.
a. Frequency count
b. Running time
c. Space complexity
d. Time complexity
Ans. a
31. When an algorithm contains a recursive call to itself,its running time can often be described by a ___________
Ans. recurrence equation or recurrence
32. A function f(n) is strictly increasing if _________ implies ________ where m and n are the two parameters.
Ans. m 33. A function f(n) is strictly decreasing if _________ implies ________ where m and n are the two parameters.
Ans. m>n , f(m)>f(n)
34. The substitution method for solving recurrences entails the following steps:
a. Guess the form of the solution
b. Use mathematical induction to find the constants and show that the solution works. True or False
Ans. True
35. The various methods for solving recurrences are
a. substitution method
b. recursion-tree method
c. master method
d. all of the above
Ans. d
36. The recursion-tree method converts the recurrence into a tree whose nodes represent the costs incurred at various levels of the recursion. True or False
Ans. True
37. The master theorem does not apply to the recurrence of the form
a. T(n) = 2T(n/2) + n lg n
b. T(n) = aT(n/b) + f(n)
c. T(n) = aT(n) + f(n)
d. None of the above
Ans. a
Here a=2,b=2,f(n)=nlgn and n^log a = n but f(n)=n lg n is not polynomially larger than n^log a = n.the ratio f(n)/n^log a = (n lg n)/n =lg n is asymptotically less than n^є for any positive constant є.
38.Which of the following is a way of classifying algorithms based on implementation.
a.Recursion vs iteration
b.Serial vs parallel
c.Random vs deterministic
d.All the above
Ans:d

39.Searching can be used with
i.lists ii.graphs iii.trees
a.i ,ii b.i,iii c.i,ii,iii d.ii,iii
Ans:c
40. _______ consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.
Ans: instance of a problem
41. Which of the following factors decides which algorithm is best for a given application?
a.Number of items to be sorted
b.extent to which items are already sorted
c.possible restrictions on the item values
d.All the above
Ans:d
42. Probabilistic analysis is the use of ___________ in the analysis of problems.
Ans. probability
43. Probabilistic analysis
a. is used to analyze the running time of an algorithm
b. requires the knowledge of the distribution of inputs
c. all the above
d. none of the above
Ans. c
44. In randomized algorithm,the behavior of the algorithm is determined only by its input but not by values produced by a randon-number generator. True or False
Ans. False
In randomized algorithm,the behavior of the algorithm is determined not only by its input but also by values produced by a randon-number generator.
45. The running time of an algorithm on a particular input is the number of primitive operations or steps executed. True or False
Ans. True