CS115 lecture notes, Spring 1999
Week 11, Friday

Quiz Monday on Chapter 10

Homework topics:

0) elements and indices

   indices are integers (or integer expressions) used to
   indicate on of the elements of an array

   the elements of the array are the value _in_ the boxes

1) RANGE:  sometimes when I say "range" I mean a range of
   values; sometimes I mean a range of indices.  It's confusing.

2) Recursion:  remember the leap of faith

  public static int totalWorker (int[] a, int low, int high) {

    // if the range only contains one element, the total is
    // equal to that element
    if (low == high) return a[low];

    // otherwise, break the array into two pieces and find
    // the total in each half
    int mid = (low + high) / 2;

    // actually, this method will work with any value of
    // mid between low and high-1
    int total1 = totalWorker (a, low, mid);
    int total2 = totalWorker (a, mid+1, high);

    // on the way back from the recursion is where the actual
    // addition takes place
    return total1 + total2;
  }

Draw a tree diagram showing how this works for an array
with 5 elements.

If this didn't work, how would you debug it?

1) Add a print statement at the beginning to print
   the parameters.  The result is sort of like a stack
   diagram, although it is a little more confusing.

2) Start with a smaller array!


Workers and wrappers
--------------------

totalWorker is called a worker because it actually performs
the computation (unlike the wrapper we are about to see).

It is also a very general form of the method, since it can
find the sum of any range of the array.

Most of the time, though, we don't want the most general
form; we just want to add up _all_ the elements of the array.

Of course, we can do that easily:

    int total = totalWorker (a, 0, a.length-1);

But it is clumsy.  Instead, we write a simple method called
total, that takes a single parameter, and that invokes totalWorker

  public static int total (int[] a) {
    return totalWorker (a, 0, a.length-1);
  }

It's called a wrapper because it encapsulates the single line
of code.

Also sometimes called a veneer, because it is a thin covering
that improves the appearance of a coarse underlayer.


For loops and internal variables
--------------------------------

Be aware that if you declare a variable inside a loop, it
only exists inside the loop:

  public static int sum (int[] a) {
    for (int i = 0, int total = 0; i<a.length; i++) {
      total += a[i];
    }
    return total;   // VARIABLE UNDECLARED
  }


Da plan
-------

Quiz on Monday.

Skipping Chapter 11.  Going to Chapter 12 next week.

One more assignment out next Wednesday, due May 5.

I will be away from May 1-4.  No class Monday 3 May.

cs231 picks up where this class leaves off.

Covers data structures and object-oriented programming.

It's not too late to sign up!