Anna University Chennai 2011-3rd Sem B.E Electrical and Electronics Engineering ./B.Tech , IL/ (ester, )-DATA STRUCTURES AND ALGORITHMS - Question Paper

B.E./B.Tech. DEGREE EXAMINATION, APRIL/MAY 2011
Third Semester Electrical and Electronics Engineering
EE 2204 — DATA STRUCTURES AND ALGORITHMS
(Regulation 2008) Time : 3 hours Maximum : 100 marks
ans ALL ques.
__________________________________________________________________________________________________

PART A — (10 × two = 20 marks)

1. describe stack. elaborate the operations performed on a stack?
2. Mention the applications of list.
3. describe tree. List the tree traversal techniques.
4. Differentiate a binary tree from a binary search tree.
5. What is meant by binary heaps?
6. What is linear hashing? Specify its merits and demerits.
7. What is meant by digraph? describe the terms in-degree and out-degree with respect to a digraph.
8. Write the adjacency matrix for the subsequent graph.
9. What is dynamic programming? provide 2 examples.
10. What is meant by NP-complete problem?
_______________________________

PART B — (5 × 16 = 80 marks)
11. (a) What is doubly linked list? discuss the algorithm in detail for inserting a node to the left and deleting a node from a doubly linked list. (16)
Or
(b) Write an algorithm and discuss how insertions and deletions are carried out in a circular queue implemented using linked list. (16)

12. (a) (i) explain how a node could be inserted in a binary tree? (8)
(ii) Write a procedure in C to obtain the Kth element in binary tree. (8)
Or
(b) (i) Derive the expression tree for the expression (a + b + c) + ((d *e + f ) * g ) . Briefly discuss the construction procedure for the above. (6)
(ii) Write routines to implement the basic binary search tree operations. (10)

13. (a) discuss with algorithm how insertion and deletion is performed in a AVL tree. discuss how the tree is balanced after the operation. (16)
Or
(b) (i) Write a procedure in C that will traverse a linked B-tree, visiting all its entries in order of keys (smaller to larger). (10)
(ii) What is meant by collision in hashing? discuss the separate chaining collision resolution strategy. (6)

14. (a) (i) describe Graph. Briefly discuss the graph traversal algorithms with an example.(8)
(ii) obtain the shortest path from node one to seven using shortest path algorithm. (8)
Or
(b) With an example, discuss Kruskals algorithm for finding minimum spanning tree.(16)

15. (a) (i) Develop an algorithm for binary search using divide and conquer method. Analyze its time and space complexity. (8)
(ii) Write a greedy algorithm to solve job sequencing with deadline issue. (8)
Or
(b) (i) discuss any 1 algorithm to solve bin packing issue. (6)
(ii) discuss backtracking algorithm design technique with an example. (10)

Earning:   Approval pending.