1. Describe how we might use DFS to locate vertices in a graph who are not connected to any other vertex in the graph.
2. Suppose we use DFS on a binary search tree, starting with the root. The edge to a left child is always traversed before an edge to a right child. In what order are the vertices visited? In what order are the vertices finished?
3. An undirected graph contains a "cycle" (i.e., loop) if there are two different simple paths by which we can get from one vertex to another. Using breadth-first search (not DFS), how can we tell if an undirected graph contains a cycle?
4. Let ???? = ????1????2···???????? and ???? = ????1????2···???????? be two strings over the alphabet Σ={????,????,????,????}. A longest common subsequence (LCS) of X and Y can be found by dynamic programming. To compute ????[????; ????], where 1≤????≤???? and 1≤????≤????, how many table entries are examined in the worst case?
5. Calculate the minimum number of multiplications necessary to find the matrix product ABCDE.
The dimensions of each of the matrices are listed below:
Matrix Dimensions
A 2x4
B 4x3
C 3x2
D 2x5
E 5x1
A 2 dimensional grid is provided below.
|
|
A
|
B
|
C
|
D
|
E
|
|
A
|
0
|
|
|
|
|
|
B
|
X
|
0
|
|
|
|
|
C
|
X
|
X
|
0
|
|
|
|
D
|
X
|
X
|
X
|
0
|
|
|
E
|
X
|
X
|
X
|
X
|
0
|
6. A directed graph G has four vertices, A, B, C, and D and the adjacency matrix below:
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
7
|
-1
|
4
|
|
B
|
3
|
0
|
5
|
∞
|
|
C
|
∞
|
4
|
0
|
∞
|
|
D
|
∞
|
1
|
∞
|
0
|
Show the updates to the shortest path estimates when allowing just vertex A as an intermediate vertex in
Floyd-Warshall's algorithm. The non-trivial values have been left for you to fill in.
|
|
A
|
B
|
C
|
D
|
|
A
|
0
|
7
|
-1
|
4
|
|
B
|
3
|
0
|
|
|
|
C
|
∞
|
|
0
|
|
|
D
|
∞
|
|
|
0
|