Define Algorithm. Discuss key characteristics of algorithm.
[3 marks]Sort the letters of word “EXAMPLE” in alphabetical order using insertion sort.
[4 marks]Explain different asymptotic notations in brief.
[7 marks]Write an algorithm of Selection Sort Method. Give its complexity.
[3 marks]Explain how multiplication of large integers can be done efficiently by using divide and conquer technique.
[4 marks]Write the quick sort algorithm. Trace the same on data set - 40,32,15,94,82,29,42,73.
[7 marks]Give the properties of Heap Tree. Sort the following data with Heap Sort Method: 65, 75, 5, 55, 25, 30, 90, 45, 80.
[7 marks]Define amortized analysis. Briefly explain its two techniques.
[3 marks]Differentiate BFS and DFS.
[4 marks]Given two sequences of characters, P=<ABCDABE>, Q=<CABE > Obtain the longest common subsequence.
[7 marks]Differentiate greedy programming approach with dynamic programming approach.
[3 marks]Solve following recurrence using master method T(n) = 9T(n/3) +n
[4 marks]Using greedy algorithm find an optimal schedule for following jobs with n=7 profits: (P1, P2, P3, P4, P5, P6, P7) = (3, 5, 18, 20, 6, 1, 38) and deadline (d1, d2, d3, d4, d5, d6, d7) = (1, 3, 3, 4, 1, 2, 1)
[7 marks]What is Principle of Optimality in dynamic programming? Explain it with example.
[3 marks]Find an optimal Huffman code for the following set of frequency. a : 50, b: 20, c: 15, d: 30. Page 1 of
[2 marks]Solve Making Change problem using Dynamic Programming. (Denominations: d1=1, d2=4, d3=6). Give your answer for making change of Rs. 9.
[7 marks]Explain: Articulation Point, Graph, Tree
[3 marks]Demonstrate Binary Search method to search Key = 14, form the array A= <2,4,7,8,9,10,12,14,18>
[4 marks]Write equation for Matrix Chain 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 solution.
[7 marks]Explain Depth First Traversal Method for Graph with algorithm.
[3 marks]Consider Knapsack capacity W=15, w = (4, 5, 6, 3) and v=(10, 15, 12, 8) find the maximum profit using greedy method.
[4 marks]What is a minimum spanning tree? Draw the minimum spanning tree correspond to following graph using Prim’s algorithm. (Consider starting vertex 1)
[7 marks]Write down the characteristics of Greedy Algorithm.
[3 marks]Define: Directed Acyclic Graph, Dense graph, Sparse graph, Preconditioning.
[4 marks]Solve the following 0/1 Knapsack Problem using Dynamic Programming. There are five items whose weights and values are given in following arrays. Weight w[] = { 1,2,5,6,7 } Value v[] = { 1,6,18, 22, 28 } Show your equation and find out the optimal knapsack items for weight capacity of 11 units. Page 2 of
[2 marks]