Homework 3 Find a Longest Comment Subsequence

Homework 3

1. (20 points.) Find a Longest Comment Subsequence (LCS) of x = < 1, 0, 0, 1, 0, 1, 0, 1> and
y = <0, 1, 0, 1, 1, 0, 1, 1, 0>
2. (20 points.) According to the following adjacency list (Fig.1), draw the corresponding
directed graph.
3. (20 points.) According to the following adjacency matrix (Fig.2), draw the
corresponding undirected graph.

Fig.1 Fig.2
4. Given the following undirected graph.
(1) (20 points.) Draw the Depth First Search (DFS) trees corresponding to this graph.
(2) (20 points.) Draw the Breath First Search (BFS) trees corresponding to this graph.