This assignment is worth a total of 50 points.
All homework will be submitted electronically, using the curator system. You may submit your homework in any format that can be opened using Microsoft Word (including plain ASCII text). If you submit more than one version of your homework, we will store all submissions, but will actually grade the latest one. Make sure that your file contains at the top your name, your ID number, and your email address.
Where a question number is used, it refers to a question from the textbook.
1. Exercise 2.14; Also, what is the big-theta running time of the algorithm?
printSubsets(n, list=""): // list is a generic list ADT of
integers
if n==0 then //base case
print "{", list, "}"
else
//recursive case
printSubsets(n-1, list)
//all subsets without n
printSubsets(n-1, toString(n) + ", "
+ list) //all subsets with n
O(2^n)
2. Exercise 3.9 parts a, c, e, and g
(a) theta
(c) omega
(e) omega
(g) omega
3. Exercise 4.10
int = 4
double = 8
pointer = 4
(a) n > arraysize/2
(b) n > arraysize * 2/3
4. Exercise 5.2 (change "in any binary tree" to "in any non-empty binary tree")
prove: for any binary tree with L leaf nodes and D degree 2 nodes, D = L-1
induction on L (can also be done differently on D):
base case: L = 1
can only be a single node, or a linear chain of nodes. hence D=0 = L-1
induction step: L>1
assume all trees with L' = L-1 leaf nodes have D' = L'-1 degree 2 nodes.
take a tree T with L leaf nodes and D degree 2 nodes,
want to show that D = L-1.
remove a leaf c from T to create new tree T'. 2 cases:
* case 1: c's parent p is degree 1: p now becomes a leaf, so T' still has
L leaves and D degree 2 nodes.
so repeat removing a leaf until case 2 occurs.
* case 2: c's parent p is degree 2: p now becomes degree 1, so T' lost a
leaf and a degree 2 node.
hence, T' has L'=L-1 leaves and D'=D-1 degree 2 nodes, and so
induction hypothesis applies to T'.
D = D'+1 = (L'-1)+1 = ((L-1)-1)+1 = L-1.
5. Exercise 5.8; Also, what is the big-theta running time of the algorithm?
int countLeaves(p):
if p==Null then return 0
if p->left==Null and p->right==Null then return 1
else return countLeaves(p->left) + countLeaves(p->right)
O(n)