Assignment 3
CMPT307
Assignment 3
4 problems, 40 points.
** For questions 1, 3, and 4, please describe your algorithm in pseudocode,
then use several sentences to explain your idea.
1. Describe an algorithm to compute the reversal (also called transpose)
rev(G) of a directed graph in O(V + E) time. (10 points)
2. Given a directed graph G. Let v denote a vetex of G, and S(v) be the
strong component of G that contains v. For two arbitrary vertices u, v ∈
G, prove that u can reach v if and only if S(u) can reach S(v) in scc(G).
(10 points)
3. Given an undirected graph G with weighted edges and a minimum spanning tree T of G, describe an algorithm (use pseudocode) to update the
minimum spanning tree T when the weight of a single edge e is increased.
The input to your algorithm is the edge e and its new weight value. You
shold modify the spanning tree T so that it is still a minimum spanning
tree. (10 points)
Hint: Consider the cases e ∈ T and e 6∈ T separately.
4. Given a directed graph G with weighted edges, describe an algorithm to
find the shortest path from one vertex s to another vertex t. There is
exactly one edge in G that is with negative weight. (10 points)
Hint: Consider modifying Dijkstra’s algorithm. Of course other ideas
could also be great.
1
