a$)$ Shortest Common Supersequence $($SCS$)$ of strings $x[1,$dots,$m]$ and $Y[1,$dots,$n]$

is the shortest string $Z[1,$dots,$p]$ such that both $x$ and $Y$ are subsequences of $Z.$

For example, if $x="$AB$"$ and $Y="BC",$ then $Z=SCS(x,Y)="$ ABC $"$ and

length of $Z$ is $3.$ Find a dynamic programming based solution to the SCS

problem. Apply your solution to find the length of a SCS of strings "ABCDGH"

and "AEDFHR".

b$)$ Apply depth$-$first search on the following directed graph with starting node as

$\text{'}$a$\text{'}.$ Show the nested parenthesis structure based on timestamps. a$)$ Prove that for any two functions $f(n)$ and $g(n),f(n)=(g(n))$ if and only if

$f(n)=O(g(n))$ and $f(n)=(g(n)).$

b$)$ Find the solution to the recurrence relation $T(n)=4T(\frac{n}{2})+n$ using the

recursion tree approach.

c$)$ Verify your solution in $($b$)$ using any alternative approach.

a$)$ Write a recursive procedure for the Quick Sort algorithm including a separate

code for the partition process.

b$)$ Apply the algorithm in $($a$)$ to sort the dataset $25,57,48,37,12,92,86$ in the

ascending order. Analyze the time$-$complexity of your solution.

c$)$ Compare the number of operations necessary to check whether the key$=86$ is

present in the given dataset using two different search techniques.