MORE IN Data Structure & Algorithm Analysis
MU Information Technology (Semester 3)
Data Structure & Algorithm Analysis
December 2012
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) Write an algorithm for Binary search method with example.
5 M
1(b) Explain Asymptotic notations and write the properties of asymptotic notations.
5 M
1(c) What are linear and non-linear data structures?
5 M
1(d) What is a vector? Explain any four functions.
5 M

2(a) Define Binary Tree. Write an algorithm to implement different tree traversal techniques.
10 M
2(b) Write a program to create a singly linked list and display the list.
10 M

3(a) Write an algorithm for merge sort and comment on its complexity.
10 M
3(b) Hash the following in a table of size 11. Use any two collision resolution techniques.
99 67 41 0 17 2 98 20 94 27
10 M

4(a) Write a program to implement queue using array.
10 M
4(b) Explain Huffman algorithm. Construct Huffman tree for MAHARASHTRA with its optimal code.
10 M

5(a) Write an algorithm to traverse a graph using :
i) Breadth first search
ii) Depth first search
10 M
5(b) 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

6(a) Write a program to implement Quick sort and show the steps to sort the following elements by Quick sort method:-
19, 27, 5, 9, 86, 45
10 M
6(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

Write short notes on any four of the following:-
7(a) Pattern Matching
5 M
7(b) Expression tree
5 M
7(c) Red and Black trees
5 M
7(d) Shortest path algorithm
5 M
7(e) Priority and circular queue
5 M
7(f) Selection sort
5 M

More question papers from Data Structure & Algorithm Analysis