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.