UNIT IV

Part A

Two Mark Questions

1. Define Sorting

2. Differenciate Internal Sorting and External Sorting

3. Give examples for Internal Sorting and External Sorting

4. Sort the sequence 3, 4, 1, 5, 9, 2, 6 using insertion sort.

5. Write the routine for Insertion Sort.

6. What is diminishing Increment Sort?

7. What is the average number of comparison used to sort N

distinct items using Heap Sort.

8. Name the Sorting technique which uses divide and conquer

strategy.

9. What is the best case and average case analysis for quicksort?

10. What is the need for external sort?

11. Compare two - way merge and Multi - way Merge.

12. Write a note on polyphase merge.

13. What is the running time of heapsort for presorted input?

14. Determine the running time of mergesort for sorted input.

15. Sort 3, 4, 5, 9, 2, 6 using mergesort.

PART - B

1. Write down the shellsort algorithm Using this algorithm : trace

the following numbers.

10 9 5 6 4 8 2 7 1

2. Explain QuickSort algorithm : with an example

3. Write the procedure for HeapSort and trace the given numbers,

18 13 10 8 5 15

4. What is external sorting? Give an example for Multiway merge

and polyphase merging strategy with three tapes T1, T2 and T3.


UNIT - V

PART - A Questions

1. Define a graph

2. Compare directed graph and undirected graph

3. Define path, degree and cycle in a graph

4. What is an adjacency matrix?

5. Give the adjacency list for the following graph

6. Define Topological Sort

7. Define Shortest path problem. Give examples

8. Define Minimum Spanning Tree and write its properties.

9. What is DAG? Write its purpose

10. What are the different ways of traversing a graph?

11. What are the various applications of depth first search?

12. What is an articulation point?

13. When a graph is said to be binconnected?

14. Write down the recursive routine for depth first search.

15. Write a procedure to check the biconnectivity of the graph using

DFS.

16. Define Class_NP

17. What is meant by NP_Complete problem?

PART - B

1. What is Topological Sort? Write down the pseudocode to

perform topological sort and apply the same to the following graph.

2. Explain the Dijkstra's algorithm and find the shortest path from A

to all other vertices in the following graph.

3. Explain prim's algo/.. in detail and find the minimum spanning

tree for the following graph.


4. Find all the articulation points in the given graph. Show the

depth_first spanning tree and the values of Num and Low for

each vertex.