===========================================================================
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!