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)
Explain Greedy method in detail with example and differentiate it with dynamic
method.
7 M
2 (a)
Sort the letters of word 'DESIGN' in alphabetical order using bubble sort.
7 M
2 (b)
Write algorithm to find Minimum Spanning Tree (MST) using Prim's method and Compute its time complexity.
7 M
2 (c)
Define MST. Explain Kruskal's algorithm with example for construction of MST.
7 M
3 (a)
Sort the following list using quick sort algorithm: <50, 40, 20, 60, 80, 100, 45,
70, 105, 30, 90, 75> Also discuss worst and best case of quick sort algorithm.
7 M
3 (b)
Given two sequences of characters, P=, Q= Obtain the
longest common subsequence.
7 M
3 (c)
Given the four matrix find out optimal sequence for multiplication D=<15,5,10,20,25>.
7 M
3 (d)
Given coins of denominations 1,3 and 4 with amount to be pay is 7. Find optimal
no. of coins and sequence of coins used to pay given amount using dynamic
Method.
7 M
4 (a)
Write a brief note on NP-completeness and the classes-P, NP and NPC.
7 M
4 (b)
Explain the heap sort in detail. Give its complexity.
7 M
4 (c)
Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 Queens Problem using Backtracking Method.
7 M
4 (d)
Explain finite automata algorithm for string matching.
7 M
5 (a)
Solve following knapsack problem using dynamic programming algorithm with
given capacity W=5, Weight and Value are as follows :
(2,12),(1,10),(3,20),(2,15)
(2,12),(1,10),(3,20),(2,15)
7 M
5 (b)
Explain Rabin-Karp Algorithm for string matching and give it complexity.
7 M
5 (c)
Explain Selection Sort Algorithm and give its best case, worst case and average
case complexity.
7 M
5 (d)
Show how divide and conquer technique is used to compute product of two n
digit no with example.
7 M
More question papers from Analysis And Design Of Algorithms