Q1 The Floyd-Warshall algorithm for
all-pair shortest paths computation
is based on
[A] Greedy paradigm
[B] Divide-and-Conquer paradigm
[C] Dynamic Programming paradigm
[D] Heuristics
Solution
Floyd Warshall algorithm is based on dynamic programming paradigm.
It finds the all pair shortest paths:
Consider for every pair (i, j), there are two possible cases:
1) k is not an intermediate vertex in shortest path from i to j. We keep the value of dist[i][j] as it is.
2) k is an intermediate vertex in shortest path from i to j. We update the value of dist[i][j] as dist[i][j] + dist[.k][j]
While using dynamic programming paradigm, we computer all pair shortest path time complexity is O(V3).
Q2 An array of 25 distinct elements is
to be sorted using quicksort.
Assume that the pivot element is
chosen uniformly at random. The
probability that the pivot element
gets placed in the worst possible
location in the first round of
partitioning (rounded off to 2
decimal places) is
[A] 0·5
[B] 0·7
[C] 0·9
[D] 0·08
Solution
Probability of choosing each element is 1/25
Worst case for quick sort arise if 1 is choosen or 25 is choosen as pivot element
P(x=1)=1/25=0.04
P(x=25)=1/25=0.04
P(x=1 or x=25)
=0.04+0.04=0.08
Q3 What is the pumping length of
string of length x?
[A] x+1
[B] x
[C] x–1
[D] x2
Solution
Explanation: There exists a property of all strings in the language that are of length p, where p is the constant-called the pumping length .For a finite language L, p is equal to the maximum string length in L plus 1.
Q4 Access time of the symbol table
will be logarithmic, if it is
implemented by
[A] Linear list
[B] Search Tree
[C] Hash Table
[D] Self-organization list
Solution
Linear list on average
= O (n/2)
Linear complexity search tree on average=O(logn)
Logarithm hash table perfect hashing leads to O(1) constant complexity.
0 Comments