CSOR-W4231 Homework 2 Solution

Homework Instructions.
1. For all algorithms that you are asked to “give” or “design”, you must do all of the following to get full credit:
(a) Describe your algorithm clearly in English.
(b) Give pseudocode.
(c) Argue correctness, even if you don’t give a formal proof and give a convincing argument instead. (d) Give with an explanation the best upper bound that you can for the running time.
2. You should submit your assignment as a pdf file to Gradescope. Other file formats will not be graded, and will automatically receive a score of 0.
3. I recommend you type your solutions using LaTeX. For every assignment, you will earn 5 extra credit points if you type your solutions using LaTeX or other software that prints equations and algorithms neatly. If you do not type your solutions, make sure that your hand-writing is very clear and that your scan is high quality.
Homework Problems
One way of formalizing this intuition is the following. You are given an undirected graph G = (V,E), and two specific nodes s and t such that the distance between s and t is strictly greater than n/2, where n = |V |. Give an efficient algorithm that, on input (G = (V,E),s,t), returns a node v different from both s and t such that deleting v from G destroys all s-t paths.
2. (30 points) You are given a directed graph G = (V,E). Design an efficient algorithm that outputs yes if G has an odd-length cycle, and no otherwise.
Hint: First solve the problem assuming that the graph is strongly connected.
3. (45 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.
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 in terms of n = max{X,Y }. If it is not possible to achieve this goal, return ”impossible” in your pseudo-code.
4. (40 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.
• Recall that the implication clause (α ⇒ β) is a shorthand notation for the clause (¬α∨β). Therefore, 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.
Prove the claim “φ is satisfiable if and only if no strongly connected component of Gφ contains both a variable x and its negation ¬x”. Then conclude that there is a linear-time algorithm for solving 2SAT, that is, an algorithm that, on input a 2SAT formula φ, returns a satisfying truth assignment for φ if φ is satisfiable, or no if φ is unsatisfiable.
Hint: Prove each direction of the claim separately.
First, prove the forward direction by proving the contrapositive statement, that is, if Gφ has a strongly connected component containing both a variable x and its negation ¬x, then φ is not satisfiable.
Then show the reverse direction of the claim, that is, if no strongly connected component of Gφ contains both a variable x and its negation ¬x, then φ is satisfiable. To prove this, it suffices to exhibit a satisfying truth assignment for φ. To construct that assignment, consider the following idea: Consider the meta-graph of SCCs of Gφ. Find a sink SCC and assign the truth value 1 to all the literals in it; remove it and recurse.
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).
2. 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.