Computer Science and Information Technology - Design Analysis and Algorithm
Exam Duration: 45 Mins Total Questions : 30
Which of the following algorithm design techniques
- (a)
Dynamic programing
- (b)
Back Tracking
- (c)
Divide and conquer
- (d)
Greedy method
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
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
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
A sorting technique that quarantees, that records with the same primary key occur in the same order in the sorted list as in the original unsorted list is said to be
- (a)
stable
- (b)
consistent
- (c)
external
- (d)
linear
The exact cover problem is the following given finite S1 ,....Sk of a set, with Si=A, is there subset J of {1,2....k} so that for any two distinct element K i and J of J1 S1\(\wedge \)SJ= \(\theta \)and \(U_{ i\varepsilon J }\quad S_{ i }=A?\)
- (a)
NP-complete by constructing reduction from the k-colorability problem
- (b)
Exact cover problem
- (c)
Sum of sub-set problem
- (d)
None of the above
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
Running time of Bellman Ford algorithm is
- (a)
O(V2)
- (b)
o(V2)
- (c)
O(VE)
- (d)
o(V+E log2V)
A digital search key is implemented as a tree with x nodes each of which can contains m pointers, corresponding to the m possible symbols in each positions of key. The number of nodes that must be accessed to find a particular tree is
- (a)
m
- (b)
x
- (c)
nm
- (d)
mn
Which decision procedure has atleast doubly exponential time complexity?
- (a)
Linear programming
- (b)
Travelling salesman problem
- (c)
Presbuyer arithmetic
- (d)
Hamiltonian circuit problem
Consider the following two functions
\({ g }_{ 1 }(n)=\{ n^{ 3 }\quad for\quad 0\le n<10000\\ \quad \quad \quad \quad \quad n^{ 2 }\quad for\quad n\ge 10000\)
\(g_{ 2 }(n)=\{ n\quad for\quad 0\le n<100\\ \quad \quad \quad \quad \quad \quad \quad n^{ 3 }\quad for\quad n>100\quad \)
Which of the following is true?
- (a)
g1(n) is g2(n)
- (b)
g1(n) is O(n3)
- (c)
g2(n) is O(g1(n))
- (d)
g2(n) is O(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)
A undirected graph G has n nodes, its adjacency matrix is given by an n x n square matrix whose
1.diagonal elements are 's and
2. Non-diagonal elements are 1's
Which one of the following is true?
- (a)
Graph G has no Maximum Spanning Tree (MST)
- (b)
Graph G has unique MST of cost n-1
- (c)
Graph G has multiple distinct MST's each of cost n-1
- (d)
Graph G has multiple spanning trees of different cases
Consider a weighted complete graph G on the vertex set {V1, V2 ,...Vn} such that the weight of the edge \(({ V }_{ i },{ V }_{ j })\quad is\quad 2\left| i-J \right| \)the weight of a minimum spanning of G is
- (a)
n-1
- (b)
2n-1
- (c)
(n/2)
- (d)
n2
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 })\)
Which one of the following in place sorting algorithms needs the minimum number of swaps
- (a)
Quick sort
- (b)
Insertion sort
- (c)
Selection sort
- (d)
Heap sort
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)\)
The recurrence relation
T(1)=2
T(n)=3T(n/4)+n has the solution T(n) equal to
- (a)
O(n)
- (b)
O(log n)
- (c)
O(n3/4)
- (d)
None of these
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)
An algorithm to test whether a graph is singly connected i.e., there is atmost one path between all pairs of vertices, can be formulated using
- (a)
DFS
- (b)
BFS
- (c)
Dijkstra's algorithm
- (d)
None of these
The recurrence relation T(n)=mT(n/2)+an2 is satisfied by
- (a)
T(n)=o(nm)
- (b)
T(n)=O(log m)
- (c)
T(n)=o(nlogm)
- (d)
T(n)=o(m log n)
We have a binary heap on n element and wish to insert n more elements (not necessarily one after another) into heap. The total time required for this is
- (a)
\(\theta (log_{ n })\)
- (b)
\(\theta (n)\)
- (c)
\(\theta (n\quad log\quad n)\)
- (d)
\(\theta (n^{ 2 })\)
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
- (a)
Dijkstra's algorithm starting from S
- (b)
Warshall's algorithm
- (c)
performing a DFS starting from S
- (d)
performing a BFS starting from S
The space complexity of the above function is
- (a)
O(1)
- (b)
O(n)
- (c)
O(n!)
- (d)
O(nn )
If all permutation are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1...n2
- (a)
n(n-1)/2
- (b)
n(n-1)/4
- (c)
n(n+1)/4
- (d)
2n[log2 n]
What would be the worst case time complexity of the insertion sort algorithm, if the inputs are restricted to permutations of 1...n with at most n inversions?
- (a)
\(\theta (n^{ 2 })\)
- (b)
\(\theta (n\quad log\quad n)\)
- (c)
\(\theta (n^{ 1.5 })\)
- (d)
\(\theta (n)\)
What is the average length of the correct answer to Question 15?
- (a)
3
- (b)
2.1875
- (c)
2.25
- (d)
1.781
What is the expected number of probes in a successful search?
- (a)
2
- (b)
3
- (c)
4
- (d)
4.5
1654060945.png)
1654060942.png)
1653987551.png)
1653987086.png)
1582095229.jpg)
