IGNOU MCA 3rd Semester MCS-031 Solved Assignment 2019-20 Available Now
 |
IGNOU MCA 3rd Semester MCS-031 Solved Assignment 2019-20DOWNLOAD 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:
a
b c
d e
4
3 2 5 6
7 4
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
