Sale!

# CS180 Homework 4

\$35.00

Category:
5/5 - (2 votes)

CS180 Homework 4

1. (25 pt) A palindrome is a string that reads the same from left to right and from right to left. Design an
algorithm to find the minimum number of characters required to make a given string to a palindrome if you
are allowed to insert characters at any position of the string. For example, for the input “aab” the output
should 1 (we’ll add a ’b’ in the beginning so it becomes “baab”).
The algorithm should run in O(n
2
) time if the input string has length n.
2. (25 pt) Consider the problem of “Approx-3SAT”: The input is the same as 3-SAT, which is a boolean expression C1∧C2∧···∧Cn where each Ci
is an “or” of three literals (each literal can be one of x1
, . . . , xm,¬x1
, . . . ,¬xm).
Note that we assume a clause cannot contain duplicate literals (e.g., (x1 ∨ x1 ∨ x2
) is not allowed). Instead
of determining whether there’s a truth assignment on {xi
}
m
i=1
that satisfies this boolean expression (which
means it satisfies all the clauses), now we want to determine whether there’s an assignment that satisfies
at least n − 1 clauses. Prove that Approx-3SAT can be polynomial time reduced to 3-SAT.
Æ Homework assignments are due on the exact time indicated. Please submit your homework using the
Gradescope system. Email attachments or other electronic delivery methods are not acceptable. To learn
how to use Gradescope, you can:
– 1. Watch the one-minute video with complete instructions from here:
– 2. Follow the instructions to generate a PDF scan of the assignments: