MCS-031 Design and Analysis of Algorithms Solved Assignment 2019-2020

Course Code : MCS-031
Course Title : Design and Analysis of Algorithms
Assignment Number : MCA(III)-031/Assignment/2019-20
Maximum Marks : 100
Weightage : 25%
Last Date of Submission : 15th October, 2019 (For July, 2019 session)
15th April, 2020 (For January, 2020 session)

Note: This assignment has 20 questions of 80 marks (each question carries equal
marks). Answer all the questions. Rest 20 marks are for viva voce. Please go
through the guidelines regarding assignments given in the Programme Guide for
the format of presentation.

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
2 5 6
3
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? how they are different from context sensitive
Languages? If L1 and L2 are context free languages then, prove that L1 U L2 is context free
language.
Q10. Compare Turing machine and push down automata. Construct a Turing Machine TM to
accept all languages of palindromes on the set of alphabets ∑ = (𝒂, 𝒃).
Q11. Compare Non-Deterministic Finite Automata and Deterministic Finite Automata. Write
the finite automata corresponding to the regular expression (a + b)*ab. Also prove that
for any set S of Strings S*=(S*)*= S**.
Q12. Differentiate the following give suitable example for each
a. NP-hard problems and NP complete Problems.
b. Push Down Automata and Turing Machine
c. Decidable problems and Undecidable problems
d. Quick Sort and Randomized quick sort
e. Greedy Techniques and Divide & Conquer Techniques
Q13. Discuss the following with suitable example for each
f. Vertex Cover problem
g. Knapsac problem
h. Strassen’s algorithm
i. Dynamic Programming

MCS-031, MCS-31, MCS 031, MCS 31, MCS031, MCS31, MCS