CMSC 435 Algorithm Analysis & Design

Answers to Homework

1. Г = { {, }, a, b, c, S} Q = { q₀, …, q₅} ∑ = { {, } } S = blank

δ	{	}	a	b	c	sp	comment
q0	q0aR	q1bL				q 5S H	Mark left brackets until first unmarked right bracket
q1			q2cR	q 1bL	q 1cL	q 5SH	Find first match for right bracket and mark it c
q2	q0aR	q1bL	q 2aR	q 2bR	q 2cR	q 3SL	Any more left or right brackets? If not, go to q3
q3			q 5aH	q 3}L	q 3{L	q 4SH	If only b and c, restore and accept

q₄ = Accept q₅ = Reject

2.

….

b

1

0

1

1

0

1

#

b

…..

Г = { 1, 0, #, b} Q = { q₀, …, q₄} ∑ = { 1, 0, # }

δ	0	1	#	b	comment
q0	q1bR	q2bR	q0#H		Remember bit and overwrite with b
q1	q10R	q11R	q1#R	q 30L	Move to copy of string and copy 0 into first blank
q2	q20R	q21R	q 2#R	q 41L	Copy 1 into first blank in copy of string
q3	q 30L	q 31L	q 3#L	q 00R	Moving left to restore 0
q4	q 40L	q 41L	q 4#L	q 01R	Moving left to restore 1

3. Step 1 -- Show that VERTEX-COVER is in NP.

Given an instance of VERTEX-COVER(G, K) and a Certificate(G, S(K), K),

the Certificate can be verified in O(p(n)) as follows:

initialize a counter to 0

construct a boolean matrix indexed by the vertices of G, boolean[][] m, initialized to all false

For each vertex in S(K)

get next vertex, call it u

increment counter

For each edge (u, v) in adjacency list of u

set m[u][v] = true

Traverse the set of edges E and return false if m[i][j] = false for any edge (i, j) ϵ E //O(|E|)

return (counter <= K)

Step 2 -- Show K-CLIQUE(G) _p£ VERTEX-COVER(G', |V| - K)

Construct G'(V, E') where each vertex of G is a vertex of G' and

for every pair of vertices i, j where i ¹ j, edge (i, j) is in E' if and only if it is NOT in E //O(|V|²)

The set V’, the Vertex-Cover for G' consists of all vertices that are not part of the clique in G.

Let (u, v) be any edge in E’, then either u ϵ V’ or v ϵ V’ or both //(not in the clique)

Therefore V’ where |V’| = |V| - K forms a vertex cover for G’

And for any x, w ϵ V, if both x and w not ϵ V’, then (x, w) ϵ E,

And V - V’ is a clique of size |V| - |V’| = K.

4. Algorithm VerifyTSP

Input: M: an N x N cost matrix

Tour: an N+1 dimensional array of vertices (integers)

K: maximum length of the tour

Local: boolean[] visited = new boolean[N]

for (int i = 0; i < N; i++) // O(N)

visited[i] = false;

for (int j = 1; j <= N; j++) {

//skip the start index

if (!visited[tour[i]])

Visited[tour[i]] = true;

else

return false; //not a Hamiltonian tour

} //O(N)

//check visited to make sure all are true

for (int k = 0; k < N; k++)

if (!visited[i]) return false;

//check that first and last vertices in the tour are the same

if (tour[0] != tour[N]) return false;

//check that there is an edge for each pair of vertices

double cost = 0.0;

for (int h = 0; h < N; h++) { //O(N)

double edge = M[tour[h]][tour[h+1]] ;

if (edge == infinity) return false ;

else cost += edge;

}

return (cost <= K); //O(1)

5. Given HAM-CYCLE in NP-Complete, prove TCP in NP-Complete

Step 1. Show TSP in NP

Given an instance, I, of TSP(N, K), and a certificate, C(I)

Prove that (I, C(I)) can be verified in polynomial-time (see Problem 4)

Step 2. Find a polynomial-time reduction of any instance of HAM-CYCLE

in to an instance of TSP such that the instance of HAM-CYCLE is

accepted iff TSP is accepted

There is a reduction of a graph G in HAM-CYCLE to a graph G' in TSP

Let every vertex in G be a vertex in G'. Let every edge in G be an edge

of cost 0 in G'

for (int i = 0; i < N; i++)

for (int j = 0; j < N; j++) { // Construct G' in O(N²)

if (i != j && G[i][j])

G'[i][j] = 0;

else if ( i != j)

G'[i][j] = 1;

}

There is a TSP(N, 0) tour iff G has a Hamiltonian cycle.

6. Convert {x₁, ~x₂, ~x₃, x₄, x₅, ~x₆, x₇} into CNF-3-SAT

Introduce 4 new variables {z₁, z₂, z₃, z₄}

Construct 5 clauses

{x₁, ~x₂, z₁}

{~x₃, ~z₁, z₂}

{x₄, ~z₂, z₃}

{x₅, ~z₃, z₄}

{~x₆, x₇, ~z₄}

Then these 5 clauses are all satisfied iff the clause in SAT is satisfied.

Without loss of generality, assume that x₅ = T which satisfies the original clause.

Then all the clauses in 3-SAT are simultaneously satisfied if we set k = 5

and for all 0 £ i £ k - 2 set z_i = T, and z_j = F for all j > k - 2. In this example

z₁ = z₂ = z₃ = T and z₄ = F

When these values along with x₅ = T are substituted into the 5 clauses in 3-SAT

each one has a literal that is set to T.

Only if -- If none of the literals in the CNF-SAT clause is T, then there is no

assignment for the z_i that will simultaneously satisfy all of the 5 3-SAT clauses.