CS231 lecture notes, Fall 1998
Week 3, Thursday

Reading: Standish Chapter 4 (skim 4.4)

Hand back quiz -- discuss List traversal idiom:

      ListNode node = head;
      while (node != null) {
        // do something here
	node = node.next;
      }

    for (ListNode node = head; node != null; node = node.next)
    {
      // do something here
    }

IMPORTANT: you cannot begin to act until you have memorized your lines!

You cannot begin to program until you have learned the syntax!

Quiz #2 will be on Monday; it will involve another list traversal,
and you'd better use the list traversal idiom...

      
Continue discussion of product (int m, int n).

public int product (int m, int n)
{
	if (m == n) return m;
	int middle = (m+n) / 2;
	return product (m, middle) * product (middle+1, n);
}

a) precondition m<=n

Who is responsible for preconditions?  Caller or callee?

If mid = (m+n)/2, can we prove that m<=mid and mid<=n?

Trivial for reals, or course; not as obvious for integers.

b) call graph looks like a tree

Example: product(5, 10)
          /          \
  product(5,7)     product(8,10)
   /       \       /          \ 
(5,6)     (7,7)  (8,9)     (10,10)


Reverse a List
--------------

NOTE:  The book does something I don't really like here,
which is that they put all the methods in the List class,
even the ones that are operating on ListNodes.  For this
week, I am going to follow their lead, in order to avoid
confusion, but one of the things on the next assignment
will be straightening out their mess.

Let's start with a recursive version of concat.  This
version is a little different from the solution I wrote to
the last assignment.

  public ListNode concat2 (ListNode node1, ListNode node2)
  {
    if (node1 == null) return node2;
    node1.next = concat2 (node1.next, node2);
    return node1;
  }

This is an object method of the List class, but it does not do
anything to the List object on which it is invoked, only on the nodes
it is passed as arguments.  It returns a pointer to the first node
in the concatenated list.

It takes a while to suss out this program, but believe it or
not, it is an example of a common _recursive_ idiom for traversing
a list.

Now, in order to reverse a list, we need a veneer and a helper
method:

  public ListNode reverse_helper (ListNode node)
  {
    if (node == null) return null;

    ListNode tail = node.next;

    node.next = null;
    return concat2 (reverse_helper(tail), node);
  }

reverse_helper takes a ListNode (the first of several, usually)
and returns a ListNode.  Notice that there is some ambiguity
when you have a ListNode object -- are you treating it as a single
node or as the first element of a list.  The answer is often
subtle.

1) although reverse_helper is also an object method of the List class,
it does not read or write any List object instance vars

2) the base case is a null list, which is defined to be its own reverse

3) after the base case we know the list has at least one elt.

4) tail refers to the rest of the list (other than the first elt),
   which may be a null list

5) if we reverse the rest of the list, then all we have to do is
   add the first node to the end of the reversed list and we're
   done (that's the leap of faith interpretation).

6) we have a method (concat) that appends one list on the end of
   another

7) don't forget to return a reference to the result



  public void reverse2 ()
  {
    head = reverse_helper (head);
  }


1) reverse2 is an object method of the List class that actually does
   something to the List object

2) most of the work is done in the helper function; reverse2 is just
   a veneer