# May 2012

N.S.: (1) Question NO.1 is compulsory.

(2) Attempt any four questions out of remaining six questions.

1.

(a) Write an algorithm for Binary Search Method with example. 5

(b) Explain Asympotic notations and write the properties of asympotic notations. 5

(c) What are linear and non-linear data structures? 5

(d) What is a Vector? Explain any four functions. 5

2.

(a) Define Binary Tree. Write on algorithm to implement different tree traversal 10 techniques. ‘.

(b) Write a program to create singly linked list and .display the list. 10

3.

(a) Write an algorithm for merge sort and comment on its complexity. 10

(b) Hash the following in a table of size 11. Use any  two collision resolution technique. 10

99 67 41 0 17 2 98 20 94 27.

4.

(a) Write a program to implement queue using array. 10

(b) Explain Huffman Algorithm. Construct Huffman tree for “MAHARASHTRA” with 10 its optimal code.

5.

(a) Write an algorithm to traverse a graph using – 10

(ii) Depth first seal’ch.

(b) Write an ADT for stack and implement it using array. The ADT should support 10

following operations :-

(i) Create

(ii) Push

(iii) POP

(iv) Display

6. (a) Write a program to implement Quick sort and show the steps to sort the following 10

elements by Quick sort method :-

19 27 5 9′ 86 4-5 .

(b) Wh~t”is Doubly Linked List? Write an algorithm to implement following operations 10

with DLL :-

(i) Insertion ‘(AII Cases)

(ii) Traverse (Forward and Backward)

7. Write short note on (any four) :-

(a) Pattern Matching

(b) Expression Tree

(c) Red and Black Trees

(d) Shortest Path Algorithm

(e) Priority and Circular Queue

(f) Selection Sort.