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".

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$)$ Compare and contrast dynamic programming and greedy algorithms.

b$)$ Explain the greedy choice behind construction of a Huffman tree. Apply a

greedy procedure for building a Huffman tree with $6$ symbols $a,b,c,d,e,f$

having respective frequencies $($in thousands$)$ as $30,10,20,15,13,12.$

c$)$ Grow a breadth$-$first tree in the following graph with root node as $\text{'}$b$\text{'}.$ Analyze

the complexity of your solution.