STUPIDSID
1 (a)
What is an algorithm? What do you mean by correct algorithm? What do you mean by
instance of a problem? List out the criteria that all algorithms must satisfy. On what
bases will you consider algorithm A is better than algorithm B?
6 M
1 (b)
What do you mean by Polynomial time complexity and Logarithmic time complexity?
Which one is higher? What does O(1) mean?
4 M
1 (c)
Arrange following functions n in increasing order:
2n,log2n,n3,nlog2n,2log2n,n2log2n,elog2n,3n,22n,1/n,n log2n.
2n,log2n,n3,nlog2n,2log2n,n2log2n,elog2n,3n,22n,1/n,n log2n.
4 M
2 (a)
Define Time Complexity and Space Complexity. Why we are generally concerned with
Time Complexities than Space Complexities? What is a major contributor for
inefficiency of a loop? What will be theta notation for :4n3+5n+6?
7 M
2 (b)
Explain why the statement, ?The running time of algorithm A is at least O (n2)? is
meaningless. Also explain what is the smallest value of n such that an algorithm whose
running time is 100n2 runs faster than an algorithm whose running time is 2n on the
same machine?
7 M
2 (c)
What is Time Complexity? What is significance of Time Complexity in Algorithm
Analysis? Provide methods and ways to measure the time complexity? What is
significance of Time Complexity in algorithm analysis? Explain Limit rules for 0,Ω,θ
notations. Express the function n3 /1000-100n2 -100n+3 in terms of Θ notation and prove
that.
7 M
2 (d)
Write down the algorithm to find minimum of N numbers and find its complexity. Also
derive the worst case complexity of searching a Key from a binary search tree
(balanced) having n nodes.
7 M
3 (a)
Write an algorithm to find the maximum and minimum element in an array A storing n
integers. What is the running time of this algorithm for computing the maximum
element in an array of integers?
6 M
3 (b)
What do you mean by 'eventually non decreasing function'? Give an example for the
Same.
4 M
3 (c)
What is optimal binary search tree problem? Explain in brief.
4 M
3 (d)
What is Space Complexity? How algorithms can be analyzed in terms of space
complexity? Will it depend on type of Instance (input) or will change?
4 M
3 (e)
Solve the following recurrence equations.
1. T (n) = 7T (n/3)+ n2
2. T (n) = 4T (n/2)+ log n
1. T (n) = 7T (n/3)+ n2
2. T (n) = 4T (n/2)+ log n
6 M
3 (f)
Differentiate decision problem and optimization problem. Is P= NP? List out the
problems which can solve in polynomial time. List out the problems which cannot solve
in polynomial time.
4 M
4 (a)
Is 3logn+loglogn is O (log10 n)? Is 3logn+loglogn is Ω (log10 n)?
4 M
4 (b)
Differentiate between Greedy, Dynamic Programming and Divide and Conquer method.
6 M
4 (c)
Write an algorithm for depth first search of a graph and explain with an example. Write
an algorithm for breadth first search of a graph and explain with an example.
4 M
4 (d)
Given two sequences of characters: P= & Q=. Obtain the longest
common subsequence.
7 M
4 (e)
Define String-matching problem. Compare all string matching algorithms.
7 M
5 (a)
There is a network given in the figure below as a highway map and the number recorded next to each arc as the maximum elevation encountered in traversing the arc. A traveller plans to drive from node 1 to 12 on this highway. The traveller dislikes high altitudes and so would like to find a path connecting node 1 to 12 that minimizes the maximum altitude. Find the best path for the traveller using a MST. (Graph do be drawn for Kruskal or Prim's algorithm for minimum spanning tree)
7 M
5 (b)
Check equalities(True/False):
5n2-6n ϵΘ(n2
n!ϵO(nn
2nn-2n+n log nϵΘ(n22n)
[sum_{i=0}^{n}i^{2}epsilon Theta(n^{3})]
n2ϵΘ(n3)
2nϵΘ(2n+1)
n!ϵΘ((n+1)!).
5n2-6n ϵΘ(n2
n!ϵO(nn
2nn-2n+n log nϵΘ(n22n)
[sum_{i=0}^{n}i^{2}epsilon Theta(n^{3})]
n2ϵΘ(n3)
2nϵΘ(2n+1)
n!ϵΘ((n+1)!).
7 M
5 (c)
Suppose we are comparing implementations of insertion sort and merge sort on the
same machine. For input of size n, insertion sort runs in 8n 2 steps, while merge sort runs
in 64n lg n steps. For which values of n does insertion sort beat merge sort?
5 M
5 (d)
Given a knapsack having maximum weight capacity W=4, and number of items available are three, such that
S=3
wi=<1, 3, 4>
vi=<3, 4, 5>
Fill the knapsack using dynamic programming such that knapsack should not exceed its maximum capacity and it should have maximum profit value. Is dynamic programming a Top-Down or a Bottom-Up technique? Why?
S=3
wi=<1, 3, 4>
vi=<3, 4, 5>
Fill the knapsack using dynamic programming such that knapsack should not exceed its maximum capacity and it should have maximum profit value. Is dynamic programming a Top-Down or a Bottom-Up technique? Why?
5 M
5 (e)
Write the recurrence for solving Tower of Hanoi problem having n rings and 3 rods and solve the recurrence.
4 M
More question papers from Design And Analysis Of Algorithm