CMSC 435  Algorithm Analysis & Design

 

Homework # 11

Due December 7

 

  1. Construct a Turing machine that recognizes well-formed strings of curly brackets.

 

  1. Construct a Turing machine that copies the contents of its tape immediately to the right of original source.  Assume S = {0, 1, #} where # is the end of string marker, and assume the tape head is initially positioned immediately to the left of the source string.

 

  1. Given that k-CLIQUE is in NP-Complete, construct a proof that VERTEX-COVER is also in NP-Complete.  Can you use 3-SAT to show that k-CLIQUE is in NPC?

 

 

  1. Write a program to verify that a candidate solution for a TSP tour is correct.  The input for this program will consist of a graph, with the cities as the vertices and the connecting roads as edges, and the certificate.  The graph may be expressed as an N ´ N matrix with the (i, j)th entry indicating the distance between the cities numbered i and j.  If no road directly connects this pair of cities, the matrix entry will be 0.  The certificate consists of a sequential list of the cities visited during the tour and the target value that the tour is not to exceed.  Demonstrate that your program decides this question in O(P(N)) time.

 

  1. Given that HAM-CYCLE is in NP-Complete.  Prove that TSP is in NP-Complete.

 

  1. Convert the clause {x1, ~x2, ~x3, x4, x5, ~x6, x7} into a conjunction of clauses in 3-SAT.  Prove that the formula in 3-SAT is satisfied if and only if there is at least one literal in the original clause that is true.  Outline an algorithm for reducing a clause in SAT into 3-SAT.  Show that this reduction can be performed in polynomial time.