Important Question of ADA (2150703)

Explain Asymptotic notation. Arrange the growth rate of 2^n, n^2,1, log n, n logn, 3^n and n in increasing order of growth. (7 Mark)
Find out the Ө-notation for the function: f(n)=27n^2+16n. (4 Mark)
What is recurrence? Explain recursion-tree method with suitable example. (7 Mark)
Write the Master theorem. Solve following recurrence using it. (7 Mark)
(i) T(n)=9T(n/3) + n
(ii) T(n)=3T(n/4) + nlgn
Write the best and worst running time of Insertion sort algorithm. Why it differ? (3 Mark)
Which are the basic steps of counting sort? Write counting sort algorithm. Derive its time complexity in worst case. (7 Mark)
Solve following recurrence using recursion tree method: T(n) = 3T(n/3) + n^3. (4 Mark)
Analyze Selection sort algorithm in best case and worst case. (7 Mark)
Apply the bubble sort algorithm for sorting {U,N,I,V,E,R,S} (4 Mark)
Solve the following recurrence relation using substitution method. T(n) = 2T(n/2) + n. Here T(1) = 1. (7 Mark)
Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40. (7 Mark)

Write standard(conventional) algorithm and Strassen's algorithm for matrix multiplication problem. What is the recurrence for Strassen's algorithm? Solve it using master method to derive time complexity of Strassen's algorithm. (7 Mark)
Discuss best case, average case and worst case time complexity of quick sort. (7 Mark)
Write Merge sort algorithm and compute its worst case and best-case time complexity. Sort the List G,U,J,A,R,A,T in alphabetical order using merge sort. (7 Mark)
Demonstrate Binary Search method to search Key = 14, form the array A=<2,4,7,8,10,13,14,60>. (4 Mark)
Analyze Quick sort algorithm in best case and worst case. (7 Mark)
Multiply 981 by 1234 by divide and conquer method. (3 Mark)
Discuss matrix multiplication problem using divide and conquer technique. (7 Mark)

Give difference of dynamic programming and divide-and- conquer method. (4 Mark)
Using dynamic programming find out the optimal sequence for the matrix chain multiplication of A4x10, B10x3, C3x12, D12x20 and E20x7 matrices. (7 Mark)
What are the steps for dynamic programming? Explain principal of optimality. (4 Mark)
Determine LCS of {1,0,0,1,0,1,0,1} and {0,1,0,1,1,0,1,1,0}. (7 Mark)
What are the advantages of dynamic programming method over devide-and- conquer method? (3 Mark)
Which are the three basic steps of the development of the dynamic programming algorithm? Mention any two examples of dynamic programming that we are using in real life. (4 Mark)
Solve the following making change problem using dynamic programming method: Amount = Rs. 7 and Denominations: (Rs. 1, Rs. 2 and Rs. 4). (7 Mark)
Consider Knapsack capacity W=9, w = (3,4,5,7) and v=(12,40,25,42) find the maximum profit using dynamic method. (7 Mark)
Solve Making change problem using dynamic technique. d1 = 1, d2=2, d3=4, d4=6, Calculate for making change of Rs. 10. (7 Mark)
Find out LCS of A={K,A,N,D,L,A,P} and B = {A,N,D,L} (7 Mark)
Find optimal sequence of multiplication using dynamic programming of following matrices: A1[10x100], A2[100x5], A3[5x50] and A4[50x1]. List optimal number of multiplication and parenthesization of matrices. (7 Mark)
Discuss Assembly Line Scheduling problem using dynamic programming with example. (7 Mark)

Differentiate greedy and dynamic programming. (3 Mark)
Explain general characteristics of greedy algorithms. (4 Mark)
Explain 0/1 knapsack using suitable example. (7 Mark)
Define spanning tree and MST. How Krushkal’s algorithm is different from Prim’s algorithm. (4 Mark)
Write and explain Dijkastra algorithm with example. (7 Mark)
Justify with example that longest path problem does not satisfy the principle of optimality. (3 Mark)
Discuss general characteristics of greedy method. Mention any two examples of greedy method that we are using in real life. (4 Mark)
What are the disadvantages of greedy method over dynamic programming method? (3 Mark)
Solve the following Knapsack Problem using greedy method. Number of items = 5, knapsack capacity W = 100, weight vector = {50, 40, 30, 20, 10} and profit vector = {1, 2, 3, 4, 5}. (7 Mark)
Write an algorithm for Huffman code. (3 Mark)
Find an optimal Huffman code for the following set of frequency. a : 50, b: 20, c: 15, d: 30. (4 Mark)
Define MST. Explain Kruskal’s algorithm with example for construction of MST. (7 Mark)

Write just steps for Backtracking and Branch-and-Bound algorithms. (4 Mark)
Explain use of branch and bound technique for solving assignment problem. (7 Mark)
Differentiate branch and bound and back tracking algorithm. (4 Mark)
Draw the state space tree Diagram for 4 Queen problem. (3 Mark)
Solve the following instance of knapsack problem using Backtracking Technique. The Capacity of the Knapsack W = 8 and w = (2,3,4,5) and value v = (3,5,6,10). (7 Mark)
Explain Backtracking Method. What is N-Queens Problem? Give solution of 4 Queens Problem using Backtracking Method. (7 Mark)

What is string-matching problem? Define valid shift and invalid shift. (3 Mark)
Write pseudo-code for Naïve-String-Matching algorithm. (3 Mark)
Write Naive string-matching algorithm. Explain notations used in the algorithm. (3 Mark)
Working modulo q = 11. How many spurious hits does the Rabin-Karp matcher encounter in the text T = 3141592653589793 when looking for the pattern P =26? (7 Mark)
Explain finite automata for string matching with example. (7 Mark)

Define P, NP, NP-complete and NP-hard problems. (4 Mark)
Explain “P = NP ?” problem. (3 Mark)
Explain travelling salesman problem. Prove that it is NP complete problem. (7 Mark)
What is an approximation algorithm? Explain performance ratio for approximation algorithm. (4 Mark)
Explain polynomial-time reduction algorithm. (4 Mark)
Which are the three major concepts used to show that a problem is an NP- Complete problem? (3 Mark)
Explain Traveling salesman problem with example. (7 Mark)
Write a brief note on NP-completeness and the classes-P, NP and NPC. (7 Mark)

Javapcode