CS151 lecture notes, Fall 1999
Week 13, Monday

Reading: Chapter 12 (quiz wednesday)

Hand back exam
--------------

Common problems:

1) definition of logical error

   The different kinds of errors are confusing because strictly
   speaking they are not different kinds of errors.  They indicate
   _when_ the error gets caught

   1) compile time (by the compiler)
   2) run time (by the run time system)
   3) after run time (by the programmer)

2) why different algorithms for humans?

   1) different basic operations
   2) humans can manipulate 5-7 things simulaneously
   3) computers only 2 (although they can store many more)

   Definition of algorithm still sketchy.

3) Checking the histogram:  check h[i] != 0 AND h[i] != 2
                                             &&

BONUS QUESTION:
Analysis of bisection search
----------------------------

How many comparisons do you have to do in a linear search?

    One for each element of the array.
    If array size is n, there are n comparisons.

How many comparisons do you have to do in a bisection search?

    One each time we divide the array in half.

    How many times can we divide the array (size n) before
    we get to one?
    
    How many times do we have to double 1 before we get to n?

    What power of 2 is n?

    What mathematical function answers that question?


Implementation
--------------

It's common to ask things like "How is a deck of cards implemented
in this program?" which means "What data structures or objects are
used to represent a deck of cards."

In general, there are many possible implementations for a given
concept or real-world object.  Many of them are functionally
equivalent, but might have performance advantages or might lend
themselves to better quality programs.

Examples:

concept			implementations

bounding box		four integers
			Rectangle object

deck of cards		array of Cards
			Deck object

subdeck			array of Cards plus two integers
			a new Deck object with references that
			  are aliases of a subset of the original
			  Deck's cards
			a new Deck object with new Cards that are
			  (deep) copies of the original Deck's
			  cards

This week's assignment involves modifying last week's to use
a Deck object instead of an array of Cards.


The Deck object
---------------

It should come as no surprise that objects can contain arrays
as instance variables.  All the rules are the same:

1) you declare the instance variables before the methods

2) you initialize the instance variables in the constructor

3) every object with type Deck has its own copy of the instance
   variables


class Deck {
  Card[] cards;

  public Deck (int n) {
    cards = new Card[n];
  }
}

This simple constructor just allocates an array of references
(initialized to null), but no Cards!

It might be nice to offer another constructor (based on buildDeck)
that creates a fully-populated Deck:

  public Deck () {
    cards = new Card[52];
    int index = 0;
    for (int suit = 0; suit <= 3; suit++) {
      for (int rank = 1; rank <= 13; rank++) {
        cards[index] = new Card (suit, rank);
        index++;
      }
    }
  }

Now that Decks are full-fledged objects in their own right, it
is less decorous to implement subdecks with such an awkward
mechanism as an index range.  Much nicer to create proper
objects (I will give practical reasons later):

  public static Deck subdeck (Deck deck, int low, int high) {
    Deck sub = new Deck (high-low+1);
	
    for (int i = 0; i<sub.cards.length; i++) {
      sub.cards[i] = deck.cards[low+i];
    }
    return sub;
  }

Why high-low+1?

Consider the state diagram carefully to understand the behavior
of subdeck.

Remember: aliasing Cards is fine, as long as we NEVER change them.

	  (mention final keyword)

Mergesort
---------

Simple mergesort

1) split the deck in half

2) sort the halves

3) merge the halves

Is this faster than the traversal sorting we did before?
We'll analyze it next time and see.

Recursive mergesort

0) if the deck contains a single card, return it

1) split the deck in half

2) sort the halves (using mergesort)

3) merge the halves

Is this faster still?  We'll see.

The hardest part of implementing mergesort is merge.
Make sure you test merge rigorously before you write
the recursive version, or you will be unhappy.