CS115 lecture notes, Spring 1999
Week 12, Wednesday

Pick a volunteer to do the evaluations.

Using data as indices
---------------------

In Chapter 12, one of the exmaples uses the rank and suit of a card as
indices into the arrays that contains the names of the ranks and
suits.

This example shows something common, which is the use of
a datum as an index.

The same thing happens when you make histograms (as in
Section 10.11)


Making histograms
-----------------

histograms are useful for a variety of uses (like
identifying poker hands)

Calculating them is also an interesting exercise.

A histogram is an array of counters.  Each counter
indicates how often a particular value, or range of
values occurs.

Version 1
---------

	create an array of counters

	traverse the array

		 index = ith element of the array
		 increment the counter indicated by index

Translate this pseudocode into Java.


Version 2
---------

Of course, the elements of the array include only odd
numbers, so we know that all the even-indexed counters
will be zero.

We can save space by only keeping counters for the odd
elements.

That means that we can't use the data itself as an index,
since the ith counter is no longer at the ith position of
the array.

Instead, we need a mapping between the data (elements)
and the counters.

The count of how many 1s should be in the 0th counter
The count of how many 3s should be in the 1th counter
The count of how many 5s should be in the 2th counter

Is there a pattern here we can take advantage of to
map data onto indices?  Yes.

		 index = ith element of the array / 2

Remember that since we are doing integer division,
everything gets rounded down.

Version 3
---------

What if we want to have a range of values in each bucket.

Same idea, we need a mapping from data values onto buckets.

Section 10.11 develops an approach to doing that.


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.


Bisection search, part two
--------------------------

For next time, read Section 12.7 and write an iterative
version of a bisection search (on paper).