## Data Structure & Algorithm Analysis - Dec 2012

### Information Technology (Semester 3)

TOTAL MARKS: 80

TOTAL TIME: 3 HOURS
(1) Question 1 is compulsory.

(2) Attempt any **three** from the remaining questions.

(3) Assume data if required.

(4) Figures to the right indicate full marks.
**1(a)** Write an algorithm for Binary search method with example.(5 marks)
**1(b)** Explain Asymptotic notations and write the properties of asymptotic notations.(5 marks)
**1(c)** What are linear and non-linear data structures?(5 marks)
**1(d)** What is a vector? Explain any four functions.(5 marks)
**2(a)** Define Binary Tree. Write an algorithm to implement different tree traversal techniques.(10 marks)
**2(b)** Write a program to create a singly linked list and display the list.(10 marks)
**3(a)** Write an algorithm for merge sort and comment on its complexity.(10 marks)
**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 marks)
**4(a)** Write a program to implement queue using array.(10 marks)
**4(b)** Explain Huffman algorithm. Construct Huffman tree for MAHARASHTRA with its optimal code.(10 marks)
**5(a)** Write an algorithm to traverse a graph using :

i) Breadth first search

ii) Depth first search(10 marks)
**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 marks)
**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 marks)
**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 marks)

### Write short notes on any four of the following:-

**7(a)** Pattern Matching(5 marks)
**7(b)** Expression tree(5 marks)
**7(c)** Red and Black trees(5 marks)
**7(d)** Shortest path algorithm(5 marks)
**7(e)** Priority and circular queue(5 marks)
**7(f)** Selection sort(5 marks)