For the graded problems, you are allowed to use the algorithms from class as black-boxes without further explanation. These include

DFS (outputs connected components, a path between two vertices, topological sort on a DAG. You also have access to the pre and post arrays!), BFS and the Explore subroutine.

Dijkstras algorithm to find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the pre labels.

Bellman-Ford and Floyd-Warshall to compute the shortest path when weights are allowed to be negative.

SCCs which outputs the strongly connected components, and the metagraph of connected components.

Kruskals and Prims algorithms to find MST.

Ford-Fulkerson and Edmonds-Karp to find max flow on networks.

When using a black-box, make sure you clearly describe which input you are passing to it and how you use the output from or take advantage of the data structures created by the algorithm. To receive full credit, your solution must:

Include the description of your algorithm in words (no pseudocode!).

Explain the correctness of your design.

State and analyse the running time of your design (you can cite and use the running time of black-boxes without further explanations).

Unless otherwise indicated, black-box graph algorithms should be used without modification.

Example: I take the input graph G, I first find the vertex with largest degree, call it v*. I take the complement of the graph G, call it G'. Run Dijkstras algorithm on G' with s = v* and then I get the array dist[v] of the shortest path lengths from s to every other vertex in the graph G'. I square each of these distances and return this new array.

We dont want you to go into the details of these algorithms and tinker with it, just use it as a black-box as showed with Dijkstras algorithm above.

Problem:

Let G=(V,E) be an undirected graph, and let s and t be distinct vertices of G. Each edge in G is assigned one of two colors, white or gold.

(a) Design an algorithm that determines if there is a path from s to t with edges of only one color (that is, a path containing either white edges only or gold edges only).

(b) Design an algorithm that determines if there is a path from s to t such that all white edges appear before all gold edges in the path.