B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS

Code No: R059211201Set No. 2II B.Tech I Semester Regular Examinations, November 2006ADVANCED DATA STRUCTURES & ALGORITHMS( Common to Information Technology and Computer Science & SystemsEngineering)Time: 3 hoursMax Marks: 80Answer any FIVE QuestionsAll Questions carry equal marks. . . . .

1. (a) What are the two steps that happen with delete p.
(b) What are the advantages of new operator than malloc in C.
(c) Explain about the C++ classes in detail and design a class for playing cards.[5+5+6]
2. What is template. Explain about function templates and class templates withsuitable examples.[16]
3. (a) Write a program to change the case of each word in a file to initial capitals.(b) Write a program to concatenate the two given strings.[8+8]
4. What are the di.erent mathematical notations used for algorithm analysis. 16]
5. Develop a class for hash table using linear probing and neverUsed concept to handlean erase operation. Write complete C++ code for all the methods. Include amethod to reorganize the table when (say) 60% of the empty buckets have neverused equal to false. The reorganization should move pairs around as necessary andleave a properly configured hash table in which neverUsed is true for every emptybucket.[16]6. What is an AVL Tree. Write the algorithm to search for an element of an AVLSearch Tree. What is its time complexity.[16]
7. (a) Explain the Binary tree in order traversal in o(n) and 0(1) space.
(b) Explain divide and conquer strategy by means of its control abstraction.
(c) What is the di.erence between Greedy method and Divide and conquer.[6+6+4]
8. (a) What are the general characteristics of greedy algorithms and the problemssolved by these algorithms.
(b) What is 0/1 Knapsack problem. Explain how principle of optimality appliesto it. Also derive its dynamic recurrence relation.[8+8]