Design Analysis and Algorithm
Exam Duration: 45 Mins Total Questions : 30
Consider a weighted undirected graph with positive edge weight and let uv be ab edge in the graph. It is known that the shortest path from the source vertex S to u have weight 53 and the shortest path from S to v has weight 65. What will be the condition for calculating shortest path in weight terms?
- (a)
weight (u,v) \(\le \)12
- (b)
weight (u,v)>12
- (c)
weight (u,v)>24
- (d)
weight (u,v)>12
Which one of the following statement is false?
- (a)
Optimal binary search tree construction can be performed efficiently using dynamic programming
- (b)
BFS cannot be used to find connected components of graph
- (c)
Given the prefix and postfix walks of a binary tree, the binary tree cannot be uniquely reconstructed the binary tree cannot be uniquely reconstructed
- (d)
DFS can be used to find the converted components of a graph
15,11,34,10,98,51,37,14,16,47Given the hash function h(k)=k mod 3, what is the number of collisions to store the following sequence of keys.
- (a)
10
- (b)
2
- (c)
4
- (d)
8
An hash table with chaining as a collision resolution technique degenerates to a
- (a)
queue
- (b)
linked list
- (c)
tree
- (d)
array
Which of the following probing methods suffers from the problem of secondary clustering?
- (a)
Linear probing
- (b)
Quadratic probing
- (c)
Double hasing
- (d)
Both (b) and (c)
The tightest lower bound on the number of comparisons, in the worst case, for comparison based sorting is of the order of
- (a)
n
- (b)
n2
- (c)
n log n
- (d)
n log2 n
The usual\(\theta \) (n2) implementation of insertion sort to sort an array uses linear search to identify the position where an element is to inserted into the already sorted part of the array. If instead into the already sorted part of the array. If instead, we use binary search to identify the position, the worst case running time will
- (a)
remain\(\theta \) (n2)
- (b)
become \(\theta \) (n logn)2)
- (c)
become\(\theta \) (n log n)
- (d)
become \(\theta \)(n)
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
- (a)
O(n)
- (b)
O(n log n)
- (c)
O(n3/2)
- (d)
O(n3)
Consider the polynomial:
\(P(X)={ a }_{ 0 }+{ a }_{ 1 }X+{ a }_{ 2 }X^{ 2 }+{ a }_{ 3 }x^{ 3 }\)
where \({ a }_{ i }\neq o,\forall i\) The minimum number of multiplication needed to evalute P on an input X
- (a)
3
- (b)
4
- (c)
6
- (d)
9
A scheme for storing binary trees in an array X is as following. Indexing of X starts 1 instead of 0. The roots is stored at X[1}. For a node stored at X[i}, the left child, if any, is stored in X[2i} and the right child, if any , X[2i+1]. To be able to store any binary tree on n vertices, the minimum size of X should be
- (a)
log2 n
- (b)
n
- (c)
2n+1
- (d)
2n
Which of the following statements is/are correct regarding Bellman-ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exists.
Q: Finds wheather any negative weighted cycle is reachable from the source
- (a)
P only
- (b)
Q only
- (c)
Both P and Q
- (d)
Neither P nor Q
Merge sort uses
- (a)
divide and conquer strategy
- (b)
Back Tracking approach
- (c)
Heuristic Search
- (d)
Greedy approach
The goal of hashing it to produce a search that takes
- (a)
O(1) time
- (b)
O(n2) time
- (c)
O(log n) time
- (d)
O(n log n) time
Which of the following also called 'diminishing intermedia sort'?
- (a)
Quick sort
- (b)
Heap sort
- (c)
Merge sort
- (d)
Shell sort
Binary search requires average number of comparisions
- (a)
log2n
- (b)
log2(log2 n)
- (c)
n2
- (d)
log2(n log2n)
The most approprite matching for the following pairs is
List I | List II | ||
X | Depth first search | 1. | Heap |
Y. | Breadth first search | 2. | Queue |
Z. | Sorting | 3. | Stack |
- (a)
X-1, Y-2,Z-3
- (b)
X-3, Y-1, Z-2
- (c)
X-3, Y-2, Z-1
- (d)
X-2, Y-3, Z-1
A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key . If the value 43,165, 62, 123, 142 are inserted in the table in what location would the key value 142 be inserted?
- (a)
2
- (b)
3
- (c)
4
- (d)
6
If the array is sorted, the complexity to search an element is
- (a)
o(n)
- (b)
O(n2)
- (c)
o(n log2 n)
- (d)
O(log2 n)
Consider the label sequence obtained by the following pair of traversals on a labelled binary tree which of these pairs identify a tree uniquely?
1. Pre-order and post-order
2. In-order and post-order
3. Pre-order and in-order
4. Level order and post-order
- (a)
1 only
- (b)
2 and 3
- (c)
3 only
- (d)
4 only
If \(L\varepsilon P\) then
- (a)
\(L'\varepsilon NP\quad \)
- (b)
\(L'\epsilon P\)
- (c)
Both (a) and (b)
- (d)
None of these
The recurrence equation
\(T(1)=1\\ T(n)=2T(n-1)+n,n\ge 2\)
evaluates to
- (a)
\({ 2 }^{ n+1 }-n-2\)
- (b)
\(2^{ n }-n\)
- (c)
\({ 2 }^{ n+1 }-2n-2\)
- (d)
\(2^{ n }+n\)
If there is NP=complete language L whose complement is in NP, then complement of any language in NP is in
- (a)
P
- (b)
NP
- (c)
Both (a) and (b)
- (d)
None of these
Let f is a total function from N to M and that f=o(P) for some polynomial function P. When C and D are contants, then for every n.
- (a)
\(f(n)\le CP(n)+D\)
- (b)
\(f(n)\ge CP(n)+D\)
- (c)
\(f(n)\ge DP(n)+C\)
- (d)
\(f(n)\le DP(n)+c\)
Suppose T(n) = 2T(n/2) + n, T(0) = T(1) = 1
Which one of the following is false?
- (a)
\(T(n)=O({ n }^{ 2 })\)
- (b)
\(T(n)=\theta (nlogn)\)
- (c)
\(T(n)=\Omega ({ n }^{ 2 })\)
- (d)
\(T(n)=O(nlogn)\)
You are given the post-order traversal, P of a binary search tree on the n elements 1,2...n. You have to determine the unique binary search tree that has P as its post-order traversal. What is time complexity of the most efficient algorithm for doing this.
- (a)
\(\theta (log\quad n)\)
- (b)
\(\theta (n)\)
- (c)
\(\theta (n\quad log\quad n)\)
- (d)
None of the above
The number of simple paths from node A to node F are
- (a)
5
- (b)
6
- (c)
7
- (d)
4
The correction needed in the program to make it work property is
- (a)
change line 6 to:
if (Y[K]<X)i=K+1;
else J=K-1; - (b)
change link 6 to
if(Y[K] <X)i=K-1
else J=K+1; - (c)
change line 6 to:
if (Y[K]<X)i =K;
else j=K; - (d)
change line 7 to: while
((Y[K]==X) && (i<J);
Solve T(n)=T(n-1)+log2n
- (a)
\(\theta (n^{ 2 }log\quad n)\)
- (b)
\(O(n^{ 2 }log\quad n)\)
- (c)
\(\Omega (n\quad log\quad n)\)
- (d)
None of these
A vertex is dequeued when its adjacent vertices are visited and then it is colored black
- (a)
to test for the presence of a cycle in a graph
- (b)
to topologically sort a graph
- (c)
to obtain the transpose of a graph
- (d)
to obtain strongly connected components of a graph
Which of the following serves as an endpoint in the above algorithm A?
- (a)
Number of black and gray vertices is equal
- (b)
There exists an edge from a gray vertex to a black vertex
- (c)
All vertices are black except for one
- (d)
Number of gray vertices exceed number of black vertices.