CSE 5311 Fall 1999

**Quiz #8**

- 1.
- (8 points).
You are given experimental data consisting of small DNA fragments.
For each fragment
*f*, it has been determined experimentally that certain fragments lie to the left of*f*on the chromosome, certain fragments lie to the right of*f*, and the rest can be on either side. How would you find a consistent ordering of the fragments from left to right that satisfies all the constaints? Solve this problem using one of the graph algorithms introduced in class.

- 2.
- (12 points). Suppose graph G has two edge-disjoint spanning trees (two spanning trees that have no edges in common). Prove that in this graph G, every pair of nodes forms part of a cycle.