SRM University 2007 B.Tech Information Technology IT203 - Data Structures and Design of Algorithms - Question Paper

5. Show the outcome of inserting 2,1,4,5,9,3,6,7 into an initially empty AVL tree.
6. Describe a data structure in which sequence of M operations takes total time of O(M log N).
7. a.What are B-Trees.?
bWite algorithms to perform ‘Insert’ and ‘Delete’ into a B-Tree.
8. Write algorithm to discuss various kinds tree traversals. discuss with example.
9. Write the algorithm to insert an element from the binary heap tree. discuss with example.
10. Write the algorithm to delete an element from the binary heap tree. discuss with example.
11. Show the outcome of inserting 10,12,1,14,6,5,8,15,3,9,4,11,13,and 2, 1 at a time, into an initially empty binary heap.



UNIT III

PART A
1. Sort the sequence 3,1,4,5,9,2,6,5 using insertion sort.
2. What is the running time of insertion sort in all elements are equal?
3. Show the outcome on running Shell sort on the input 9,8,7,6,5,4,3,2,1 using the shell sizes 7,3,1.
4. Write about the running time of heap sort.
5. sort 3,1,4,1,5,9,2,6 using merge sort.
6. Write algorithm for linear search.
7. Give best, worst, avg. case analysis of sequential search
8. Write about diminishing increment sort.
9. What is meant by External Sorting?
10. Explain about Multiway Merge Sorting.
11. Construct a heap tree : 99,77,44,22,1,76,89,91,90
12. Explain about the basics of Hashing technique
13. Write about bucket sorting.
14. Define open hashing and closed hashing.

PART B

1. Write algorithm to implement insertion sort and explain about the running time.
2. Show how heap sort processes the input 142, 543, 123, 65, 453, 879, 572, 434, 111, 242, 811, 102.
3. Write algorithm for binary search, discuss with example.
4. Write the algorithm to perform Shell Sort with example.
5. Write the routine to implement merge sort. Perform the merge sort for the subsequent list of elements: 24,13,26,1,2,27,38,15.
6. Write the routine to implement Quick Sort and discuss with an example.
7. Write the routine to implement Polyphase Sorting.
8. Write the routine to implement Multiway Merge Sorting.
9. Write the algorithm to perform Heap Sort and discuss with example.
10. Explain about Linear Probing and Quadratic probing techniques used in Hashing Techniques
11. Explain about Linear Probing and Double Hashing techniques used in Hashing Techniques






UNIT IV
1. What is a Graph ADT?
2. Define the following:’path’, ‘simple path’, ‘cycle’, ‘connected graph’, ‘complete graph’.
3. What are the 2 ways of representing graphs?
4. List the techniques used in reducing the running time of Dijkstra’s algorithm.
5. What is meant by negative edge cost?
6. What is DAG?
7. Write an algorithm to perform Depth 1st Search in an undirected graph.
8. What is meant by Minimum Spanning Tree?
9. Define depth 1st search.
10. Describe the subsequent
a. Class NP
b. NP Complete issues

PART B
1. Describe the implementation of Dijkstra’s algorithm with an example.
2. Describe the Prim’s algorithm for finding the minimum spanning tree in an undirected graph and analyze its running time.
3. Describe the Kruskal’s algorithm for finding the minimum spanning tree in an undirected graph and analyze its running time.
4. What is an Euler circuit? discuss the procedure to obtain an Euler circuit in an undirected graph with an example.
5. Describe how to solve the ‘Traveling Salesperson’ issue with example.
6. Explain about the applications of Depth 1st Search.
7. Explain about Network Flow issue.

UNIT V
PART A

1. What is a Greedy Algorithmic Technique?
2. Write notes on Huffman Codes.
3. Describe the on-line algorithms used in bin packing issue.
4. What are Randomized Algorithms?
5. What is Backtracking Technique?

PART B

1. Describe how greedy algorithm can be used in solving scheduling issue.
2. Describe the off-line algorithms used in bin packing issue.
3. What is dynamic programming? discuss with an example.
4. Explain the divide and conquer technique.




5. a.A file contains only colons, newlines, commas and digits in the subsequent frequency: colon(100), space(605), new line(100), comma(705), 0(431), 1(242), 2(176), 3(59), 4(185), 5(250), 6(174), 7(199), 8(205), 9(217).Discuss a Greedy algorithm to compress the file.
6. Describe in detail how greedy algorithms can be used in the Selection issue.
7. What are Randomized Algorithms? Write notes on Random number generators.
8. Explain about Backtracking algorithm with example.

Earning:   Approval pending.