N A L A N D A O P E N U N I V E R S I T Y
Master of Computer Application Part-I
PAPER-VII
(Design and Analysis of Algorithms)
Annual Examination, 2016
Time 3 Hours. Full Marks 80
Answer any Five Questions.
All questions carry equal marks.
1. Write an- algorithm to build a heap from a given sequence. Illustrate the heap sort algorithm
on the sequence 10, 12, 16.
2. Explain recurrence with an example. Prove that f 2n3 3n 5 is O(n3).
3. List the major differences between Divide and Conquer and dynamic programming design
techniques for solving problems.
4. Define fractional Knap-Sack problem, and give a greedy algorithm to solve this problem
efficiently.
5. What is a binary tree? Give a recursive function to find the height of a binary tree. What is the
running time of this algorithm?
6. Identify the tree edges, back edges and forward edges. Give an algorithm for topological sort.
Obtain a topological ordering for the following graph:
7. Explain the Kruskal-algorithm for Minimum Spanning Tree construction. Derive the
running time of the algorithm.
8. Define Regular Languages. Write regular expression corresponding to the following Languages
over alphabet b}.
Strings with even length.
Strings with odd number of and even number of b's.
9. Write context free grammar for the following languages.
Even palindromes over
Odd palindromes over b}.
10. Write short notes on the following
Clique problem
Vertex Cover
Turing machine.