Homework 3

Due Wednesday, February 11

1. For a given graph $G = (V, E)$ and an edge $e \in E$, design an $O(n + m)$-time algorithm to find, if it exists, the shortest cycle that contains $e$.

2. (a) Prove that every connected graph $G = (V, E)$ has a node $v \in V$ such that removing $v$ and all its adjacent edges will not disconnect $G$.

   (b) For a given connected graph $G = (V, E)$, design an $O(n + m)$-time algorithm to find such a node.

3. A company in Slovakia manufactures blue halogen bulbs for cars. Unfortunately, it is very difficult to color bulbs consistently. Naturally, it is also very important to package bulbs that look alike in pairs. To package bulbs in pairs, bulbs coming out of the assembly line are first partitioned into two sets of bulbs sharing similar colors (e.g., one set of darker bulbs, another set of lighter bulbs), and then pairs are formed within each set.

   Because of increasing demand, the company wishes to hire more workers to partition bulbs into two sets. To determine whether applicants have appropriate skills to perform this rather delicate task, they are asked to take this simple test: Given a set of $n$ bulbs, compare each pair of bulbs and determine whether two bulbs have “similar” or “different” colors. An applicant also has an option to say “indeterminate” for each pair. The company wishes to hire applicants who are consistent in their judgment. We say $m$ judgments (resulted in either “similar” or “different”) are consistent if it is possible to partition $n$ bulbs into two sets such that (i) for each pair $\{ a, b \}$ determined to be “similar”, $a$ and $b$ indeed belong to the same set, and (ii) for each pair $\{ a, b \}$ determined to be “different”, $a$ and $b$ indeed belong to different sets.

   For a given test result for $n$ bulbs with $m$ judgments, design an $O(n + m)$-time algorithm to determine whether the judgments are consistent. In practice, there should be a minimum number of judgments applicants are required to make, but your algorithm should work for any integer $m \ge 0$.

CPSC 320 home page