CS151 lecture notes, Fall 1999
Week 11, Monday

Quiz 14

Homework hints
--------------

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.


Encoding and encryption
-----------------------

To encode means to create a mapping between an internal
representation and something in the outside world.

Should not be confused with encryption, which is a way
of transforming a message so that it cannot be transformed
back without the use of a secret key.

Java comes with a number of standard mappings.

They are not secret.

For example, if you saw the bit pattern 01100001, you
would not know how to interpret it, unless I told you it
was an integer, in which case you would know it was 97.

If I told you it was a character, you would interpret it
as the letter 'a'.

If I told you it was a double (and it was preceded by
56 zeroes), you would interpret it as an extremely small
number (roughly 1e-300).

The point of these examples is that the mapping is not
written down inside the computer anywhere.

It is implied by the operations we perform on these values.

When we do addition, we interpret the values as integers
or floating-point numbers and do different things accordingly.

When we print values, we translate them into human-readable
form according to the mapping.

The same thing is true of user-defined types (the Object types
we have been writing).

Except that we have to provide the methods that perform the
operations and generate the human-readable output.


Arrays of objects
-----------------

Keys ideas:

1) when you create an array of Object types, you get an
   array of null references

2) you have to use new (repeatedly) to actually create the
   objects.

   Card[] deck = new Card[52];

   deck[0] = new Card (0, 1);
   deck[1] = new Card (0, 2);

   The book 12.6 contains a loop that allocates
   52 different cards.

3) You can compose the syntax for accessing arrays and
   accessing instance variables.

   card[i].rank          the rank of the ith card

   suits[card[i].suit]   the name of the suit of the ith card

   Composition is cool, but of course you want to show restraint.