Question 1. Consider the following algorithm:
ALGORITHM DFS(G)
//Input: Graph G = (V, E)
mark each vertex in V with 0 as a mark of being "unvisited"
count ← 0
for each vertex v in V do
if v is marked with 0
dfs (v)
dfs (v)
count ← count + 1; mark v with count
for each vertex w in V adjacent to v do if w is marked with 0 dfs(w)
(a) Implement the DFS algorithm to the graph in Figure 1 by starting at vertex A and resolving ties by the vertex alphabetical order and trace the values of the variables of the algorithm in the following table.
(b) Construct the corresponding DSF tree for the graph in Figure 1, and classify all the edges of the above DSF tree into four types: (1) tree edge, (2) back edge, (3) forward edge, and (4) cross edge.
(c) Write down the adjacency matrix for the graph in Figure 1.
Question 2. Consider the following algorithm:
ALGORITHM: BruteForceStringMatch (T [0..n-1], P [0..m-1])
// Input: An text array T [0..n - 1] of n characters and an pattern array P [0..m-1] of m characters
for i ← 0 to n-m do
j ← 0
while j < m and P[ j ] = T [ i + j ] do
j ← j + 1
if j = m then return i
return -1
(a) Search the pattern (P = W X Y Z ) in the text (T = W X W X Y Z W X W X ) by the Brute Force String Match algorithm, and record the values of the parameters of this algorithm in the following table.
(b) How many Comparisons (both successful and unsuccessful) are made by the brute-force string-matching algorithm in search for the pattern 000100010001 in the binary text of four hundred zeros?
Question 3. Given 4 items of known weights w1, w2, w3, w4, and values v1, v2, v3, v4 as shown in Table 3-1and a knapsack of capacity W = 18 Kg, find the most valuable subset of the items that fit into the knapsack by exhaustive search.
|
Item
|
Weight (Kg)
|
Value
|
|
A
|
8
|
13
|
|
B
|
4
|
16
|
|
C
|
11
|
21
|
|
D
|
5
|
9
|
You must show your work to receive credit. A correct answer without showing your reasoning process will not receive credit.