 MORE IN Data Structure & Algorithm Analysis
MU Information Technology (Semester 3)
Data Structure & Algorithm Analysis
December 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) Explain the Asymptotic notations to measure the time complexity of algorithm.
5 M
1(b) What are linear and non-linear data structures?
5 M
1(c) Explain vectors with at least five methods.
5 M
1(d) Discuss circular and priority queue.
5 M

2(a) Write a program to create ?QUEUE? ADT using Linked list implementation. ADT should support following operations:-
(i) Create queue
(ii) Enqueue
(iii) Dequeue
(iv) Display
10 M
2(b) Explain Huffman Coding algorithm with example.
10 M

3(a) Write a program to implement Quick sort and comment on its complexity.
10 M
3(b) Implement the function to delete a node from Binary search tree. (consider all cases)
10 M

4(a) Write a program to create Binary tree and inorder, preorder and postorder traversal of the tree.
10 M
4(b) Write any pattern matching algorithm and explain with an example.
10 M

5(a) Using Prim's and Kruskal's algorithm find Minimum Spannin tree for the following graph. 10 M
5(b) What is Hashing? What is meant by collision? Hash the following in table of size 10. Use any two collision resolution techniques:- 99, 33, 23, 44, 56, 43, 19
10 M

6(a) Given a 'INFIX' expression, write a program to convert it to its 'POSTFIX' form.
10 M
6(b) Write an algorithm to traverse a graph using:
ii) Depth first search
10 M

Write short notes on any four of the following:-
7(a) Red Black trees
5 M
7(b) Searching algorithms
5 M
7(c) Recursion
5 M