M.Sc. DEGREE EXAMINATION, APRIL 2018
First Semester
Computer Science
DATA STRUCTURES AND ALGORITHMS
(CBCS — 2011 onwards)
Time 3 Hours Maximum 75 Marks
Part A (10 x 2 20)
Answer all questions.
1. Define: Space Complexity.
2. What is best-case step count?
3. What do you mean by Subset Paradigm?
4. Define: Weighted Trees.
5. Write the difference between Greedy Method and
dynamic programming.
6. State principles of Optimality.
7. What is dead node?
8. What is Hamiltonian cycle?
9. What is approximate Scheme?
10. Write the objective of rounding.
Sub. Code
1MCE1C2
AFC-10835
2
Wk7
Part B x 5 25)
Answer all questions choosing either or
11. Write algorithm for Addition and Deletion assuming
the Queue is represented as a linked list.
Or
Write a note on graph.
12. Discuss about the tree vertex splitting algorithm.
Or
Explain the algorithm to generate a two-way merge
tree.
13. How multistage graph problems can be solved by
backward approach? Explain.
Or
Write the steps for Informal knapsack algorithm.
14. Write the pseudocode for breath First Search.
Or
Show that if G is a connected graph, then no edge of
G can be in two different bi connected components.
15. What is interval partitioning? Explain.
Or
Obtain an O(n logn) algorithm that implements the
LPT Scheduling rule.
AFC-10835
3
Wk7
Part C x 10 30)
Answer any three questions.
16. Explain the Merge Sort Algorithm with an example.
17. How to generate shortest paths using Greedy Algorithm?
Explain.
18. Explain the OBST Algorithm.
19. Write the pseudocode for Depth First Search.
20. Write a note on Separation Method.
————————