What is an algorithm? Explain various properties of an algorithm.
[3 marks]What is Amortized analysis? Explain different Methods for Amortized analysis.
[4 marks]Why do we use asymptotic notations in the study of algorithms? Briefly describe the commonly used asymptotic notations.
[7 marks]Explain general characteristics of greedy algorithms.
[3 marks]What is the use of Loop Invariant? Explain different between Loop Invariant Condition and Loop Condition.
[4 marks]Sort the following numbers using Bucket Sort. 45, 96, 29,30,27,12,39,61,91
[7 marks]llustrate the working of the quick sort on input instance: 25, 29, 30, 35, 42, 47, 50, 52, 60. Comment on the nature of input i.e. best case, average case or worst case.
[7 marks]Explain how divide and conquer approach work?
[3 marks]Explain Merge Sort algorithm with suitable example.
[4 marks]For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the 0/1 knapsack problem using dynamic programming. ItemWeightValue I1 2 I2 3 I3 4 I4 5
[6 marks]Explain Multiplying large Integers Problem.
[3 marks]Write an algorithm for Max-Min problem using divide and conquer approach. Calculate its complexity. Page 1 of
[3 marks]Find minimum spanning tree for the given graph in fig-1 using prim’s algorithm
[7 marks]How huffman code is memory efficient compare to fixed length code?
[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]Define minimum spanning tree. Explain Prim’s algorithm with suitable example.
[7 marks]Explain principle of optimality with suitable example.
[3 marks]Find Longest Common Subsequence of given two strings using Dynamic Programming. S1=abbacdcba S2=bcdbbcaa
[4 marks]Solve Coin Change problem using Dynamic Programming. Take an example for Denominations: d1=1, d2=4, d3=6, give your answer for making change of Rs.9.
[7 marks]Differentiate between Backtracking and Branch-and- Bound algorithms.
[3 marks]Traverse the following graph using Breadth First Search Technique. Also draw BFS Tree for a given graph.
[4 marks]What is Minimum Spanning Tree (MST)? Explain Dijkastra’s shortest path algorithm to create the MST.
[7 marks]Define BFS. How it is differ from DFS.
[3 marks]Explain Matrix chain multiplication briefly using dynamic programming algorithm.
[4 marks]Explain Backtracking Method. What is N-Queens Problem? Give solution of 4- Queens Problem using Backtracking Method. Page 2 of Page 3 of
[3 marks]