cs231 Lecture Notes
Week 2, Friday

Analysis of Algorithms
----------------------

Is mergeSort faster than the simple sort we saw last time
(which is sometimes called selection sort)?

What do we mean by faster?

One possibility is run time (how do we deal with different machines)?

   obviously running the program on two different machines isn't
   fair, but it's possible that

   On machine A, one algorithm is faster than the other, but

   On machine B, the other algorithm is faster!

So, the usual practice of computer scientists is to evaluate
algorithms by counting the number of ABSTRACT OPERATIONS.

By "abstract operation" I mean something less concrete than
the simple operations computers perform.

Instead, for each kind of algorithm, we usually choose the particular
operation that we expect to take most of the time.  For example,

1) text manipulation: count integer operations
2) matrix arithmetic: count floating-point operations

   sometimes, the number of multiply-adds

3) sorting: count the number of comparisons

This decision is sometimes a little arbitrary.

Next problem:  The number of operations depends on the size of
the problem (how big is the text, or the matrix, or the array we
are sorting).

So what we really want is a function

   number of ops = f (problem size)

Next problem: problem size is not always one dimensional

     (matrixes are 2 or 3 or more dimensional)

In this case (sorting) life is easy.

Ok, so let's figure out the number of COMPARISONS as a function
of the SIZE OF THE ARRAY (a.k.a. number of elements).

Simple sort:

    public void sort () {
	for (int i=0; i<cards.length; i++) {
	    int j = findLowestCard (i, cards.length-1);
	    swapCards (i, j);
	}
    }

    public int findLowestCard (int low, int high) {
	int winner = low;
	for (int i=low+1; i<=high; i++) {
	    if (cards[i].compare (cards[winner]) < 0) {
		winner = i;
	    }
	}
	return winner;
    }

We call findLowestCard n times.

The first time it calls compare n times.
The second time it calls compare n-1 times.

etc.

What's the total?


Mergesort:

No comparisons get done on the way down.

At the bottom level of the tree, we have n decks with 1 card each.

It takes n/2 comparisons to merge them.

At the next level, we have n/2 decks with 2 cards each.

It takes 3 * n/2 comparisons.

Then n/4 decks with 4 cards each.

It takes 7 * n/4 comparisons.

Then    15 * n/8
then    31 * n/16

Ok, we need to simplify this!

First, recognize that the numerator is pretty close to a power of
two.  We'll round everything up, so our analysis will be a little
pessimistic.

        2 * n       
        4 * n/2
        8 * n/4
Then    16 * n/8
then    32 * n/16

Now we see the pattern!

Each level involves (a little less than) 2n comparisons.

How many levels are there?


Precomputing Histograms
-----------------------

Last time we talked about using histograms to make it easier
to classify hands.

We need those histograms to be precomputed and then used by
many different methods.

Instance variables are "visible" from any method, so they
are a reasonable mechanism.

We could compute them at the time the Deck gets created, but
that might be wasteful.

    Card[] cards;
    int[] suitHist;
    int[] rankHist;

Then we can write a method that initializes the instance varaible
(and does the corresponding computation) later...

    public void makeSuitHist () {
	suitHist = new int[4];

	for (int i=0; i<cards.length; i++) {
	    suitHist[cards[i].suit]++;
	}
    }

It's ok to postpone initializing some of the instance variables,
although sometimes it makes things tricky.

For example, we have to make sure that we make the rankHist
before calling isPair, and make sure we make the suitHist before
calling isFlush.


Invariants / preconditions
--------------------------

Invariant:  something that is provably true at some point in a program

Precondition: a condition that a method requires to be true when it
	      executes, in order to work correctly

Postcondition: a condition that is provably true at the end of a method
	       (provided that the precondition is satisfied)

What are the preconditions for isFlush?  isPair?  isStraightFlush?

What should a method do about its preconditions?

1) fail: the method says, "if you (the caller) don't satisfy my
   preconditions, I simply won't do what I said I would do."

   Often, that means generating a run time error (for example,
   if rankHist is null)

   Sometimes, it means just not doing the right thing.  For example,
   what does findBisect do if the deck is not actually in order?

2) check: some preconditions can be checked cheaply

   (rankHist != null)

   some can be checked, but they are a little expensive

   (is the array sorted)

   some cannot be checked (for various reasons).

   Obviously, this last group is the most unpleasant.

3) eliminate (minimize)

   it is often a good idea to both check and correct missing
   preconditions.  For example:

   if (rankHist == null) makeRankHist ();

PRECONDITIONS ARE THE MOST IMPORTANT THINGS TO INCLUDE IN COMMENTS.

The comments at the beginning of a method are like a contract.
They describe what the method does, but they include a catch

     The method is only guaranteed to work if the preconditions
     are satisfied.

Please read Appendix C.3, pages 496 through 501 for more
information about Proving Programs Correct.