cs230 Lecture Notes
Week 3 Tuesday

For today you should be working on Homework 1.  It's due
on Wednesday at 1:30pm.  There will be a box outside my
door.

I will be out of town Thursday morning, so no office hour.


Performance evaluation: selection sort vs. mergesort

Selection 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?



Abstract parameters
-------------------

array + 2 integers = one representation of a subdeck

subDeck method actually allocates a smaller deck (but not cards)



Object methods
--------------

Observation: lots of methods operate on a single object that
is passed as a parameter.

The object-oriented view of this is that you are invoking
a method "on" an object, or sometimes people say you are passing
a message to the object.

Either way, there is the notion that one of the parameters is
special.

OBJECT METHODS are an alternate syntax that makes the special
parameter invisible!

We've used a few object methods for built-in Java classes,
like string.charAt (int i)

When you invoke them, you invoke them "on" an object.

All the methods we have written have been CLASS METHODS.
You just invoke them.

Possible confusion:

	 Sometimes when you invoke a CLASS METHOD, you
	 specify the name of the class, as in

	 Card.printCard (...);
	 Math.cos (...);

How can we tell when we are invoking a CLASS or OBJECT method?


Ok, so how do we WRITE object methods?

1) leave out the word static

2) leave out the magic parameter


In that case, how do we refer to the magic parameter?

1) using the keyword this

   OR

2) implicitly!

Examples:

	printDeck and printCard

plenty more examples in Chapter 6!


-----

Homework 1 discussion

Multiple classes -- mapping between objects and real-world
concepts.

Disadvantage -- additional level of indirection between you
	     and the contents of the objects

	     syntax is more convoluted...

	     deck.length   vs.  deck.cards.length

Actually, that indirectness can be an advantage:

1) object method syntax mitigates the awkwardness

2) each object can control the management of its data

3) separation of interest between objects -- promotes
   reusability, reliability

More about this later.



Homework 2

Next step toward object-orientedness -- object methods.

Compare the syntaxes and see what's what.


Algorithms -- how to classify card hands.