Description
Homework Problems
1. (25 points) There is a natural intuition that, if two nodes are “far apart” in a communication
network, they may become disconnected more easily. One way of formalizing this intuition
is the following. You are given an undirected graph G = (V, E) with n vertices and m edges
that contains two nodes s and t such that the distance between s and t is strictly greater
than n/2. Give an efficient algorithm that returns a node v different from both s and t such
that deleting v from G destroys all s-t paths.
2. (25 points) Give an efficient algorithm that takes as input a directed graph G = (V, E) and
determines whether or not there is a vertex s ∈ V from which all other vertices in the graph
are reachable. Assume |V | = n, |E| = m.
3. (25 points) Give an efficient algorithm that takes as input a directed acyclic graph G = (V, E)
and two vertices s, t ∈ V , and outputs the number of different paths from s to t in G. Assume
|V | = n, |E| = m.
4. (35 points) You are given two bottles with capacities X and Y liters, respectively.
Initially, there are x liters of water in the first bottle, and y liters of water in the second
bottle, where 0 ≤ x ≤ X and 0 ≤ y ≤ Y .
At each step, you can perform one of the three operations below:
– FILLUP(i). Fill up bottle i with tap water.
– EMPTY(i). Pour all the water from bottle i to the drain.
– POUR(i, j). Pour the water from bottle i to bottle j. After this operation, either
bottle i is empty or bottle j is full while there may be some water left in bottle i.
Your goal is to end up with exactly A liters of water in one of the two bottles, for some
A ≤ max{X, Y }.
Design an algorithm that, on input X, Y, x, y, A, achieves this goal by using the smallest
number of operations, and returns that number. If it is not possible to achieve this goal,
return ”impossible” in your pseudo-code.
5. (35 points) In this problem, you will design a linear-time algorithm for 2SAT.
Consider a CNF formula φ with m clauses and n variables such that every clause consists of
2 literals. Given φ, construct a directed graph Gφ = (V, E) as follows:
• Gφ has 2n nodes, one for each variable and its negation;
• Note that a clause (x∨y) is equivalent to either of the implications (¬x ⇒ y) or (¬y ⇒ x).
Introduce all these implications as edges of Gφ: for every clause (x∨y) add one directed
edge from ¬x to y and one directed edge from ¬y to x.
Show that φ is satisfiable if and only if there is no strongly connected component of Gφ that
contains both a variable x and its negation ¬x. Then conclude that there is a linear-time
algorithm for solving 2SAT.
Hint: First show that if Gφ has a strongly connected component containing both a variable x
and its negation ¬x, then φ is not satisfiable. Then show the converse of this statement, (that
is, if no strongly connected component of Gφ contains both a variable x and its negation ¬x,
then φ is satisfiable) by exhibiting an appropriate satisfying truth assignment for φ.
RECOMMENDED EXERCISES (do NOT submit, they will not be graded)
1. Problem 22-2, parts a, b, c, d, e and f, in your textbook (p. 622).
