Algorithm Design and Analysis Assignment 2

    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