Design and Analysis of Algorithms Mid - I, February - 2012

1.The complexity of adding two matrices of order m*n is __________.
  • mn
  • m+n
  • max(m,n)
  • min(m,n)
Answer: A
2.The running time of the following sorting algorithm depends on whether the partitioning balanced or
unbalanced.
  • Insertion sort
  • Quick sort
  • Selection sort
  • Merge sort
Answer: B
3.The disjoint set is an abstract data type that supports the operations,
  • Union
  • Find
  • both A and B
  • none
Answer: C
4.A graph G is said to be ____________ if and only if it contains no articulation points.
  • Connected
  • Biconnected
  • either A or B
  • both A and B
Answer: B
5.For merging two sorted lists of sizes m and n into a sorted list of size m n, requires ________ number of
comparisons.
  • O(m)
  • O(n)
  • O(m+n)
  • O(log m + log n)
Answer: C
6.Nodes which satisfy __________ , w being the children of u are identified as an articulation points.
  • L[w]≤dfn[u]
  • L[w]≥dfn[u]
  • dfn[u]≥L[w]
  • dfn[u]≤L[w]
Answer: A
7.The essence of greedy algorithm is the __________ policy.
  • maximization
  • minimization
  • selection
  • either A or B
Answer: D
8.In Krushkal’s algorithm, the edges are selected and added to the spanning tree in _________
order of their weights.
  • increasing
  • decreasing
  • increasing or decreasing
  • increasing and decreasing
Answer: A
9.The single-source shortest path problem has a good well known solution of the type_____.
  • brute-force
  • greedy
  • DFS
  • divide and conquer
Answer: B
10.The single-source shortest path problem is to find shortest paths from a source vertex to
______________ in the graph.
  • nearest vertex
  • adjacent vertex
  • same vertex
  • all other vertices
Answer: D
11.The _______________________ of an algorithm is the amount of computer time it needs to run to
completion.
Answer: Time complexity
12.In the weighting rule of UNION(I,j), the height of tree is not greater than _____________.
Answer: The number in the tree with root j
13.The time complexity for Strassen’s matrix multiplication is ____________.
Answer: O(n^2.81)
14.A feasible solution that either maximizes or minimizes a given objective function is called an
_____________________.
Answer: Optinal Solution
15._________________ is a Boolean-valued function that determines whether the input size is small enough
that the answer can be computed without splitting.
Answer: Small(p)
16.Krushkal’s algorithm takes a total time of _____________________.
Answer: O(|E|log|E|)
17.Given a function to compute on ‘n’ inputs, the ______________________ strategy suggests splitting the
inputs into ‘k’ distinct subsets.
Answer: Divide and conquer
18.Time complexity of merge sort in worst time is _______________.
Answer: O(n^2)
19.A _________________ is a function that is defined in terms of itself.
Answer: Recursion
20._____________ is a function that determines the solution to the problem p using the solutions to the sub
problems p1, p2,…., pk.
Answer: Combine