1)(i) Derive the ADT to execute insertion and deletion in the singly linked list.
(ii) Describe cursor implementation of linked lists. Write down the necessary operations.
2)(i) Write down an ADT to execute stack of size N using an array. The elements in the stack are to be integers. The operations to be supported are PUSH, POP and DISPLAY. Take into account the exceptions of stack overflow and stack underflow.
(ii) Circular queue has the size of 5 and has 3 elements 10, 20 and 40 where F = 2 and R = 4. After inserting 50 and 60, find is the value of F and R. Trying to insert 30 at this stage what happens? Delete two elements from queue and insert 70, 80 & 90. Illustrate the sequence of steps with essential diagrams with the value of F & R
3)(i) Write down an ADT to construct an AVL tree.
(ii) Assume the following sequences list nodes of a binary tree T in preorder and inorder, respectively:
Preorder: A, B, D, C, E, G, F, H,J
Inorder: D, B, A, E, G, C, H, F, J
Design the diagram of the tree.
4)(i) Write down an ADT for performing insert and delete operations in a Binary Search Tree.
(ii) Explain in detail binary heaps. Construct a min heap tree for the following:
5, 2, 6,7, 1, 3, 8, 9, 4
5)(i) Create the ADT to execute separate chaining hashing scheme.
(ii) Illustrate the result of inserting the keys 2, 3, 5, 7, 11, 13, 15, 6, 4 into the initially empty extendible hashing data structure with M = 3.
6) (i) Create an ADT to perform for the Union and find operations of disjoint sets.
(ii) Explain about Union-by-rank and determine with path compression with code.
7) (i) Write routines to determine shortest path using Dijkstra’s algorithm.
(ii) Determine all articulation points in the below graph. Illustrate the depth first spanning tree and the values of DFN and Low for each vertex.
8)(i) Write down the pseudo code to determine a minimum spanning tree using Kruskal’s algorithm.
(ii) Determine the topological ordering of the below graph.
9)(i) Describe the running time of Divide-and-Conquer merge sort algorithm.
(ii) Describe the concept of greedy algorithm with Huffman codes example.
10) Describe the Dynamic Programming with suitable example.