Homework Policy

● If you leave a question completely blank, you will receive 25% of the grade for that question.  This however does not apply to the extra credit questions.

● You may also consult all the materials used in this course (lecture notes, textbook, slides, etc.) while writing your solution, but no other resources are allowed.

● Unless specified otherwise, you may use any algorithm covered in class as a “black box” – for example you can simply write “use Dijsktra’s algorithm to find a shortest path from a vertex s to a vertex t in the input graph in O(n + m log m) time” .

You are strongly encouraged to use graph reductions instead of designing an algorithm from scratch whenever possible (even when the question does not ask you to do so explicitly).

● Remember to always prove the correctness of your algorithms and analyze their running time (or any other efficiency measure asked in the question).

● The  “Challenge yourself”  and  “Fun with  algorithms”  are both extra  credit.   These problems  are significantly more challenging than the standard problems you see in this course (including lectures, homeworks, and exams). As a general rule, only attempt to solve these problems if you enjoy them.

●  Groups: You are allowed to form groups of size two or three students for solving each homework (you can also opt to do it alone if you prefer). The policy regarding groups is as follows:

– You can pick different partners for different assignments (e.g., from HW1 to HW2) but for any single assignment (e.g., HW1), you have to use the same partners for all questions.

– The members of each group only need to write down and submit a single assignment between them, and all of them will receive the same grade.

– For submissions, only one member of the group submits the full solutions on Canvas and lists the name of their partners in the group. The other members of the group also need to submit a PDF on Canvas that contains only a single line, stating the name of their partner who has submitted the full solution on Canvas (Example:  Say A, B, and C are in one group; A submits the whole assignment and writes down the names A, B, and C . B and C only submit a one-page PDF with a single line that says “See the solution of A”).

– You are allowed to discuss the questions with any of your classmates even if they are not in your group. But each group must write their solutions independently.

● Extensions: All the students in a group can decide to use an extension and submit their homework up to two days after the original deadline (you do not need to ask permission for using an extension; there is no penalty for using one, nor any bonus credit for not using them). In this case, all members of the group lose one of their extensions. Since the group members can change during the semester, to ensure fairness, as long as there is even one member of the group who has used less than two extensions, the entire group is allowed to use an extension (this means that some students may end up having used more than two extensions throughout the semester, but that is okay).

Problem 1. You are given a weighted undirected graph G = (V, E) with integer weights we  ∈ {1, 2, . . . , W } on each edge e, where W ≤ 25. Given two vertices s, t ∈ V , the goal is to find the minimum weight path (or shortest path) from s to t. Recall that Dijkstra’s algorithm solves this problem in O(n + m log m) time even if we do not have the condition that W ≤ 25.  However, we now want to use this extra condition to design an even faster algorithm.

Design and analyze an algorithm to find the minimum weight (shortest) s-t path on these restricted weighted

graphs in O(n + m) time.                                                                                                                  (40 points)

Problem 2. Prove that each of the following problems is NP-hard and for each problem determine whether it is also NP-complete or not (you do not need to prove NP-completeness).

(a)  Minus-One 3-SAT Problem: Given a 3-CNF formula Φ with m clauses and n variables (in which

size of each clause is at most  3), is there an assignment to the variables that satisfies exactly m − 1 clauses, namely, all minus one of them?                                                                                  (30 points)

(b)  Negative-Weight Shortest Path Problem:  Given an undirected graph G = (V, E), two vertices

s, t and negative weights on the edges, what is the weight of the shortest path from s to t? (30 points)

You may assume the following problems are NP-hard for your reductions:

● Undirected s-t Hamiltonian Path: Given an undirected graph G = (V, E) and two vertices s, t ∈ V , is there a Hamiltonian path from s to t in G? (A Hamiltonian path is a path that passes every vertex).

● 3-SAT Problem: Given a 3-CNF formula Φ (where each clause as at most 3 variables), is there an assignment to Φ that makes it true?

Fun with Algorithms. You are given a puzzle consists of an m × n grid of squares, where each square can be empty, occupied by a red stone, or occupied by a blue stone.  The goal of the puzzle is to remove some of the given stones so that the remaining stones satisfy two conditions:  (1) every row contains at least one stone, and (2) no column contains stones of both colors.

It is easy to see that for some initial configurations of stones, reaching this goal is impossible. We define the Puzzle problem as follows. Given an initial configuration of red and blue stones on an m × n grid of squares, determine whether or not the puzzle instance has a feasible solution.

Prove that the Puzzle problem is NP-complete.   (+10 points)

Consider solving at most one of the following two challenge yourself problems.