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(n^{2})

O(2^{n})

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.

Topdown

Bottomup

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.

Onotation

onotation

ω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(n^{2})

O(2^{n})

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 conquerstyle 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(n^{3})
20.A _________that either maximize can minimize a given objectives function is called an optimal solution.
Answer: feasible solution