SE (IT) Semester III Data Structure & Algorithms May 2009.

S.E. (IT) Sem 3rd

Data Structure & Algorithms (May 2009)

Con. 2996-09.

VR-3393

(3 Hours)

[Total Mark 100]

N. B.:- (1) Question No. 1 is compulsory.
(2) Answer any four out of remaining six questions.
(3) All Programs are to be written in JAVA only.
1. (a) What is Recursion? Give disadvantage of recursion. Write a programme to implement Tower of Hanoi.--10 Marks
(b) Explain Asympotic Notations (0, Ω,.θ) and write the properties of asymptotic notations.--5 Marks
(c) Explain packages and how do we hide classes using packages.--5 Marks
2. (a) Write a program to implement Quick sort and comment on its complexity.--10 Marks
(b) Write an algorithm for binary search method with example.--6 Marks
(c) Explain vectors with at least five methods.--4 Marks
3. (a) Write a program to implement Circular queue using array.--10 Marks
(b) Explain Huffman Algorithm. Construct Huffman tree for “MALAYALAM” with its optimal code.--10 Marks
4. (a) Write an algorithm to traverse a graph using – (with example)-- 10 Marks

1. Breath First Search
2. Depth First search

(b) Implement the function to delete a node from Binary Search Tree.--10 Marks
(Consider all possible cases.)

5. (a) Draw the minimum cost spanning tree using Kruskal’s algorithm. Also find its cost with all intermediate steps.--10 marks

(b) Write a program to implement STACK using Linked List.--10 marks
6. (a) Explain in brief--10 marks

1. Ascending heap
2. Desending heap

Write a program to implement heap sort.
(b) What is hashing? Explain Hashing methods and collision avoiding techniques.--10 marks
7. Write short notes on any four of the following with example.--20Marks
(a) AVL Tress
(b) B- Tress
(c) Shortest Path Algorithm.
(d) Pattern matching.
(e) Comparison of sorting Algorithms.
(f) Expression and realization of ADT’s in JAVA.

Also see Data structure & algorithms question papers for December-2010