NALANDA OPEN UNIVERSITY QUESTION, MCA, 2017, Part-I, Paper-VII (old) (Design and Analysis of Algorithm)

NALANDA OPEN UNIVERSITY QUESTION, MCA, 2017, Part-I, Paper-VII (old) (Design and Analysis of Algorithm) 

                                                                               2017
                                                                         Time: 3 hours
                                                                        Full Marks: 80
                                        Answer any five questions. All questions carry equal marks.

1. What is an algorithm ? Explain the characteristics of an algorithm. Give an algorithm to find the factorial of a number.

2. Write a recursive procedure for the following:-
    (a) To print the sum of first 10 natural numbers.
    (b) To print the sum of first 10 factorial numbers.

3. Compare and contrast different sorting algorithms with their complexities.

4. Write short notes on the following:-
    (a) Regular expression
    (b) Context free grammar

5. What is Push down Automata? How is it different from Finite Automata.

6. Compare and contrast between Heap sort and Merge sort. Give examples for each type.

7. Explain principal of optimality. Give an example of chained matrix multiplication.

8. Describe different types of minimum spanning tress with examples.

9. What is Best case analysis? Perform the best case analysis for quick sort.

10. Explain each of the following, with an appropriate example:-
      (a) Greedy algorithms
      (b) Halting Problem