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.