STUPIDSID
1 (a)
Explain following terms with example.
1. Set
2. Relation
3. Function
1. Set
2. Relation
3. Function
6 M
1 (b)
Do as directed.
1. Calculate computation time for the statement t3 in following code fragment?
for i = 1 to n
{
for j = 1 to i
{
c = c + 1 .................... t3
}
}
2. Prove that T(n)=1+2+3+.......+n=Θ(n2).
1. Calculate computation time for the statement t3 in following code fragment?
for i = 1 to n
{
for j = 1 to i
{
c = c + 1 .................... t3
}
}
2. Prove that T(n)=1+2+3+.......+n=Θ(n2).
8 M
2 (a) (i)
Write an algorithm for insertion sort.
3 M
2 (a) (ii)
Analyze insertion sort algorithm for best case and worst case.
4 M
2 (b)
Define an amortized analysis. Briefly explain its different techniques.
Carry out aggregate analysis for the problem of implementing a k-bit
binary counter that counts upward from 0.
7 M
2 (c)
Analyze quick sort algorithm for best case, average case and worst case with example.
2. In which case it performs similar to selection sort?
2. In which case it performs similar to selection sort?
7 M
3 (a)
1. Mention applications of minimum spanning tree.
2.Generate minimum spanning tree from the following graph using Prim?s algorithm. (Start at vertex a).
2.Generate minimum spanning tree from the following graph using Prim?s algorithm. (Start at vertex a).
7 M
3 (b)
Discuss matrix multiplication problem using divide and conquer technique.
7 M
3 (c)
Following are the details of various jobs to be scheduled on multiple processors such that no two processes execute at the same on the same Processor
1) Show schedule of these jobs on minimum number of processors using greedy approach.
2) Derive an algorithm for the same.
3) What is the time complexity of this algorithm?
| Jobs | J1 | J2 | J3 | J4 | J5 | J6 | J7 |
| Start time | 0 | 3 | 4 | 9 | 7 | 1 | 6 |
| Finish time | 2 | 7 | 7 | 11 | 10 | 5 | 8 |
1) Show schedule of these jobs on minimum number of processors using greedy approach.
2) Derive an algorithm for the same.
3) What is the time complexity of this algorithm?
7 M
3 (d)
Answer the following questions.
1. What are the differences between greedy approach and dynamic programming?
2. Explain class P and class NP.
1. What are the differences between greedy approach and dynamic programming?
2. Explain class P and class NP.
7 M
4 (a)
1) Find an optimal solution to the knapsack instance n=4, M=8, (P1,P2,P3,P4)=(3,5,6,10) and (W1,W2,W3,W4)=(2,3,4,5) using
Backtracking.
2) Also draw the corresponding state space tree.
2) Also draw the corresponding state space tree.
7 M
4 (b)
1) What is finite automata?
2) Explain with example how finite automaton is used for string matching?
2) Explain with example how finite automaton is used for string matching?
7 M
4 (c)
1) Write an algorithm to find out the articulation points of an undirected graph.
2) Find out articulation points for the following graph. Consider vertex A as the starting point.
7 M
4 (d)
1) Explain spurious hits in Rabin-Karp string matching algorithm with
example.
2) Working modulo q=13, how many spurious hits does the Rabin-Karp matcher encounter in the text T = 2359023141526739921 when looking for the pattern P = 31415?
2) Working modulo q=13, how many spurious hits does the Rabin-Karp matcher encounter in the text T = 2359023141526739921 when looking for the pattern P = 31415?
7 M
5 (a)
1) Generate equation for Matrix chain multiplication using Dynamic
Programming.
2) Find out minimum number of multiplications required for multiplying:
A[1×5],B[5×4],C[4×3],D[3×2] and E[2×1].
3) Also give the optimal parenthesization of matrices.
2) Find out minimum number of multiplications required for multiplying:
A[1×5],B[5×4],C[4×3],D[3×2] and E[2×1].
3) Also give the optimal parenthesization of matrices.
7 M
5 (b)
Discuss and derive an equation for solving the 0/1 Knapsack problem
using dynamic programming method. Design and analyze the algorithm
for the same.
7 M
5 (c)
1) Discuss and derive the optimal substructure that can be used to solve
the Longest Common Subsequence problem using dynamic
programming.
2) Find the longest common subsequence for the given two sequences of characters: P = (1,0,0,1,0,1,1,0,1,1,0,1); Q= ( 0,1,1,0).
2) Find the longest common subsequence for the given two sequences of characters: P = (1,0,0,1,0,1,1,0,1,1,0,1); Q= ( 0,1,1,0).
7 M
5 (d)
Discuss Assembly Line Scheduling problem using dynamic programming with example.
7 M
More question papers from Analysis And Design Of Algorithms