Tutorial 9      Lecturer: Ray Reiter          Tutor: Andria Hunter
==========                                  990310 Wed@1pm

CSC148, Spring 1999                            Tutorial notes,  T9
==================================================================

Topics:
------------------------------
  - A3 questions
  - recursive proofs

Information for you
-------------------------------------------------------------------------------

  - In lectures, I have covered through slide [286], recursive inOrder
    print.  The other instructors seem to be all over the map, but all
    of us have covered recursive code.

  - My class requested that we show them more proofs of correctness
    for recursive code, so the students should be interested in it.

Questions on A3
-------------------------------------------------------------------------------
  - Please read the A3 handout if you haven't already.  (And please
    return any extra handouts you have to me ASAP.)

  - Student should have started on A3; if they haven't, they had better
    do it pretty soon.  It's not a lot of code to write, but if they
    don't understand recursion they'll be in major trouble.

  - Tell them to do the online homework on recursion!

Recursive proofs
-------------------------------------------------------------------------------
  - Please develop some proofs of correctness for recursive code.
  - Review the format for inductive proofs that we use in 148.
  - Make sure that they develop the proofs with you!  It will not help them
    if you just show it to them.  It may be painful waiting for them to say
    things, but it's really important.  Grin at them, it usually helps.
  - Remind them that induction parallels recursion beautifully.  In an
    inductive proof for recursive code, the base cases are used to prove the
    degenerate cases correct, and the inductive step is used to prove the
    recursive cases correct.
  - I've included the sample recursive code from last week.  Those would be
    good to prove correct, especially any tree code.
  - I recommend both developing and proving the numPositive() method.  It's
    pretty simple, but the inductive step requires two cases, and you need
    strong induction because you don't know the size of the subtrees.
  - Tell them that in order to prove code correct, they need to explain what
    happens in the code -- for some reason this is something that they have
    trouble with.
  - Doing something with two base cases would be good -- maybe Fibonacci.
    You can also tell them it's a terrible algorithm because the running time
    is exponential.  (Explain why.)
  - If they find these easy, you could have them try to prove question 9 (on
    palindromes) from the 1994 exam correct.  It's a bit tricky because the
    code is in Turing, and they're not used to thinking in terms of an
    algorithm rather than Java.  Note that 'word (*)' means the last
    character in string 'word'.  Also, in Turing, strings indices start at 1
    rather than 0.

Example: Size of a tree
-----------------------

Define the SIZE of a tree to be the total number of nodes in a tree (number
of leaves + number of internal nodes). Write a method to calculate the size
of a tree.

// for a binary tree of integers.
class TreeNode {
    public int data;
    public TreeNode left, right;
}

public static int size (TreeNode root) {
    if (root == null)
        return 0;
    else 
        return 1 + size(root.left) + size(root.right);
}


Example: Counting the number of positive numbers in a tree
----------------------------------------------------------

public static int numPositive (TreeNode root) {
    if (root == null)
        return 0;
    else if (root.data > 0)
        return 1 + numPositive(root.left) + numPositive(root.right);
    else
        return numPositive(root.left) + numPositive(root.right);
}



Example:  Printing a singly linked list in reverse order
--------------------------------------------------------

This may be a good one to do if you covered iterative versions of this
in your pointer tutorials.

class Node {
    public String data;
    public Node next;
}

public static void reversePrint (Node front) {
    // If the list is empty, there is nothing to print.

    if (front != null) {
        reversePrint(front.next);
        System.out.println(front.data);
    }
}


Example: Reverse a string
-------------------------

//  This is a recursive method which reverses a string.    
//  Note that the iterative version would be more efficient.  
//  But a smart compiler should convert to a loop behind the scenes.

public static String reverse (String s) {
 
    if (s.length() <= 1)
        return s;
    else 
        // I hope I got this right.
        // We want to pull out the substring from 1 to the end inclusive,
        // so that's s[1 .. s.length()-1] inclusive.
        // s.substring(a,b) returns s[a..b-1] inclusive, so we need
        // so we need to call s.substring(1,s.length()).
        return reverse (s.substring(1 .. s.length()) + s.charAt(0);
}