Define the following questions: i. Define space complexity. ii. Define Feasible Solution. iii. Define P-type Problem. iv. Define Directed Acyclic Graph. v. Define Minimum Spanning Tree. vi. Write down the Best case, Worst Case and Average case Complexity for Heap sort. vii. What is vector? Which operations are performed on vector?
[7 marks]Explain the difference between Greedy and Dynamic Algorithm.
[7 marks]Apply the bubble sort algorithm for sorting {U,N,I,V,E,R,S}
[7 marks]Analyze Selection sort algorithm in best case and worst case.
[7 marks]Analyze Quick sort algorithm in best case and worst case.
[7 marks]What is recurrence? Solve recurrence equation T (n) =T (n-1) + n using forward substitution and backward substitution method.
[7 marks]Sort the given elements with Heap Sort Method: 20, 50, 30, 75, 90, 60, 25, 10, 40.
[7 marks]Write Huffman code algorithm and Generate Huffman code for following Letters A B C D E Frequencies 24 12 10 8
[8 marks]Write equation for Chained matrix multiplication using Dynamic programming. Find out optimal sequence for multiplication: A1 [5 × 4], A2 [4 × 6], A3 [6 × 2], and A4 [2 × 7]. Also give the optimal parenthesization of matrices.
[7 marks]Explain Depth First Traversal Method for Graph with algorithm with example.
[7 marks]Explain how to find out Longest Common Subsequence of two strings using Dynamic Programming method. Find any one Longest Common Subsequence of given two strings using Dynamic Programming. X=abbacdcba Y=bcdbbcaac
[7 marks]Define P, NP, NP complete and NP-Hard problems. Give examples of each.
[7 marks]Give and explain Rabin-Carp string matching algorithm with example.
[7 marks]Discuss matrix multiplication problem using divide and conquer technique.
[7 marks]Discuss Assembly Line Scheduling problem using dynamic programming with example.
[7 marks]Sort the letters of word “EDUCATION” in alphabetical order using insertion sort.
[7 marks]What is an amortized analysis? Explain aggregate method of amortized analysis using suitable example.
[7 marks]