CS 535
                                                       Fall 2010

                      Assignment #2


Date Due: Tuesday, September 28

Reading:  Chapter 6, pages 122-142.

Problems :

1. An undirected graph G has a Hamiltonian circuit if it has a 
cycle which contains every vertex in G. 
(This definition and an example are on page 4 of the book. )

The set HAM-PATH is set of all undirected graphs which 
have Hamiltonian circuits. 

Design a nondeterministic algorithm to accept the set HAM-PATH. 

Suggestion: Take a look at example 2.3 on page 33 of the book. 
There a nondeterministic algorithm is described for the clique problem C.

Your algorithm for HAM-PATH should follow this pattern and be 
quite similar in detail to the algorithm in this example.

2. Describe a deterministic algorithm which decides the set HAM-PATH.

Try to analyze the time complexity your deterministic algorithm.  
That is, for a graph of n vertices, approximately how many steps does you algorithm 
take (at most). 

3. a. Prove that the union of 2 decidable languages is decidable. 

b. Does you proof in part a work for acceptable languages as well ?
That is, does it show that the union of 2 acceptable languages is acceptable ? 

Why or why not ? 

4. Show that if a language B is decidable then so is BB, the 
concatenation of B with B.