COS 341, November 12, 1997

Handout Number 15

Homework Set 7

Reading Assignments Read Chapter 12.

Written Assignments Do Exercises 5, 13, 18, 19, 30 and 42 in Chapter 12.6.

Remark In your solution to Exercise 5, be sure to give a rigorous justification of your claim.

Special Problem 1 (counted as 2 exercises) An ancient DNA fragment of a dinosaur has just been found. It is known that this critical fragment contains some critical information. If the string ACGAACT appears in , then it can fly; if the string CTCACG appears in , then it is vegetarian; if the string TGACCT appears in , then it is a timid dinosaur.

The fragment has length 17, and you have subjected it to the hybridization procedure with . The spectrum S you get consists of the strings ACGA, AACT, ACTC, ACGT, GACT, CTCA, CGAA, CTGA, TGAC, GAAC, GACG, ACTG, CACG, TCAC. What kind of dinosaurs can you infer? What is ? What is ? Find all the which has S as its spectrum. Special Problem 2 (counted as 2 exercises) A bicycle graph of order n is a graph of the form shown in the figure below, with each wheel containing n vertices. The BICYCLE problem is: Given as input a pair (n, G), where n is an integer and G is a graph on or less vertices, decide whether G contains (as subgraph) a bicycle graph of order n.

Question: Prove that the Hamiltonian cycle problem is polynomial-time reducible to the BICYCLE problem.

• About this document ...