Q.1. (a) Write a program to implement a Tree using array. Also, write an algorithm for inserting and deleting items in a tree.
(b) What are AA-trees ? Explain their properties and operations with the help of suitable example.
(c) Write the algorithm to evaluate an expression consisting of (+, -, *,%) binary operations using stack.
(d) Write the algorithm for addition of two polynomials of order n and m, where n < m.
2. (a) Consider the matrix A
[5 8 7]
[3 2 0]
[4 3 8]
(i) Write the steps involved in calculating the rank of A.
(ii) Write an algorithm to find the transpose of A.
(b) Write a program that accepts a Binary Search Tree (BST) and a key value as input and outputs a message indicating whether the key is found in BST or not.
3. (a) Using Dijkstra's algorithm find the path between A and F for the following graph. Show the intermediate steps also
(b) Define a multiple stack. Write algorithm for its imlementation.
4. (a) (i) Prove that height h of a complete binary tree with n nodes is h = log2(n+1)
(ii) Wriote algorithm for non-recursive in-order binary tree traversal. (5)
(b) Define Prim's algorithm. Write the steps to find minimum spanning tree using example graph.