1. (20 points) Here is a proposal to nd the length of the shortest cycle in an unweighted undirected graph:
DFS the graph, when there is a back edge (v; u), it forms a cycle from u to v, and the length is level[v] level[u] + 1, where the level of a vertex is its distance in the DFS tree from the root. This suggests the following algorithm:
◦ Do a DFS and keep tracking the level.
◦ Each time we nd a back edge, compute the cycle length, and update the smallest length.
Please justify the correctness of the algorithm, prove it or provide a counterexample.
2. (20 points) Given a directed graph G = (V; E) on which each edge (u; v) 2 E has a weight p(u; v) in range [0; 1], that represents the reliability. We can view each edge as a channel, and p(u; v) is the probability that the channel from u to v will not fail. We assume all these probabilities are independent. Give an e cient algorithm to nd the most reliable path from two given vertices s and t. Hint: it makes a path failed if any channel on the path fails, and we want to nd a path with minimized failure probability.
3. (20 points) We have a connected undirected graph G = (V; E), and a speci c vertex u 2 V . Suppose we compute a depth- rst search tree rooted at u, and obtain a T that includes all nodes of G. Suppose we then compute a breath- rst search tree rooted at u, and obtain the same tree T . Prove that G = T . (In other words, if T is both a DFS tree and a BFS tree rooted at u, then G cannot contain any edges that do not belong to T .)
Page 1 of 2
4. (20 points) Given a directed graph G(V; E) where each vertex can be viewed as a port.
Consider that you are a salesman, and you plan to travel the graph. Whenever you reach a port v, it earns you a pro t of pv dollars, and it cost you cuv if you travel from
u to v. For any directed cycle in the graph, we can de ne a pro t-to-cost ratio to be
r(C) =
P((u;v)
2C cuv :
u;v) C pv
P
2
As a salesman, you want to design an algorithm to nd the best cycle to travel with the largest pro t-to-cost ratio. Let r be the maximum pro t-to-cost ratio in the graph.
(a) (10 points) If we guess a ratio r, can we determine whether r > r or r < r e ciently?
(b) (10 points) Based the guessing approach, given a desired accuracy > 0, de-
sign an e cient algorithm to output a good-enough cycle, where r(C) r .
Justify the correctness and analyze the running time in terms of jV j, , and
R = max(u;v)2E(pu=cuv).
5. (20 points) Consider if we want to run Dijkstra on a bounded weight graph G = (V; E) such that each edge weight is integer and in the range from 1 to C, where C is a relatively small constant.
(a) (10 points) Show how to make Dijkstra run in O(CjV j + jEj).
(b) (10 points) Show how to make Dijkstra run in O(log C(jV j + jEj)). Hint: Can we use a binary heap with size C but not jV j?
6. How long does it take you to nish the assignment (include thinking and discussing)? Give a score (1,2,3,4,5) to the di culty. Do you have any collaborators? Write down their names here.
Page 2 of 2
