About Me

Data Structures And Algorithms CS9212 Jan2012 Question Ppaer

Sponsored Ads:

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

ANNA UNIVERSITY PAPERS: CLICK HERE

Download PDF File - 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)

Post a Comment

0 Comments