CS180 Homework 4

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:
https://www.youtube.com/watch?v=-wemznvGPfg
– 2. Follow the instructions to generate a PDF scan of the assignments:
http://gradescope-static-assets.s3-us-west-2.amazonaws.com/help/submitting_
hw_guide.pdf
– 3. Make sure you start each problem on a new page.
Æ We recommend to use LATEX, LYX or other word processing software for submitting the homework. This is
not a requirement but it helps us to grade the homework and give feedback. For grading, we will take into
account both the correctness and the clarity. Your answer are supposed to be in a simple and understandable
manner. Sloppy answers are expected to receiver fewer points.
Æ Unless specified, you should justify your algorithm with proof of correctness and time complexity.