Define Knapsack Problem and cite one instance of the  knapsack problem. Compare Knapsack Problem with fractional  knapsack problem. Give a Greedy algorithm for fractional  Knapsack Problem.

Explain the essential idea of Dynamic Programming.  How  Dynamic programming differs from Divide and conquers  approach for solving the problems? 

Explain the meaning of Big O notation with suitableexample.  How does it differ from Theta and Omega notations.  Arrange  the following growth rates in increasing order: O(3n), O(n 2 ),  O(1), O(n log n) 

Differentiate Between

(i)  Greedy technique and Dynamic programming technique
(ii)  NP-Complete & NP Hard Problems
(iii)  Decidable & Un-decidable problems
(iv)  Context free & Context sensitive Language
(v)  Strassen’s Algorithm & Chain Matrix Multiplication algorithm 

Explain how dynamic programming reduces the complexity of a  simple algorithm. Also explain the matrix chain multiplication  algorithm in this context. Derive the principle of  optimality for  multiplication of matrix chain. Compute the optimalmultiplications  required following matrices.  A1 of order 30 x 35; A2 of order 35 x 15; A3 of order 15 x 5 

Write Quick Sort Algorithm. How is it Different from Randomized  Quick Sort Algorithm? Prove that that Worst case ofQuick Sort is  Best case of Bubble Sort.  Apply Quick sort Algorithm to sort the  following list:  Q U I C K S O R T, in alphabetical order. Find the  element whose position is unchanged in the sorted list. 

     Give a divide and conquer based algorithm (Write a  pseudo-code)  to perform following:
  (i)  find the is smallest element in an array of size. Derive the  running time complexity of your                 algorithm.
  (ii)  finding the position of an element in an array of n numbers  Estimate the number of key                    comparisons made by youralgorithms

Write Insertion sort algorithm. Determine its complexity in Best, Average and Worst Case. Sort the following sequencein increasing order: 35, 37, 18, 15, 40, 12; Using Insertion Sort.