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 singlesource shortest path problem has a good well known solution of the type_____.

bruteforce

greedy

DFS

divide and conquer

Answer: B
10.The singlesource 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 Booleanvalued 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(ElogE)
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