M.E./M.Tech. DEGREE EXAMINATION, JANUARY 2012.

First semester

Computer Science and Engineering

CS 9212-DATA STRUCTURES AND ALGORITHMS

(Common to M.Tech Information Technology)

(Regulation 2009)

Time: Three hours

Maximum: 100 marks

Answer ALL the Questions

PART A— (10 × 2 = 20 marks)

1. Mention any two properties of big Oh notation.

2. What is a threaded binary tree?

3. What are skew heaps?

4. Give the class definition of a double ended priority queue.

5. Define a height balanced tree.

6. List out any two applications of splay trees.

7. What is convex hull?

8. Write the time complexity and space complexity of Quick sort for best case.

9. What is meant by backtracking?

10. What is dynamic programming?

PART B— (5 × 16 = 80 marks)

11. (a) Write a program, to determine if a positive integer, n, is a prime.

(i)Discuss the worst-case running time of the program. (8)

(ii) Let B equal the number of bits in the binary representation of n. In terms of B, find out the worst-case running time of the program. (8)

Or

(b) Perform the following using doubly linked list:

(i) Insert ‘n’ digits to generate a number. (8)

(ii) Check if the number is a palindrome or not and display the output. (8)

12. (a)Write functions to do the following in a min-max heap:

(i) Insert an element (8)

(ii) Delete an element (8)

Or

(b) Write C++ member function to implement the following Fibonacci Heap operations

(i) Create an empty F-heap. (8)

(ii) Insert element x into F-heap. (8)

13. (a) Perform the following:

(i) Develop functions FindNode, NewRoot, PutIn and split of a 2-3 tree. (8)

(ii) Putting these together, develop the function Two3::InSert (8)

Or

(b) Compare the worst-case height of a red black tree with ‘n’ nodes with that os an AVL tree

with the same number of nodes. (16)

14. (a) Analyze the time complexity of Strassen’s matrix multiplication that uses Divide and

Conqure. (16)

Or

(b) Assume that there are 10 jobs, J1, J2, …..J10 with associated running times

3,5,6,10,11,14,15,18,20,21 and 3 number of Processors. Find the optimal arrangement to

minimize mean completion time using Greedy algorithm. (16)

15. (a) Solve Graph coloring problem using dynamic programming. (16)

Or

(b) Solve the (8-Queens) problem by backtracking, (16)