Tuesday, October 22, 2019

DOWNLOAD NOW

Q1. Enumerate five important characteristics of an Algorithm, and discuss any five wellknown

techniques for designing algorithms to solve problems. State Travelling Sales

Persons problem. Comment on the nature of solution to the problem.

Q2. Write recursive binary search algorithm and compare its run time complexity with the

non recursive binary search algorithm. Solve the recurrence T(𝑛) = 2T (𝑛/2) + 𝑛 𝑛≥2

= 1 n<2

Q3. Derive the principle of optimality for multiplication of matrix chain. Compute the

optimal number of scalar multiplication required to multiply the following matrices.

A1 of order 30*35

A2 of order 35*15

A3 of order 15*5

Q4. Write Selection sort Algorithm. Use it to sort the list 90, 42, 41, 120, 60, 50. Calculate the

complexity of the selection sort algorithm in best case , average case and worst case.

Q5. Sort the following elements using Heap Sort: 10, 28, 46, 39, 15, 12, 18, 9, 56, 2.Show

each step, while creating a heap and processing a heap. Also determine the Best case and

worst complexity of Heap sort algorithm. Prove that best case for bubble sort is worst

case for heap sort

Q6. Using Dijkstra’s algorithm, find the minimum distances of all the nodes from source node

‘a’ for the following graph:

b c

d e

3 2 5 6

7 4

Q7. Obtain the minimum cost spanning tree for the following graph using Prim’s algorithm.

Obtain the DFS and BFS tree for the graph given considering node “a” as root node.

Q8. Explain the Chomsky’s Classification of grammars. What is an ambiguous grammar?

How do you prove that a given grammar is ambiguous? Explain with an example. Write a

context free grammar to generate palindromes of even length Over the set of alphabets

Σ = {𝑎, 𝑏}.

Q9. What are context free languages

IGNOU HELP4U