$1$ Derive the asymptotic bound for the recurrences.

a$.T(n)=6T(\frac{n}{3})+n$

b$.,T(n)=4T(\frac{n}{2})+n^2$

$2$ Prove that the amortized cost of Fibonacci Heap Union operation is equal to its

$(5)$

actual cost.

$3$ Find the maximum bipartite matching of the graph G $($LUR$,$ E$).$ where $L=\{a,b,c,d,e\},R=\{w,x,y,z\}$ and $.(e,y)\text{'}$

$4$ Apply Miller Rabin algorithm to test whether $127$ is prime or not.

$5$ Design an approximation algorithm to find the vertex cover of a graph. Derive the approximation ratio $c,$ of the algorithm.