Instructions:
1. This is an individual assignment. You should do your own work. Any evidence of copying will result in a zero grade and additional penalties/actions.
2. Late submissions will not be accepted unless prior permission has been granted or there is a valid and verifiable excuse.
3. Think carefully; formulate your answers, and then write them out concisely using English, logic, mathematics and pseudocode (no programming language syntax).
4. Type your final answers in this Word document.
5. Don’t turn in handwritten answers with scribbling, cross-outs, erasures, etc. If an answer is unreadable, it will earn zero points. Neatly and cleanly handwritten submissions are acceptable.
1. (15 points) Show d and π values that result from running Breadth First Search on the directed graph below using vertex 3 as the start node.
d=
d=
π =
d=
π =
1
2
3
• =
d=
4
5
6
π =
d=
d=
π =
π =
2. (10 points) Show how Depth First Search works on the graph below by marking on the graph the discovery and finishing times (d and f) for each vertex and the classification of each edge. Assume that the for loops in DFS and DFS-VISIT consider vertices alphabetically.
q
r
s
t
y
u
v
w
x
3. (15 points) List the vertices of the graph below in Topological Order, as produced by the Topological Sort algorithm. Assume that the for loops in DFS and DFS-VISIT consider vertices alphabetically.
m n o p
q
r
s
t
u
v
w
x y z
4. (15 points) Do Problem 24.1-1 (p. 654) (you do not have to do the last part, i.e., running the algorithm again after changing an edge weight).
5. (15 points) Do Problem 24.2-1 (p. 657). Show the results similar to Fig. 24.5.
6. (20 points) Do Problem 24.3-1 (p. 662).
(7) (10 points) Suppose that a graph G has a Minimum Spanning Tree (MST) computed. How quickly can we update the MST if we add a new vertex and incident edges to G. Propose and outline a strategy and present an algorithm (you can reuse graph algorithms covered in class as building blocks as part of your solution) and evaluate its asymptotic complexity.
