代写CSE 491留学生、Java，c++程序代写、代做Python，Java、代做Bioinformatics

日期：2019-02-11 10:46

CSE 491 Introduction to Bioinformatics

Homework 2

Assigned on February 5, 2019. Written solution due at start of class on February 14, 2019.

Type-set solutions are preferred. Remember that written homework solutions must be type-set

to be eligible for electronic submission. If you submit a hand-written solution, please make an

effort to use neat, clean handwriting. Hand-written homework solutions must physically submitted

in-person. See syllabus for more details regarding this policy.

Reminder: CSE 491 adheres to Michigan State University’s policies on academic integrity. No

collaboration is allowed on homeworks, and all work must be your own.

1. (10 points) The unrooted version of a rooted leaf-labeled binary tree can be obtained by

simply ignoring edge directionality, deleting the root, and then “connecting” its two incident

edges.

Equivalently, an unrooted leaf-labeled binary tree is an undirected graph G = (V, E) where

G is connected, acyclic, all nodes v ∈ V have degree of either 1 (i.e., leaf nodes) or 3 (i.e.,

internal nodes), and all leaf nodes have distinct labels. Recall that the degree of a node in

an undirected graph is defined as the number of edges incident upon it.

For example, see Figure 1 which shows three distinct unrooted leaf-labeled binary trees. These

are the only possible distinct unrooted leaf-labeled binary trees with four taxa.

Using induction, prove that the number of distinct unrooted leaf-labeled binary trees on n

taxa is (2n 5)!!.

Figure 1: These are the only possible distinct unrooted leaf-labeled binary trees with four taxa.

(5 points) Without using induction, prove that the number of distinct unrooted leaf-labeled

binary trees on n taxa is (2n 5)!!.

(Hint: you can make use of the fact that the number of distinct rooted leaf-labeled binary

trees on n taxa is (2n 3)!!, as we proved in class.)

2. (5 points) Let i be a natural number. Let T be the set of rooted binary trees which have

n = 2i

leaves. Let X T be the subset of such trees having maximal height. What property

(or properties) do the trees in X have in common? Prove that your answer is correct.

(5 points) Let Y T be the subset of such trees having minimal height. What property (or

properties) do the trees in Y have in common? Prove that your answer is correct.

1

3. Optional bonus problem (+10 extra credit points):

Recall that the nth Fibonacci number can be defined using a recursive function f:

f(0) = 1

f(1) = 1

f(n) = f(n1) + f(n2) where n is a natural number greater than 1

Also recall that the golden ratio constant is defined to be, and the complement of

φ is defined to be ψ = 1

Prove that f can be equivalently expressed in the following non-recursive form:

f(n) = φ

where n is a natural number