Implement the dfs algorithm to the graph

Assignment Help Data Structure & Algorithms

Reference no: EM131679589

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.

Count

Vertex

Stack

(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.

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 w₁, w₂, w₃, w₄, and values v₁, v₂, v_3, v₄ 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.

Reference no: EM131679589

Questions Cloud

Analyze information about the hospital from its website : Identify hospital in your area to research that interest you. Analyze information about hospital from its website, annual report and other source that you find.

Write a function that removes all duplicates in an array : Write a function that removes all duplicates in an array A of N items. Return the number of items that remain in A.

Essential for people with celiac disease : Gluten-free diets are essential for people with celiac disease, but a gluten-free diet has also been promoted for weight loss.

Discuss defense to assault with intent to commit rape : Now use the same defense and apply it to assault with intent to commit rape. How would you defend your client using this strategy

Implement the dfs algorithm to the graph : Implement the DFS algorithm to the graph in Figure by starting at vertex A and resolving ties by the vertex alphabetical order and trace the values

What are your conclusions after reviewing the data : What are your conclusions after reviewing the data? Prepare a bar graph that displays the number of patients by age of diagnosis.

Write a simple sorting utility and sort : Write a simple sorting utility, sort. The sort command takes a file name as a parameter, and the file contains one item per line.

Choices can help reduce the risk of heart disease : Day-to-day choices can help reduce the risk of heart disease. One of the major risk factors for the development of heart disease

Explain types of outcomes and effects on employee motivation : Explain the types of outcomes and the effects on employee motivation toward doing the job duties being targeted in the training.

User Account

All Pages