CS 610留学生代做、代写DFS algorithm、代做Java，Python代写、代写c++程序

日期：2019-04-24 11:00

Assignment 6 (85 points)

CS 610 Spring 2019

Due : Apr.24,2019 in class

Problem 1. (7 points)

How will you modify the DFS biconnectivity algorithm discussed in class so

that we can output edges of each biconnected component ?

Hint: Keep both tree and back edges on stack and think about when to pop

them from stack as part of a biconnected component.

Problem 2. (15 points)

Apply the biconnectivity algorithm discussed in class to the undirected graph

shown in Figure 6.8 of the text book to identify the separation vertices. Your

search should start from vertex A. Assume the adjacent list of each vertex

contains vertices in alphabetical order. For example for vertex M, the adjacency

list has vertices A, B and C in that order. You need to show the DFS tree

showing both tree and back edges and also DF, LOW values for each vertex.

Problem 3. (10 points)

For the following weighted graph, produce minimimum cost spanning tree

(MST) using Prim-Jarn`?k’s algorithm showing all intermediate steps. Your

algorithm should start from vertex a.

1

Problem 4. (10 points)

Repeat the above problem except that you need to use Kruskal’s algorithm for

MST.

2

Problem 5. (10 points)

(a) Show how to modify Dijkstra’s algorithm to not only output the distance

from a vertex s to each vertex in G but also to output a spanning tree

T rooted at s such that the path in T from s to a vertex u is actually a

shortest path in G from v to u. Your output of the tree should be some

thing like ”v1 has shortest distance d and v2 is parent of v1 ”. (5 points)

(b) Do additional modification so that if there are more than one shortest path

from s to u, we output the one with shortest number of edges.(5 points)

Problem 6. (18 points)

Let G = (V, E) be a directed graph where each edge has a probability value

associated with it given by the function p : E? > [0, 1]. Assume there are no

self-cycles in this graph. The reliability of a directed path P = (e1, e2, ...ek)

from vertex u to vertex v given by R(P) = Qk

i=1 p(ei) is the product of probabilities

of edges in the path. All-pairs Max Reliablity Problem is one of finding

for each pair of vertices u and v, the maximum reliability among all paths from

u to v.

(a) Define a proper closed semi-ring for this all-pairs problem and prove it is a

closed semi-ring.(7 pts)

(b) Modify Warshall-Floyd algorithm to solve this problem using proper semiring

operations.Your algorithm should also find for each pair of vertices the

actual path that achieves maximum reliability.(8 pts)

(c) Estimate the time complexity of this algorithm specifying exactly the primitive

operations being measured.(3 pts)

Problem 7. (15 points) Problem R-8.4 from the text book. Show all the

different steps of the algorithm and also the miniumum cut.

3