CS151 lecture notes, Fall 1999
Week 10, Friday

Reading for Monday: Chapter 11

Correction: on page 122, the method printCard should print
the result rather than returning it:

  public static void printCard (Card c) {
    String[] suits = { "Clubs", "Diamonds", "Hearts", "Spades" };
    String[] ranks = { "narf", "Ace", "2", "3", "4", "5", "6",
		 "7", "8", "9", "10", "Jack", "Queen", "King" };

    System.out.println (ranks[c.rank] + " of " + suits[c.suit]);
  }

Compare that method to the one you wrote on Homework 10.
A little smaller?


Histograms
----------

A histogram is a collection (array) of counters.

Chapter 10 shows a histogram of the contents of an array

Each element of the histogram is a count of how many
elements of the array fall into the given range.

Here is a simpler version of the thing in the chapter:

Given an array of integers, generate a histogram with
10 counters.

The 0th counter says how many zeros there are
The 1th counter says how many ones there are
...
and so on.

Assume we want 10 counters.

  public static int[] histogram (int[] a) {
    int[] hist = new int[10];
    for (int i=0; i<a.length; i++) {
      if (a[i] >= 0 && a[i] <=10) {
        int index = a[i];
	hist[index]++;
      }
    }
  }

As an exercise, write a method that take a string and
returns a histogram with 26 counters that tells how
many of each letter there are.


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.


CS231 plug
----------

cs231 picks up where this class leaves off.

Will be taught by Dale Skrien in the Spring.

Covers data structures and object-oriented programming.

It's not too late to sign up!

If you are thinking of being a CS major, cs231 is the
only class you can take in the Spring.