EECS 325 – Fall 2021
Analysis of Algorithms
Homework 4
Instructions:
• This homework is due by 11:59PM Pacific Time on Thursday, December 2nd. You have
a one-time grace period allowing you to submit a homework assignment up to two days late.
Subsequent assignments submitted up to two days late will incur a 20% penalty. Assignments
submitted more than two days late will not be graded and will receive a score of 0.
• You must submit your written solutions as a single .pdf file on Canvas with your name at the
top. Typesetting your written solutions using LATEX is strongly encouraged. If you solve the
extra credit part of Question 1 you must submit your solution as a single .cpp, .java, or .py
file depending on your choice of language.
• You are welcome and encouraged to discuss the problems in groups of up to three people, but
you must write up and submit your own solutions and code. You must also write the
names of everyone in your group on the top of your submission.
• The primary resources for this class are the lectures, lecture slides, the CLRS and Erickson
algorithms textbooks, the teaching staff, your (up to two) collaborators, and the class Piazza
forum. We strongly encourage you only to use these resources. If you do use another resource,
make sure to cite it and explain why you needed it.
• Scoring: 50 points with up to 5 points of extra credit.
Question 1 (Chomping logs, 12 points + 5 extra credit points). Filbert and Maple are beavers
at the Oregon Zoo. They are experts at chomping logs into pieces, and, realizing that there’s a
market for logs of a particular length, they decide to monetize their skills. In this problem you will
design an algorithm to help Filbert and Maple maximize their profit.
As input, you get an integer L ≥ 1 corresponding to the length of the starting log to be
chomped (in feet), and a table corresponding to the retail value v(i) of i-foot-long logs for each
integer 1 ≤ i ≤ L. The goal is to pick a number of pieces k satisfying 1 ≤ k ≤ L and integer lengths
`1, . . . , `k satisfying 1 ≤ `1 ≤ · · · ≤ `k ≤ L so that L =
∑k
i=1 `i (the sum of the lengths of the log
pieces is equal to the length of the original log) and the total retail value
∑k
i=1 v(i) is maximized
over all choices of k and `1, . . . , `k. The final output is the maximum possible total retail value∑k
i=1 v(i).
Consider the example in the following table:
a. (8 points) Design a tabulation-based dynamic programming algorithm for solving the “chomping
logs” problem. Give pseudocode for your algorithm and analyze its runtime. Clearly specify
what the dimensions of your table are, what each entry in the table represents, and how the
value of each in the table is computed.
(Hint: Suppose that you were given the value of `1. How could you use that to help solve the problem?)
1
Log length i (in feet) 1 2 3 4 5 6 7 8
Retail value v(i) (in dollars) 1 1 5 4 2 8 7 10
Table 1: An input table of log retail values v(i). If L = 8, then by picking k = 3, `1 = 1, `2 = 1, `3 =
6, we get that
∑k
i=1 `i = 1 + 1 + 6 = 8 = L, as required, and that the total retail value with these
choices is
∑k
i=1 v(`i) = v(1) + v(1) + v(6) = 1 + 1 + 8 = 10. Alternatively, we could have achieved
the same total value by picking k = 1, `1 = 8 for a total value of
∑1
i=1 v(`i) = v(`1) = v(8) = 10.
In part (b), you will analyze whether it’s possible to do better.
b. (4 points) Show the dynamic programming table produced by your algorithm from part (a) when
the starting log has length L = 8 and log retail values are as specified in Table 1. Also state the
final answer.
c. (5 points extra credit) Implement your algorithm from part (a). Your program should take a
file name as input. The file should contain the values v(1), . . . , v(L) in order from, separated by
single spaces (the values i in the top row of the input table and the value of L are implicit from
this information). Your program should output a single number corresponding to the maximum
possible total retail value.
For example, on input
4 8 3 8 9
corresponding to the values of v(1), v(2), v(3), v(4), v(5) your program should output
20
d. (0 points but highly recommended.) Watch videos of Filbert and Maple (https://www.youtube.
com/watch?v=6_idLrnt6vQ) and of Filbert in full log-chomping action (https://www.youtube.
com/watch?v=uWwtKXoQKZA).
Question 2 (3-SAT to Exact-3-SAT, 12 points). Recall that in class we defined 3-SAT as the
variant of CNF-SAT where each clause contains at most 3 literals (i.e., a clause may contain 1, 2,
or 3 literals). Define Exact-3-SAT to be the variant of CNF-SAT where each clause contains exactly
3 literals. Prove that Exact-3-SAT is NP-complete.
a. Prove that Exact-3-SAT is in NP.
(Hint: Give a polynomial-time verifier. Make sure to state what information is contained in the certifi-
cates that make it accept on YES instances. The verifier and certificates should be very similar to the
ones for 3-SAT.)
b. Give a polynomial time reduction from 3-SAT to Exact-3-SAT. Conclude that Exact-3-SAT is
NP-hard, and by part (a), also NP-complete.
(Hint: Start by thinking about the special case where the input CNF-SAT formula consists of just one
clause C. If C contains only one or two literals, show how to reduce it to an equisatisfiable Exact-3-SAT
formula (potentially containing new variables and more than one clause).)
2
Question 3 (Search-to-decision reduction for 3-SAT, 12 points). Suppose that you have a polynomial-
time algorithm D for deciding whether a 3-SAT formula Φ(x1, . . . , xn) on n variables is satisfiable.
Design a polynomial-time algorithm that, when given a satisfiable such formula Φ as input, uses D
as a “black-box” subroutine to find a Boolean assignment a1, . . . , an ∈ {0, 1} that satisfies Φ (i.e.,
an assignment so that Φ(a1, . . . , an) = 1).
1
(Hint: Note that D outputs one bit of information each time you query it. How many bits of information
does a satisfying assignment to Φ consist of?)
Question 4 (Guards and Streets, 14 points). The GuardsAndStreets Problem is the decision
problem defined as follows. As input, you are given a set of locations L = {`1, . . . , `n}, a set of
streets S = {s1, . . . , sm}, and a number k ≥ 0 as input. Each street s has exactly two distinct
locations `i and `j as its endpoints. Each location may be the endpoint of any number of streets,
and a guard can be stationed (or not) at each location. A street s ∈ S is called guarded if a guard
is stationed at at least one of its endpoints, and S is called totally guarded if each street s ∈ S is
guarded. The goal of the problem is to decide whether:
• (YES instances) It is possible to totally guard S using g ≤ k guards.
• (NO instances) To totally guard S, it is necessary to use g > k guards.
a. (4 points) Prove that the GuardsAndStreets Problem is in NP.
(Hint: Give a polynomial-time verifier. Make sure to state what information is contained in the certifi-
cates that make it accept on YES instances.)
b. (10 points) Give a polynomial-time reduction R from the IndependentSet Problem that we
saw in class to the GuardsAndStreets Problem. Conclude that the GuardsAndStreets
Problem is NP-hard, and by part (a), also NP-complete.
(Hint: Model the GuardsAndStreets Problem as a graph problem. Make sure to show that your
reduction maps YES instances of the IndependentSet Problem to YES instances of the Guard-
sAndStreets Problem, and NO instances of the IndependentSet Problem to NO instances of the
GuardsAndStreets Problem.)
1The algorithm you are asked to design in Question 3, where you are using a black-box algorithm for one problem
to solve another, is actually a type of reduction. These reductions are a bit different from the ones that we saw in
class for reducing instances of decision problems to equisatisfiable instances of other decision problems. That type
of reduction from class is called a mapping reduction, and the type of reduction in this problem is called a Turing
reduction.
3