COMP4500/7500 Advanced Algorithms & Data Structures Sample Solution to Tutorial Exercise 1 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland August 5, 2014
1. Consider a binary tree structure defined using a Java class definition like:
class TreeNode {
String info;
TreeNode left;
TreeNode right;
}
Here info contains the data item in the node; left and right are “pointers” to the left and right subtrees
respectively. If a subtree is empty then its corresponding pointer is null.
Give recursive procedures for the following problems in pseudocode or Java-like pseudocode. Carefully explain
any assumptions you need to make.
The Java environment is not well-defined; to answer this question in Java requires knowledge of the available methods and class variables. For example, with a traversal method we could piggy-back on it easily to count the number of nodes. So the solutions here use pseudocode like that used in the text.
(a) Determine the size of (number of nodes in) a tree. (Remember to deal correctly with the case of an empty tree, that has no nodes.)
Sample solution.
SIZE(T)
1 ifT==NULL
2 return 0
3 else
4 return SIZE(T.left) + SIZE(T.right) + 1
In Java, if the methods are written within TreeNode that will handle the case of a non-empty tree. A clean way to extend the methods to handle empty trees is to have a top-level class Tree and have TreeNode as a sub-class that represents non-empty trees and a second sub-class EmptyTree that represents an empty tree. The SIZE method of EmptyTree would return 0.
(b) Determine the height of a tree.
Sample solution.
HEIGHT(T)
1 ifT==NULL
2 return 0
3 else
4 return MAX(HEIGHT(T.left), HEIGHT(T.right)) + 1
This assumes that the HEIGHT of an empty tree is 0 and that a function max is suitably defined.
(c) Determine whether a value given as a parameter is a member of a tree, assuming the tree is ordered as a
binary search tree.
∗Copyright ⃝c reserved August 5, 2014
1
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 1 (August 5, 2014) 2 Sample solution.
MEMBERBST(T, E)
1 2 3 4 5 6 7 8
ifT==NULL return FALSE
elseif E == T.info return TRUE
elseif E > T . info
return MEMBERBST(T.right, E)
else
return MEMBERBST(T.left, E)
This assumes that == and > are suitably defined on the type of E. (d) Determine whether a value is a member of an unordered tree.
Sample solution.
MEMBER(T, E)
1 return T ̸= NULL and (E == T.info or MEMBER(T.right, E) or MEMBER(T.left, E))
An alternative approach is to use if statements.
2. (CLRS Exercise 3.2-2, p60 (3rd), p57 (2nd), CLR Exercise 2.2-3, p37 (1st))
Prove alogb n = nlogb a.
Remember that the logarithm (base b) for any positive y, i.e., logb y, is defined to be the power to which b is
raised to get y, so by definition blogb y = y . You may also use the fact that (xa)b = x(a·b). Sample solution.
alogb n =
— blogb a = a
— prop. powers
— mult. commutative
— prop. powers —blogbn=n
(blogb a)logb n
= b(logb a)·(logb n)
= b(logb n)·(logb a)
= (blogb n)logb a
= nlogba
3. Use mathematical induction on n to prove the following linearity property of summations for all n ≥ 0. nnn
(cak +bk)=cak +bk
k=1
Note that, by definition, for any term tk : tk = 0. k=1
k=1 k=1
m+1(cak + bk) =
(cam+1 + bm+1) + m (cak + bk) k=1
— prop. summation — ind. hypothesis — regrouping — prop. summation (twice)
k=1
= (cam+1 + bm+1) + c mk=1 ak + mk=1 bk
0
Sample solution. Base case: for n = 0 the summations are all 0. Hence
0k=1(cak +bk) = 0
= c·0+0
= c0k=1ak+0k=1bk
Inductive case: assume the property holds for n = m and prove it holds for n = m + 1.
= c(am+1 + mk=1 ak) + bm+1 + mk=1 bk
= c(m+1 ak ) + m+1 bk
k=1 k=1
4. Use induction to prove the following property of arithmetic series for all n ≥ 0. n n(n + 1)
k=1+2+3+···+n= 2 k=1
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 1 (August 5, 2014) 3 Sample solution. Base case: for n = 0 the summation is 0. Hence 0 k = 0 = 0(0+1) .
k=1
Inductive case: assume the property holds for n = m and prove it holds for n = m + 1.
2
m+1 k k=1
= (m+1)+m k k=1
= (m + 1) + m(m+1) 2
= 2(m+1)+m(m+1) 2
= (m+1)(m+2) 2
—prop. summation — ind. hypothesis — putting m + 1 over 2 — factoring m + 1
5. (CLRS Exercise A.1-1, p1149 (3rd), p1062 (2nd), CLR Exercise 3.1-1, p45 (1st))
n
Find a simple formula for: (2k − 1). k=1
Sample solution. Using the linearity property (see Question 3 above) we can rewrite the summation to use an arithmetic series (see Question 4).
nk=1(2k − 1)
= 2 nk=1 k − nk=1 1 = 2 n(n+1) − n 1
2 k=1 = n(n+1)−n·1
= (n2+n)−n = n2
— linearity — arithmetic series —constantsummation
6. Use induction to prove the following property of geometric (or exponential) series, for all n ≥ 0 and real x ̸= 1.
xn+1 − 1 x−1
An infinite summation is defined to be the limit as n tends to infinity of the corresponding finite summation. ∞n
tk = lim tk
n→∞
n k=0
xk =1+x+x2 +···+xn = For |x| < 1, show the following holds when the summation is infinite.
∞ 1
xk = 1 − x k=0
k=0
Sample solution. Throughout the following we assume x ̸= 1 (as given). We start with the finite sum.
Basecase:forn=0,0 xk =x0 =1= x0+1−1,asx̸=1. k=0 x−1
Inductive case: assume the property holds for n = m and prove it holds for n = m + 1.
k=0
m+1 xk k=0
= xm+1 + m xk k=0
= xm+1 + xm+1−1 x−1
= (x−1)xm+1+xm+1−1 x−1
= x(m+1)+1−xm+1+xm+1−1 x−1
limn→∞ nk=0 xk
limn→∞ xn+1−1
— prop. summation — ind. hypothesis — putting xm+1 over x − 1 — expanding (x − 1)xm+1
x(m+1)+1 −1 x−1
=
An infinite summation is defined to be the limit of the finite summations to n, as n tends to infinity.
∞k=0 xk =
— infinite sum — geometric sum —limn→∞xn+1 =0for|x|<1
=
= 0−1
x−1
=
x−1 1
1−x