Homework Assignment 3

Due: by 10am on Thu 3 Apr
Worth: 8%

For each question, please write your answer carefully. Keep in mind that approximately half of the marks for each question will be given purely for having the correct proof structure, written up clearly and precisely, irrespective of the correctness of the proof. Also, make sure that you use notation and terminology correctly, and that you explain and justify what you are doing — marks will be deducted for incorrect or ambiguous use of notation and terminology, and for making incorrect, unjustified, ambiguous, or vague claims in your solutions.

  1. Reminders:

    • In a Binary Search Tree (BST), every node stores a value with the property that each node's value is greater than or equal to all the values in the node's left subtree and less than or equal to all the values in the node's right subtree. For this question, assume that no two values are the same, i.e., each value is different from all the others — this is not strictly necessary for the code below to be correct, but it makes the statement of correctness and its proof easier.

    • In Python (including the "pseudo-code Python" I use in the course), it is possible to test if a reference is "null" by using it as a truth value, e.g., the expression "node.left" in a boolean context (when evaluating an if-statement or while-statement) is considered True if node.left exists, and False if node.left does not exist (i.e., if node.left is the special value None; the Python version of "null").
      Also, the keyword 'is' compares that two references actually refer to the same object, e.g., 'node is node.parent.right' has value True when node is its parent's right child, False otherwise.

    Prove that the following algorithm is correct, including filling in appropriate loop invariants where indicated. 

        # Precond:  node is a reference to the root of a non-empty BST where each
    #     node stores a numerical value (in field datum), in addition to
    #     references to its parent, left child, and right child.  Also,
    #     every value in the tree is unique (does not appear more than once).
    count = 0
    average = 0.0
    # LI1:  The subtree rooted at node contains the smallest value in the
    #     entire tree.
    while node.left:  node = node.left
    # LI2:  average stores the average of every value in the tree that is
    #     strictly less than node.datum (or the average of every value in
    #     the tree if node is None).
    while node:
        count += 1
        average += (node.datum - average) / count
        # Let current denote the value just added to the average
        # (i.e., current = node.datum for the current node).
        if node.right:
            node = node.right
            # LI3:  (TO BE FILLED IN: state the relationship between current
            #     and values in the subtree rooted at node.)
            while node.left:  node = node.left
        else:
            # LI4:  (TO BE FILLED IN: state the relationship between current
            #     and values in the subtree rooted at node.)
            while node.parent and node is node.parent.right:  node = node.parent
            node = node.parent
        # Hint: state the relationship between current and node.datum for
        # the value of node at this point.
    # Postcond:  average stores the average of every value in the tree.

  2. Give a NFA and a DFA for the following language, and justify that both are correct (i.e., you do not have to write a complete proof of correctness, but you should describe clearly the meaning of each state, or show your work if you use a construction given in class).

    { w ∈ {-,0,1}* : |w| ≥ 3 and the third-last character of w is not 0 }

    (Where "third-last" is counted from the right.)

  3. In "balanced ternary" notation, positive and negative integers are represented using the "digits" -1, 0, +1, as follows: the representation of integer x consists of the sequence of digits ak, ak-1, ..., a1, a0 such that

    x = ak 3k + ak-1 3k-1 + ... + a1 31 + a0 30.

    For example, -5 = -9+3+1 so the representation of -5 is "-11" (using "-" to stand for -1). For another example, the representation of 21 is "1-10" because 21 = 27-9+3. For all strings of digits w ∈ {-,0,1}*, let #(w) denote the numerical value of w in balanced ternary, e.g., #(01011-) = 81+9+3-1 = 93.

    Give a FSA and a RE for the following language, and prove that your answers are correct — if you use a constructions given in class for one of your answers, you do not have to prove that the construction is correct but you should clearly show your work during the construction as part of your justification.

    { w ∈ {-,0,1}* : #(w) is a multiple of 4 }