Introduction to Algorithm Assignment 4

   

  • Submission Guideline: Upload your homework file (hw3_[your student id].doc or hw3_[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.

   

  1. Show the comparisons the naive string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.

   

  1. Show the comparisons the KMP string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.

   

  1. Show the comparisons the Boyer-Moore string matcher makes for the pattern $abacab$ in the text $abacaabadcabacab$.

   

  1. 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.

   

  1. 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.

   

  1. Show that the problem of determining the satisfiability of boolean formulas in disjunctive normal form is polynomial-time solvable.

   

  1. 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.)

   

  1. 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.