a$)$ Define a height baianced binary search tree.

b$)$ Show that the binary search tree constructed with nodes as $8,6,10,4,7,9,11,$

$3,5,2$ is not height$-$balanced. You should first show the step$-$by$-$step

construction of the tree taking the first data as the root.

c$)$ Apply appropriate AVL rotation on the tree in $($b$).$ Verify that the rotation

indeed achieves the desired result.

d$)$ Prove or disprove: A complete graph is always connected.Give brief answers to the following questions:

a$)$ Write a pseudocode for inserting an element into the front of a list.

b$)$ Differentiate between a queue and a priority queue.

c$)$ Prove or disprove: $3n^2+4n^{2}logn+5n+2=O(n^{3}logn).$

d$)$ Given: $T(n)=T(\frac{3n}{4})+1.$ Find the tight asymptotic bound for $T(n).$

e$)$ Show the bounds for number of nodes of an almost complete binary tree of

depth $d.$

f$)$ Prove or disprove: Number of edges in $K_n$ is less than the number of edges in

$K_{n,n}.$

g$)$ Find the complexity of the Merge Sort algorithm.

h$)$ What is meant by hash collision?

i$)$ Explain whether dynamic programming is the most suitable approach to solve

the Fractional Knapsack problem.

j$)$ State the shortest path problem in a weighted directed graph.

a$)$ Define a stack.

b$)$ Clearly explain how you can use a stack for reversing a string. Show linked

implementation of the two basic operations you will need for achieving the

above task.

c$)$ Explain how a stack can be used to solve the Towers of Hanoi problem. Trace

the recursive solution for the above problem with $4$ discs.