211L5Solutions

Exercise

2. Construct expression trees for the following expressions 2, x/y, ((x/y) + ((2 + z) ⋆ y)), ((((x ⋆ y) + (a + b)) ⋆ z) − 2).

2

  %
 / \
x   y

    +
   / \
  %   *
 / \  | \
x  y  +  y
     / \
    2   Z

        -
       / \
      *   2
     / \
    +   Z
   / \
  *   +
 / \ / \
x  y a  b

4. An arithmetic expression e is called ground if it contains no integer variables. Each ground arithmetic expression can be evaluated in a natural way. For example, the values of (2 −7), ((2 + 1) ⋆ (5 − 3)) are −5 and 6, respectively. Consider an expression tree T for a ground arithmetic expression. The value val(T ) of T is defined according to the following rules:

• (a) If T consists of the root then val(T ) is the label of the root.
• (b) If T is an expression tree for (e1 + e2) and Te1 and Te2 are expression trees for ground arithmetic expressions e1 and e2 then val(T ) = val(Te1 ) + val(Te2 ).
• (c) If T is an expression tree for (e1 ⋆ e2) and Te1 and Te2 are expression trees for ground arithmetic expressions e1 and e2 then val(T ) = val(Te1 ) ⋆ val(Te2 ).
• (d) If T is an expression tree for (e1 − e2) and Te1 and Te2 are expression trees for ground arithmetic expressions e1 and e2 then val(T ) = val(Te1 ) − val(Te2 ).

Prove by induction that for ground expressions e the value of e equals val(Te), where Te is the expression tree for e.

A base case of e where there are two variables and one operation, will always be equal to some value, val(Te). As such, combining any two expressions by an operation, is the same as combining the equivalent value of each sub expression. This creates a new value which can represent the tree.

6. Consider the FindComponents(G) algorithm. Build the forest F12 for the graph presented in Figure 4 for each of the following list of edges:

• (a) {a, d}, {a, g}, {b, e}, {c, f}, {c,m}, {e, j}, {e, h}, {f, l}, {g, i}, {h, j}, {i, k}, {l,m}.

                   h
a - d             /|  c - f
|            b - e |  |   |
g - i - k         \|  m - l
                   j

• (b) {a, g}, {e, h}, {b, e}, {c,m}, {e, j}, {a, d}, {f, l}, {l,m}, {g, i}, {h, j}, {i, k}, {c, f}.

                   h
a - d             /|  c - f
|            b - e |  |   |
g - i - k         \|  m - l
                   j

8. Let T be a tree with n nodes and m edges. Prove, using the induction on constructing trees, that m = n − 1.

A base case a single root node consists of 1 node and no edges. Two base cases can be combined into a new unit with two edges and a new root node. This means there are 3 nodes and 2 edges. This is preserved when any sub trees are combined. As such, by induction, every tree will have m = n-1 where m is the number of edges and n is the number of nodes.

10. Prove the following statement known as K¨onig’s lemma. A finitely branching tree T is infinite if and only if it has an infinite path. (Hint: If T is infinite then construct an infinite path by induction).

• If a finitely branching tree is infinite, then there can be an infinite path.

From any vertex in the tree, it is still possible to reach an infinite number of vertices as there is always another vertex down each of the finite branches which can be traveled too.

• If there is an infinite path, the tree can be finitely branching.

In a graph it is possible to have an infinite path from a finite number of branches. This is possible if down one of a finite set of branches, there is always an infinite path.

Programming exercises

2. Write a program that given a tree with a left-to-right order on children of its nodes outputs the nodes of the tree in post-order.

4. Write a program that given a tree T and its node x outputs the height of x.