Design and Analysis of Algorithms Mid - I, September - 2014

1.________ algorithm is not quite as numerically stable as the naïve method.
  • Strassen’s
  • Binary Search
  • Knapsack
  • Kruskal’s
Answer: A
2.An edge of a spanning tree is called a
  • Chord
  • Branch
  • Vertex
  • Edge weight
Answer: B
3.Single source shortest path takes _____ time.
  • O(n)
  • O(n2)
  • O(2n)
  • O(logn)
Answer: B
4.The greedy method and dynamic programming algorithm are the methods for obtaining ________solution.
  • Correct
  • Incorrect
  • Feasible
  • Optimum
Answer: D
5.Divide and Conquer uses ___ approach.
  • Top-down
  • Bottom-up
  • Both (A) and (B)
  • Recursion
Answer: A
6.If the solution of a problem is uncertain then it is called as_______ algorithm.
  • Probabilistic
  • Infinite
  • Heuristic
  • Approximate
Answer: A
7.We use _____to denote a lower bound that is not asymptotically tight.
  • O-notation
  • o-notation
  • ω-notation
  • Ω-notation
Answer: C
8.f(n)=Θ(g(n)) if and only if g(n)=Θ(f(n)) denotes_______ property.
  • Transitivity
  • Symmetry
  • Transpose Symmetry
  • Reflexivity
Answer: B
9.In ______ Method sub problems are solved independently.
  • Algorithm
  • Divide and Conquer
  • Greedy Method
  • Dynamic Programming
Answer: B
10.The Time complexity of merge sort is
  • O(n2)
  • O(2n)
  • O(n log n)
  • O( 2 log n)
Answer: C
11.The set that contains nothing, known as the____________________.
Answer: empty set
12.A __________of a set of values is the value that separates the highest half of the values from the lowest half.
Answer: median
13.Divide and conquer-style operation known as____________.
Answer: partitioning
14.______________can be thought of as an optimization technique for particular classes of backtracking algorithms where sub problems are repeatedly solved.
Answer: Dynamic programming
15.Kruskal’s algorithm Running Time is _____________.
Answer: O(E log V)
16.The _________is the maximum amount of stack space used at any time during acomputation.
Answer: stack depth
17.The nested repetition of identical algorithm is __________.
Answer: recursion
18.A ______is a complete binary tree with the property that the value at each node is atleast as large as the value at its children.
Answer: heap
19.The time complexity for the formal matrix Multiplication is __________.
Answer: O(n3)
20.A _________that either maximize can minimize a given objectives function is called an optimal solution.
Answer: feasible solution