Exercise Lover

March 19, 2007

Exercises B.5-7

Filed under: B.5 — yuhanlyu @ 8:44 am

Proof by contradiction.
Suppose that a tree T with L leaves contains no subtree having between L/3 and 2L/3 nodes. Let root be x_0. We find x_i = children of x_{i-1} with more leaves. Since the tree has only L leaf nodes, so there must be one i such that x_i has more than 2L/3 leaves nodes and x_{i+1} has fewer than L/3 leaves. Since sibling of x_{i+1} has fewer than L/3 leaves, x_i can’t have 2L/3 leaves.

Exercises B.5-6

Filed under: B.5 — yuhanlyu @ 8:30 am

Proof by induction.
Base case: If tree T has just one node. Trivial.
Induction step: Assume that \sum_{x \in leaf} w(x) \leq 1 for all tree size smaller than k. Suppose that a tree T with size k. If T’s root has a subtree, then \sum_{x \in subtree's leaf} w(x) is at most 0.5. Because the depth increase by one. Since T has at most two subtrees, the inequality is hold.

Exercises B.5-5

Filed under: B.5 — yuhanlyu @ 8:17 am

Proof by induction.
Base case: A tree with one node. Trivial.
Induction step: Assuem E = I+2n for all tree with size smaller k. Suppose that a tree T with size k. We can construct T’ by removing a internal leaf node x, then E’ = I’ + 2n-2. When adding x back, we must add two external node. So E = I + 2n – 2 + 2 = I + 2n.

March 18, 2007

Exercises B.5-4

Filed under: B.5 — yuhanlyu @ 2:41 pm

Base case: If a tree has only one node, then the height = 1 > \lfloor \lg 1 \rfloor = 0.
Induction step: Assume binary tree with n nodes has height at least \lfloor \lg n \rfloor, for all n < k. Suppose that a binary tree T with k nodes. We can construct a tree T’ by remove a node from T, such that the height of T’ > \lfloor \lg (k-1) \rfloor. Because \lfloor \lg (k-1) \rfloor = \lfloor \lg k \rfloor except k is power of 2. T’s height = T’s height > \lfloor \lg k \rfloor. If k is power of 2, then the inequality is also hold.

Exercises B.5-3

Filed under: B.5 — yuhanlyu @ 2:32 pm

Base case: A tree with three vertices, one is root and others are leaves. The number of degree-2 nodes is 1 less than the number of leaves.
Induction step: Assume the number of degree-2 nodes is 1 less than the number of leaves for all tree with size smaller than k-1. Suppose that a tree with k nodes, we can find a leaf x and remove it. If x’s parent’s degree is 1, then both the number of degree-2 nodes and the number of leaves don’t change. If x’s parents degree is 2, then both the number of degree-2 nodes and the number of leaves decrease by one. The proposition that number of degree-2 nodes is 1 less than the number of leaves is hold.

Exercises B.5-2

Filed under: B.5 — yuhanlyu @ 2:23 pm

Because G is acyclic, there is no directed cycle. But if there one vertex which has two path to another vertex, then the undirected version also has cycle. However v_0 has a unique path to all the other vertices. Hence the undirected version must be connected and has no cycle, which is a tree.

Exercises B.5-1

Filed under: B.5 — yuhanlyu @ 6:42 am

Blog at WordPress.com.