$[20$ pts$]$ Find a Longest Common Subsequence $($LCS$)$ of X $=$ abcbd and Y $=$ acad by

constructing a cost table.

$2)[20$ pts$]$ Show how breadth$-$first search works on the graph shown in the figure above

assuming we start the BFS from the vertex r$.$ Provide the BFS tree.

$3)[20$ pts$]$ Show how depth$-$first search works on the graph shown in the figure above

assuming we start the DFS from the vertex r$.$

$4)[20$ pts$]$ Show how Kruskal$$s algorithm works on the graph shown in the figure above.

$5)[20$ pts$]$ Show how Prim$$s algorithm works on the graph shown in the figure above

assuming we start from the