**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.**

Title Name | MCS-031 Solved Assignment 2019-2020 |

University | IGNOU |

Service Type | Solved Assignment (Soft copy/PDF) |

Course | MASTER OF COMPUTER APPLICATIONS(MCA) |

Language | ENGLISH |

Semester | MCA/ASSIGN/SEMESTER-III |

Session | 2019-20 |

Short Name | MCS-031 |

Assignment Code | MCA(III)/031/Assignment/2019-20 |

Product | Assignment of MCA 2020 (IGNOU) |

Price | Rs. 30 |

| 15th October, 2019 (For July, 2019 Session)15th April, 2020 (For January, 2020 Session) |

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

## Reviews

There are no reviews yet.