Description
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(n2) 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 expres-
sion 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 fxi gmi=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.
