=========================================================================== CSC 236 Tutorial Solutions for Week 3 Winter 2012 =========================================================================== 1. A "complete binary tree" is a binary tree in which every node has two children, except for the leaves (which have no child), and every leaf is at the same depth (same distance from the root). { Draw some pictures here, of complete binary trees and also trees that are not complete for various reasons (unbalanced, or some node missing a child. } It is possible to give a recursive definition for the set of all complete binary trees: (a) A single node is a complete binary tree. (b) If T_1 and T_2 are a complete binary tree with the same height, then the tree constructed by placing T_1 and T_2 under a new root node is also a complete binary tree. (c) Nothing else is a complete binary tree. { See the Assignment 1 handout for a picture to illustrate this. } Use structural induction to prove that, for all complete binary trees T, if h is the height of T, then T contains exactly 2^{h+1} - 1 nodes. { Make sure the definition of "height" is clear for everyone: it's the distance (number of edges) from the root to a leaf-- so it's equal to 0 for a single node, 1 for a tree with one root and two leaves, etc. } 0. P(T): T contains 2^{h+1} - 1 nodes, where h is the height of T. 1. Base Case: T = a single node. Then T has height 0 and contains 1 = 2^{0+1} - 1 nodes. 2. Ind. Hyp.: Assume T is a complete binary tree and that T contains 2^{h+1} - 1 nodes, where h is the height of T. 3. Ind. Step: Consider the tree with root r, both of whose children are copies of T. This tree has height h+1 and it contains (2^{h+1} - 1) + 1 + (2^{h+1} - 1) = 2^{h+2} - 1 nodes. 4. By structural induction, every complete binary tree contains exactly 2^{h+1} - 1 nodes, where h is the height of the tree. 2. Explain what is wrong with the following "proof". Define P(n): In every set of n horses, all horses have the same colour. (Say that every horse has a single "main" colour we are considering.) We "prove" \-/ n (- N, P(n): - Base Case: P(0) is vacuously true: in every set of 0 horse, all horses have the same colour. P(1) is true: in every set of 1 horse, all horses have the same colour. - Ind. Hyp.: Let n (- N and suppose P(n): in every set of n horses, all horses have the same colour. - Ind. Step: Prove P(n+1): in every set of n+1 horses, all horses have the same colour. Let S be a set of n+1 horses, say S = { h_1, h_2, ..., h_{n+1} }. Consider { h_1, h_2, ..., h_n }: this is a set of n horses, so by IH, all horses in that set have the same colour, say A. Now consider { h_2, ..., h_n, h_{n+1} }: this is also a set of n horses, so by IH, all horses in that set have the same colour, say B. Since horses h_2, ..., h_n belong to both sets and cannot have two different main colours, it must be that A = B. This means every horse in S has the same colour. Problem? Base Case is OK, Ind. Hyp. is OK, but Ind. Step makes an implicit assumption about n: reasoning only works if n > 1 (if n = 1, reasoning fails for S = { h_1, h_2 } because there is no horse in range h_2 .. h_n). This could be "fixed" by changing IH to "let n >= 2", but then proof only shows P(1) /\ \-/ n >= 2, P(n) -> P(n+1)-- IH does not "connect" with base case(s). If we try to "fix" this again by adding base case P(2), proof fails because P(2) cannot be proven. Moral: Look out for implicit assumptions in inductive step; make sure structure of inductive proof "fits" together properly. 3. Explain what is wrong with the following "proof" that 1^2 + 2^2 + ... + n^2 (- O(n^2): - Base Case: 1^2 <= c 2^1 for any c >= 1. - Ind. Hyp.: Let n >= 1 and suppose 1^2 + ... + n^2 (- O(n^2), i.e., 1^2 + ... + n^2 <= c n^2 for some constant c > 0. - Ind. Step: Prove 1^2 + ... + (n+1)^2 (- O((n+1)^2). 1^2 + ... + (n+1)^2 = 1^2 + ... + n^2 + (n+1)^2 <= c n^2 + (n+1)^2 <= c (n+1)^2 + (n+1)^2 <= (c+1) (n+1)^2 so 1^2 + ... + (n+1)^2 <= (c+1) (n+1)^2, for constant c+1. Problem? Predicate P not carefully defined, so not used properly. Recall that "1^2 + ... + n^2 (- O(n^2)" stands for -] c > 0, -] B, \-/ n >= B, 1^2 + ... + n^2 <= c n^2. But this is NOT a statement about a single value of n (it contains \-/ n), so not a valid P(n)! This shows up in "proof" above because value of constant *changes* between IH and Ind. Step-- but then it's not constant! To prove 1^2 + ... + n^2 (- O(n^2) by induction would mean: Pick values of c > 0 and B. Prove \-/ n >= B, 1^2 + ... + n^2 <= c n^2 using induction (where values of c, B are fixed). However, this is not possible (\sum i^2 !(- O(n^2)). Moral: Define P(n) carefully!