Description

Instructions:
2. Think carefully; formulate your answers, and then write them out concisely using English, logic, mathematics and pseudocode (no programming language syntax).
3. Type your final answers in this Word document.
4. 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.

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.

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.

Topological Order: p, n, o, s, m, r, y, v, x, w, z, u, q, t

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

From the textbook:

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.

My strategy is to use Prim’s algorithm, but to keep track of the previous vertices/edges and any new vertices/edges. Look at the new edges and remove the max weight edge. For the priority queue, the edges that are being added are from the new edges.

Asymptotic complexity = O(E)