Explain five characteristics of an algorithm briefly.
Write and explain recursive algorithm to find the factorial of any given number
Explain the importance of asymptotic analysis for running time of an algorithm with the help of an example.
Briefly describe Chomsky classification for Grammars. Using Dijkstra's algorithm, find the minimum. distances of all the nodes from node which is taken as the source node, for the following graph:
<img src='./qimages/11727-1e.jpg'> "The best-case analysis is not as important as the worst-case analysis of an algorithm." Yes or No Justify your answer with the help of an example.

2.(a) Explain how greedy approach is useful to find the solution to fractional knapsack problem.
Solve the following recurrence relation:

fn-fn-1

such that f0=0 and f1=1.

(c) Explain Turing Machine as a computer of functions, with the help of an example.

3.(a) Using Prim's algorithm, find a minimal spanning tree for the graph given below: <img src='./qimages/11727-3a.jpg'>
Sort the following sequence of numbers,using Selection Sort. Also find the number of comparisons and copy operations required by the algorithm in sorting this list:

20 5 15 8 6 28

4.(a) Using Depth First Search traverse the following graph by using A as the starting node: <img src='./qimages/11727-4a.jpg'> Define ohm notation used for comparing two functions.

For 3x^2 1 2x^3 2
show that ohm x^2
What is dynamic programming? Explain briefly the optimal substructure property of a dynamic programming problem.
What is NP-complete problem Is it necessary that every NP-complete problem must also be a NP-hard problem? Justify.

5.(a) Write an algorithm for Heap Sort and analyse its Best and Worst run time complexity.
Define a Turing Machine.
Consider the CFG:
S SS/XaXaX/^
Find the language generated by this CFG.