Quick Links
| University Papers | University Syllabus | Entrance Exam |
| PSU Papers | Bank Papers | Placement Papers |
| VTU | Anna Univerity Syllabus | Anna Univerity Papers |
Anna University Question Paper
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)
University Papers | Syllabus | Entrance Exam | Govt & PSU Papers | Bank Papers
Programming Questions | Travel Tips | Mobile Review | Placement Papers | Books
ANNA UNIVERSITY SYLLABUS: CLICK HERE
For More Question paper of CSE - CLICK HERE
For More Question paper of IT - CLICK HERE
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)
0 Comments