MORE IN Data Structure & Algorithm Analysis
MU Information Technology (Semester 3)
Data Structure & Algorithm Analysis
December 2016
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) Define Algorithm and write its properties.
3 M
1(b) Write properties of B-Tree.
3 M
1(c) Define minimum spanning trees with examples.
3 M
1(d) What is Queue ADT? Mention its operations.
3 M
1(e) What is linked list? Explain types of linked list.
3 M
1(f) Define Recursion? State its advantages and disadvantages.
3 M
1(g) Explain linear and non-linear data structures.
2 M

2(a) Write a program to implement queue using arrays.
10 M
2(b) Write an algorithm for insertion and traversal in a circular linked list.
10 M

3(a) Write a program to convert INFIX expression into POSTFIX expression.
10 M
3(b) Wriet an algorithm to implement Heap-sort. Also comment on its complexity.
10 M

4(a) Define AVL Tree? Construct AVL Tree for the following data (Mention type of rotation for each case) 10,40,30,20,70,50,45.
10 M
4(b) Write a program to implement Priority Queue.
10 M

5(a) Explain BFS and DFS algorithm with examples.
10 M
5(b) What is Binary Search-Tree? Construct the Binary Search Tree for the following set of data: 14, 10, 1, 20, 17, 24, 18, 12, 15, 11, 4, 6.
10 M

Write a short note any four Q6..(a,b,c,d,e,f)
6(a) Red-black Trees
5 M
6(b) Searching Algorithms
5 M