 MORE IN Data Structure & Algorithm Analysis
MU Information Technology (Semester 3)
Data Structure & Algorithm Analysis
May 2011
Total marks: --
Total time: --
INSTRUCTIONS
(1) Assume appropriate data and state your reasons
(2) Marks are given to the right of every question
(3) Draw neat diagrams wherever necessary

1(a) What is a data structure and Abstract Data type?
5 M
1(b) Explain the Asymptotic notations to measure the time complexity of algorithm.
5 M
5 M
1(d) What is a vector? Explain any four functions.
5 M

2(a) Write an ADT for stack and implement it using array. The ADT should support the following operations.
i) Create
ii) Push
iii) Pop
iv) Display
10 M
2(b) Write an algorithm to implement Quick Sort. Derive its Best case and Worst case time complexity.
10 M

3(a) What is a Priority queue? Explain the insertion and deletion operations on a Priority queue if implemented using an array.
10 M
3(b) Explain the working of merge sort.
10 M

4(a) Define Binary Tree. Write an algorithm to implement different tree traversal techniques.
10 M
4(b) What is a Doubly linked list? Write an algorithm to implement to following operations with DLL :
1.Insertion (All cases)
2.Traverse (Forward and backward)
10 M

5(a) What is an AVL tree? Construct the AVL tree for the following set of data:14,10,1,20,17,24,18,12,15, 11, 4, 6
10 M
5(b) Explain Huffman algorithm for encoding the characters. And construct the Huffman's code for following characters. 10 M

6(a) Using Prim's and Kruskal's algorithm find Minimum Spannin tree for the following graph. 10 M
6(b) What do you mean by Hashing and Collision. How do you resolve hash clashes?
10 M

Write short notes on any four of the following:-
7(a) MAP abstract Data Type
5 M
7(b) Splay Tree
5 M
7(c ) Pattern Matching
5 M
7(d) Graph Traversal
5 M
7(e) Expression Tree
5 M

More question papers from Data Structure & Algorithm Analysis