Computer Science and Information Technology - Design Analysis and Algorithm
Exam Duration: 45 Mins Total Questions : 30
Merge sort uses
- (a)
divide and conquer strategy
- (b)
back tracking approach
- (c)
heuristic search
- (d)
approach
The minimum number of colours needed to colour a graph having n(>3) vertices and 2 edges is
- (a)
3
- (b)
4
- (c)
2
- (d)
1
The average total path length of a randomly built binary search tree with n nodes is
- (a)
d(log2 n)
- (b)
d(n log2 n)
- (c)
d(n2)
- (d)
d(n2 log2 n)
Let G be a directed graph whose vertex set is the set of number from 1 to 100. There is an edge from a vertex i to a vertex j, if either j=i+1 or j=3i. The maximum number of edges in a path in G from vertex 1 to vertex v are
- (a)
25
- (b)
26
- (c)
10
- (d)
23
Which of the following statement is/are correct regarding Bellman ford shortest path algorithm?
P; Always finds a negative weighted cycle, if one exists.
Q: Find wheather any negative weighted cycle is reachable from the source.
R: Find whether 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
What is the preferred form of representation of dense graphs?
- (a)
Adjacency list
- (b)
Adjacency matrix
- (c)
Incidence matrix
- (d)
One-dimensional array
Which of the following problems is solvable?
- (a)
Writing a universal turing machine
- (b)
Determining of an arbitary turing machine in an universal turing machine
- (c)
Determining of a universal turing machine can be written for fewer than k instructions for same k
- (d)
Determining of a universal turing machine and some input will half
A search technique where we keep expanding nodes with least accumulated cost so far is called
- (a)
hill-climbing
- (b)
branch and bound
- (c)
best first
- (d)
divided and conquer
The height of a binary tree is the maximum number of edges in any root to leaf path. The maximum number of nodes in a binary tree of height h is
- (a)
2h
- (b)
2h-1-1
- (c)
2h+1-1
- (d)
2h+1
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
An element in array X is called a leader if it is greater than elements to the right of it in X. The best algorithm to find all leaders in an array
- (a)
solves it in linear time using a left to right pass of the array
- (b)
solves in linear time using a right to left pass
- (c)
solves it is using divide and conquer in time \(\theta (nlogn)\)
- (d)
solves it in time \(\theta (n^{ 2 })\)
In a binary max-heap containing n numbers, the smallest element can be found in time
- (a)
\(\theta (n)\)
- (b)
\(\theta (log\quad n)\)
- (c)
\(\theta (log\quad log\quad n)\)
- (d)
\(\theta (1)\)
Which of the following sorting algorithms has the lowest worst case complexity?
- (a)
Merge sort
- (b)
Bubble sort
- (c)
Quick sort
- (d)
Selection sort
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertics and m edges has time complexity
- (a)
\(\theta (n)\)
- (b)
\(\theta (m)\)
- (c)
\(\theta (m+n)\)
- (d)
\(\theta (mn)\)
Let \({ \pi }_{ A }\) be a problem that belongs to the class NP. Then which one of the following is true?
- (a)
There is no polynomial time algorithm for \({ \pi }_{ A }\)
- (b)
If \({ \pi }_{ A }\) can be solved deterministically in polynomial time, then P=NP
- (c)
If \({ \pi }_{ A }\) is NP-hard, then it is NP-complete
- (d)
\({ \pi }_{ A }\) may be undecidable
What is the number of swaps required to sort n element using selection sort, in the worst case?
- (a)
\(\theta (n)\)
- (b)
\(\theta (nlogn)\)
- (c)
\(\theta (n^{ 2 })\)
- (d)
\(\theta n^{ 2 }(logn)\)
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
What is the order of complexity in bubble sort in worst case?
- (a)
o(n)
- (b)
o(n2)
- (c)
o(n log n)
- (d)
o 9log n)
An algorithm is made up of 2 modules m1 and m2 ,. if order of M1 is f(n) and M2 is g(n) then the order of the algorithm is
- (a)
max(f(n) , g(n))
- (b)
min(f(n), g(n))
- (c)
f(n)+g(n)
- (d)
f(n)x g(n)
The cube root of a natural number n is defined as the largest natural numbers m such that \({ m }^{ 3 }\le n.\) The complexity of computing the cube root of n (n is represented in binary notation) is
- (a)
\(O(n)\quad but\quad not\quad O({ n }^{ 0.5 })\)
- (b)
\(O({ n }^{ 0.5 })\quad but\quad O(logn)^{ k }\quad for\quad any\quad constant\quad K>0\)
- (c)
\(O((log\quad n)^{ k })\quad for\quad same\quad constant\quad k>0,but\quad not\\ o(loglogn)m)\quad for\quad any\quad constant\quad m>0.\)
- (d)
\(O(loglogn)^{ k })\quad for\quad same\quad constant\quad k>0.5,but\quad not\\ O((loglogn)^{ 0.5 })\)
If \(L\epsilon P\) space, then
- (a)
\(L'\epsilon P\quad space\\ \)
- (b)
\(L'\epsilon P\)
- (c)
\(L'\epsilon NP\quad space\)
- (d)
None of these
The running time of an algorithm is given by
T(n)=T(n-1)+T(n-2)-T(n-3), if n>3
=n>3, otherwise
The order of this algorithm is
- (a)
n
- (b)
log n
- (c)
nn
- (d)
n2
Let G(V, E) an undirected graph with positive edge weight. Dijkstra's sign source shortest path algorithm can be implemented using the binary heap data structure with time complexity.
- (a)
\(O(\left| V \right| ^{ 2 })\)
- (b)
\(O(\left| E \right| +\left| V \right| log\left| V \right| )\)
- (c)
\(O(\left| V \right| log\left| V \right| )\)
- (d)
\(O(\left| E \right| +\left| V \right| log\left| V \right| )\)
In a complete k-ary every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is
- (a)
nk
- (b)
(n-1)k+1
- (c)
n(k-1)+1
- (d)
n(k-1)
Consider the quick sort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into sub lists each of which contains atleast one-fifh of the element. Let T(n) be the number of comparisons required to sort n element. Then
- (a)
\(T(n)\le 2t(n/5)+n\)
- (b)
\(T(n)\le T(n/5)+T(4n+5)+n\)
- (c)
\(T(n)\le 2T(4n/5)+n\)
- (d)
\(T(n)\le 2T(n/2)+n\)
In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using O(n) time algorithm. What is the worst case time complexity of the quick sort?
- (a)
\(\theta (n)\)
- (b)
\(\theta (n\quad log\quad n)\)
- (c)
\(\theta (n^{ 2 })\)
- (d)
\(\theta (n^{ 2 }log\quad n)\)
f1(8) and f2(8) return the values
- (a)
1661and 1640
- (b)
59 and 59
- (c)
1640 and 1640
- (d)
1640 and 1661
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);
If the array is in reverse sorted order then time complexities will be
- (a)
O(n)
- (b)
O(n3)
- (c)
O(n log2n)
- (d)
O(log2 n)