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)

673_figure.jpg

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

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

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.

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

  Implement an open hash table

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

  Use a search tree to find the solution

Explain how will use a search tree to find the solution.

  How to access virtualised applications through unicore

How to access virtualised applications through UNICORE

  Recursive tree algorithms

Write a recursive function to determine if a binary tree is a binary search tree.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Currency conversion development

Currency Conversion Development

  Cloud computing assignment

WSDL service that receives a request for a stock market quote and returns the quote

  Design a gui and implement tic tac toe game in java

Design a GUI and implement Tic Tac Toe game in java

  Recursive implementation of euclids algorithm

Write a recursive implementation of Euclid's algorithm for finding the greatest common divisor (GCD) of two integers

  Data structures for a single algorithm

Data structures for a single algorithm

  Write the selection sort algorithm

Write the selection sort algorithm

  Design of sample and hold amplifiers for 100 msps by using n

The report is divided into four main parts. The introduction about sample, hold amplifier and design, bootstrap switch design followed by simulation results.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd