$1.$ Given a digraph G $=($V$,$ E$),$ its transitive closure G$$ is a digraph defined as follows: It has the same vertex set V as G and contains an edge from a vertex a to another vertex b if and only if there is a directed path from a to b in G$.$ Suppose we want to design a DP algorithm that outputs G$$ on input G$.$ Design the subinstances and the Bellman Equation. $($Note that though this is not an optimization problem, DP is still helpful.$)$

$2.$ Compute the shortest path from vertex $2$ to every other vertex of the attached graph using the Bellman$-$Ford Algorithm. Show your work by constructing the table as in Slide $13$ of Lecture $19.$

$3.$ Compute the length of longest common subsequence for the two input strings x $=$ ABCBDAB and y $=$ BDCABA using the dynamic programming algorithm on Slide $11$ of Lecture $20.$ Show your work by filling the DP table.