Homework #8 Solution


Category: Tag:


  1. Reductions

Let A B for two problems A and B mean that problem A can be solved in big O of the time it takes to solve problem B.




  1. If A B means A B and B A which of MULTIPLICATION, SQUAR-ING, and RECIPROCAL are equivalent ?

HINT: x1y1 = yxyx . Try y = x + 1.

  1. Lucas Numbers:

INPUT: A K bit number X.

QUESTION: Is X a Fibonacci number?

The Lucas numbers are defined by the recurrence

Ln = Ln−1 + L n−2

with the initial conditions: L0 = 2, L1 = 1 Show that this problem is in P by out-lining (NO CODE, just explain what you’re doing) an algorithm, AND showing that your algorithm runs in polynomial time in K, the number of bits.

  1. Roots:

Without finding the solutions, show that x2 − x − 1 = 0 has:

    1. NO positive integer solutions

    1. NO rational solutions


      1. Assume that x = p/q where p and q are integers with no common factors.

      1. p2 − q2 = (p − q) (p + q).

      1. Each integer is either ODD or EVEN.

  1. Average Case:

Do Exercise 5.25 in the NOTES on page 61.

  1. Lower Bound:

Exercise 6.1 in the NOTES on page 71, is about the lower bound of 32 n − 2 comparisons to find the largest and smallest elements in an array. Devise a divide-and-conquer algorithm for this problem and show that the number of comparisons used by your algorithm achieves this lower bound.

  1. Boolean Expression:

Assume that you have an algorithm YS( ) so that when you input a Boolean expression E(x1, . . . , xn) into YS( ) ,

YS( E ) outputs YES if E is satisfiable, and YS( E ) outputs NO if E is not satisfiable.

    1. Show how to use YS( ) to construct an algorithm FIND( D(x1, . . . , xn)) which when given a satisfiable Boolean expression D(x1, . . . , xn), returns an assignment x1 = a1, x2 = a2, . . . , xn = an, so that D(a1, . . . , an) is TRUE.

    1. Assume that YS( D(x1, . . . , xn) ) has run time O( nk ) and find the run time of FIND( D(x1, . . . , xn) ) .

  1. Platonic Hamiltonian Circiuts:

Show that each of the PLATONIC solids has a Hamiltonian circuit.

  1. s-t Hamiltonian Path:

INPUT: A graph G and two specified vertices s and t.

QUESTION: Does G have a Hamiltonian Path which starts at s and ends at t?

    1. Assume that you know that Hamiltonian Circuit is N P −Complete, show that s-t Hamiltonian Path is N P −Complete.

    1. Assume that you know that s-t Hamiltonian Path is N P −Complete, show that Hamiltonian Circuit is N P −Complete.

    1. Show that the Yes/No version of TSP (Traveling Sales Person) with all edge weights in {1, 2} is N P −Complete. (You should assume that Hamiltonian Cir-cuit is N P −Complete.)

  1. Graph Isomorphism:

Graph isomorphism is an example of a problem which is in N P, but is not known to be N P-complete, nor is it known to be in co-N P.

INPUT: Two graphs, G1 = (V1 , E1) and G2 = (V2 , E2).

QUESTION: Can the vertices of G1 be renamed so that G1 becomes G2? (Is there a

one-to-one onto function f : V1 ! V2 so that 8x, y (x, y) 2 E1 i( f(x), f(y) ) 2 E2? Show that GRAPH ISOMORPHISM is in N P.

  1. Canonical Number:

A graph with n vertices can be represented as an n n binary matrix which has a 1 in position (i, j) if and only if there is an edge (vi, vj ). If you “unroll” this matrix (say by rows), you will have a vector of n2 bits and you can consider this to be a number in standard binary notation. So, there is a correspondence between n vertex graphs and n2 bit numbers. If we re-label the vertices of the graph, we don’t change the graph properties. Dierent re-labelings of the graph will (usually) give dierent numbers. Clearly among all re-labelings of the graph, there is some re-labeling which gives the smallest value for this binary number. We would like to represent a graph by the minimum number we can get by re-labeling. We’ll call this minimal number the canonical number of the graph. It’s easy to see that two graphs are isomorphic ithey have the same canonical number.

(a) The graph v1 — v2 — v3 is isomorphic to v1 — v3 — v2 and is also isomorphic to v2 — v1 — v3.

Find the canonical number of v1 — v2 — v3.

    1. Show that if finding the canonical number of a graph is easy, then GRAPH ISO-MORPHISM is easy. (Here, easy means takes polynomial time. )

However, canonical number may be harder than GRAPH ISOMORPHISM. If I can tell that two graphs are NOT isomorphic, I know that their canonical numbers are dierent, but I don’t know what their canonical numbers are. Further, if I know that two graphs are isomorphic, I know that their canonical numbers are identical, but again I don’t know what these canonical numbers are.

    1. Is-Canonical:

INPUT: A graph G and an integer I.

QUESTION: Is I < the canonical number of G?

EXERCISE: Show that IS-CANONICAL is in co-N P.

  1. Tautology:

INPUT: A Boolean Expression E(x1, . . . , xn).

QUESTION: Does E evaluate to TRUE for each and every assignment of TRUE and FALSE to the variables, the x’s ?

Show that TAUTOLOGY is co-N P-complete.

  1. 3-SAT:

INPUT: A Boolean Expression E(x1, . . . , xn) in Clause form with at most 3 literals per clause.

QUESTION: Does E evaluate to TRUE for some assignment of TRUE and FALSE to the variables, the x’s ?

Show that if SAT is N P-complete, then 3-SAT is N P-complete.

error: Content is protected !!