Anna univ CS 252 — ALGORITHMS AND DATA STRUCTURES

PART A — (10 ? 2 = 20 marks)
1. When is an algorithm said to be correct?
2. Distinguish between NP–hard and NP–complete problems.
3. Give the recursive algorithm for finding the factorial of a positive integer.
4. Define Big–oh notation.
5. Give two differences between Data structures and ADTs.
6. Show that stacks follow the LIFO phenomenon.
7. What are priority queues?
8. Define complete graph and mixed graph.
9. Obtain the binary search tree for the following numbers :
10, 2, 5, 88, 92, 46, 11
10. Define hashing.
PART B — (5 ? 16 = 80 marks)
11. List and explain the properties of algorithms. How are deterministic algorithms different from non–deterministic algorithms?
12. (a) Explain the priori analysis of algorithms. Distinguish between priori and posterior analysis.
Or
(b) What is travelling salesman problem (TSP)? How will you solve it using the greedy method? Give its algorithm.
13. (a) What are the properties of recursive algorithms? How are recursive algorithms implemented using stacks? Explain with an example.
Or
(b) How will you represent polynomials using linked lists? Write an algorithm to add two polynomials.
14. (a) With an example, explain the minimum spanning tree algorithm.
Or
(b) Explain with examples the various representations of graphs.
15. (a) Write an algorithm to sort 10 numbers using binary sort. Show the steps involved in it with an example.
Or
(b) What is collision resolution? Explain the various methods.