STUPIDSID
1 (a)
Why do we use asymptotic notations in the study of algorithms? Briefly describe the commonly used asymptotic notations.
7 M
1 (b)
Define MST. Explain Kruskal's algorithm with example for construction of MST.
7 M
2 (a)
Explain finite automata for string matching with example.
7 M
Solve any one question from Q2(b) & Q2(c)
2 (b)
Write a brief note on NP-completeness and the classes-P, NP and NPC.
7 M
2 (c)
What is the basic idea behind Rabin ' Karp algorithm? What is expected running
time of this algorithm? Explain it with example.
7 M
Solve any two question from Q3(a), Q3(b) & Q3(c), Q3(d)
3 (a)
Explain in brief characteristics of greedy algorithms. Compare Greedy Method with Dynamic Programming Method.
7 M
3 (b)
Explain the use of Divide and Conquer Technique for Binary Search Method.What is the complexity of Binary Search Method? Explain it with example.
7 M
3 (c)
Explain Breadth First Traversal Method for Graph with algorithm.
7 M
3 (d)
Explain Depth First Traversal Method for Graph with algorithm.
7 M
Solve any two question from Q4(a), Q4(b) & Q4(c), Q4(d)
4 (a)
What is an amortized analysis? Explain aggregate method of amortized analysis
using suitable example.
7 M
4 (b)
Discuss Assembly Line Scheduling problem using dynamic programming with example.
7 M
4 (c)
Write a program/algorithm of Quick Sort Method and analyze it with example.
7 M
4 (d)
Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 Queens Problem using Backtracking Method.
7 M
Solve any two question from Q5(a), Q5(b) & Q5(c), Q5(d)
5 (a)
Explain Chained Matrix Multiplication with example.
7 M
5 (b)
Explain Selection Sort Algorithm and give its best case, worst case and average
case complexity with example.
7 M
5 (c)
Discuss matrix multiplication problem using divide and conquer technique.
7 M
5 (d)
Sort the letters of word 'EDUCATION' in alphabetical order using insertion
Sort.
7 M
More question papers from Analysis And Design Of Algorithms