- Submission Guideline: Upload your homework file (
hw3_[your student id].doc
orhw3_[your student id].hwp
) to online Uclass classroom. You are allowed to write down your answers either in Korean or English at your convenience. - Deadline: 23:59 PM, Friday, June 21, 2024
Please feel free to leave your questions about homework problems in the online Ed Discussion platform.
- Show the comparisons the naive string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.
- Show the comparisons the KMP string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.
- Show the comparisons the Boyer-Moore string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.
- Give a dynamic-programming solution to the 0-1 knapsack problem that runs in $O(nW)$ time, where $n$ is the number of items and $W$ is the maximum weight of items that the thief can put in the knapsack. Is the dynamic-programming algorithm a polynomial-time algorithm? Explain your answer.
- Show that if $\text{HAM-CYCLE} \in P$, then the problem of listing the vertices of a hamiltonian cycle, in order, is polynomial-time solvable.
- Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.
- Let $\text{2-CNF-SAT}$ be the set of satisfiable boolean formulas in $\text{CNF}$ with exactly $2$ literals per clause. Show that $\text{2-CNF-SAT} \in P$. Make your algorithm as efficient as possible. ($\textit{Hint:}$ Observe that $x \vee y$ is equivalent to $\neg x \to y$. Reduce $\text{2-CNF-SAT}$ to an efficiently solvable problem on a directed graph.)
- Show how in polynomial time we can transform one instance of the traveling-salesman problem into another instance whose cost function satisfies the triangle inequality. The two instances must have the same set of optimal tours. Explain why such a polynomial-time transformation does not contradict the following theorem, assuming that $\text P \ne \text{NP}$.
Theorem: If $\text P \ne \text{NP}$, then for any constant $\rho \ge 1$, there is no polynomial-time approximation algorithm with approximation ratio $\rho$ for the general traveling-salesperson problem.