Algorithms Interview Question Part 6

46. Consider the following four terms given in Part A and some definitions given in Part B.
Part A Part B
(i) Big O (p) The notation used to capture the most dominant term in a function
(ii) Big Omega (q) A guarantee over all inputs of some size
(iii) Average case bound (r) The bound in which running time is measured as an average
over all the possible inputs of size N
(iv) Worst case bound (s) An algorithm that causes the running time to grow as O(N)
(v) Linear time algorithm (t) The notation similar to greater than or equal to when
considering growth rates
Choose the best definition from Part B for the above five hash operations respectively in Part A.
(a) (i)􀃆(p) (ii)􀃆(r) (iii)􀃆(t) (iv)􀃆(q) (v)􀃆(s) (b) (i)􀃆(s) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(p)
(c) (i)􀃆(p) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(s) (d) (i)􀃆(p) (ii)􀃆(s) (iii)􀃆(r) (iv)􀃆(q) (v)􀃆(t)
(e) (i)􀃆(p) (ii)􀃆(t) (iii)􀃆(r) (iv)􀃆(s) (v)􀃆(q)

Ans. c

47. There are the three main measures of efficiency that can be applied to most algorithms: best, worst and average cases.

Part A Part B
(i) Best case P This case is when the target is either a
last item in the list or is not in the list at all
(ii) Worst case Q This case occurs when the target for which
you are searching is the first item in the list
(iii) Average case R This case is found by considering all possible
outcomes of a search and averaging the number
of companions over all these cases.
Choose the best definition from part B for the above three cases.
a. (i)  R (ii)  P (iii)  Q
b. (i)  R (ii)  Q (iii)  P
c. (i)  Q (ii)  P (iii)  R
d. (i)  Q (ii)  R (iii)  P
Ans. d

48. Consider the following characteristics connected with a program.
(i) The input to the program
(ii) The time complexity of the algorithm underlying the program
(iii) The quality of the Compiler
(iv) The nature and speed of the machine
On which of the above does the running time of a program depend?
a. (i) and (ii) only
b. (i),(ii) and (iii) only
c. (i),(iii) and (iv) only
d. (i),(ii) and (iv) only
Ans. d

49. We may find several algorithms for solving a problem; for each algorithm, the measure to calculate the proportionate time taken to solve that particular problem is called ____________.

a. Time Complexity
b. Space Complexity
c. Algorithm complexity
d. Design Complexity
Ans: a
50. If an algorithm takes the largest possible execution time for a certain set of input values, then it is called ________ of the algorithm.
a. Best case
b. Worst Case
c. Average case
d. none
Ans:b
51. Which of the following is not a feature of algorithm
a. Step wise implementation of large problems
b. Calculation of time and space complexity
c. Analyzing the efficiency of the code
d. Complex representation of problems
Ans:d

52. The correct order of sequential search algorithm is
(i) marker ++.
(ii) else, throw an exception.
(iii) if target == key at location marker, then return.
(iv) While target = = key at location marker and not at the end of the list.
(v) Read in target, initialize marker to first array index(0).
a.(v), (iv), (i), (ii), and (iii).
b.(iv), (i), (iii), (iv) and (ii).
d.(v), (iv), (iii), (i) and (ii). c.(v), (iv), (i), (iii) and (ii)

Ans:c

53. Running time of an algorithm does not depend on which of the following statement(s)
(i) Time taken by each instruction in the algorithm.
(ii) Number of times each instruction is executed.
(iii) Processor speed and its machine language instruction set.
(iv) Size of the input
a.(iii) only b.(iii) and (iv) c. (i) and (iii) only d. (iv) only e.none of these
Ans:e
54. Consider the following program code.

Public static int sum (int n)

{ int Partialsum
Partialsum=0;
for (int i=1; i<=n ;i++)
Partialsum += i *i *i ;

return Partialsum;
}

The time complexity of the above algorithm is?
a.log n b.nlogn c.n d.constant
Ans:c


55.The minimal spanning tree of a graph gives the shortest distance between any two nodes. (True or False)
Ans. False
Minimal spanning tree assures that the total weight of the tree is kept at its minimum.But it doesn’t mean that the distance between any two nodes involved in the minimum-spanning tree is minimum.
56.What is the simplest file structure?
a. Sequential
b. Indexed
c. Random
Ans. Sequential
57. Computational procedure is an algorithm that
d. does not terminate
e. terminates
f. computes
g. analyzes
Ans. a
58.An algorithm consists of the following areas
i) to devise the algorithm
ii) to validate the algorithm
iii) to express the algorithm
iv) to analyze the algorithm
v) to test the programs for the algorithm
The correct options are
a. (i),(ii),(iii) only
b. (ii),(iii),(iv) and (v) only
c. (i),(ii),(iii),(iv) only
d. All of the above
Ans. d
59.An algorithm is said to be recursive if the same algorithm is invoked in the body of the algorithm. (True or False)
Ans. True
.
60.______________ is an algorithm design method that can be used when the solution to a problem can be viewed as the result of a sequence of decisions.
Ans. Dynamic programming
61.The two parameters that can be taken as cost of an algorithm include
running time and amount of memory used .

62. Given a list implemented with a linked list, the operation remove(p) runs in:
a) O(1)
b) O(log n)
c) O(n)
d). O(nlog n)
Ans:c