cs230 Lecture Notes
Week 3, Thursday

For today you should have read Chapters 10, 11 and 12
and prepared for a quiz.

Also, you should have started hw2 and maybe finished the
first part (splitting the Card class into a Card and a
Deck class).

For next time you should finish Homework 2.  For the
second part, you need to know about mergeSort, which is
the topic for today.

Quiz 3 solutions
----------------





























Sorting
-------

How do people sort things?

What people do is not usually an algorithm we
can express simply.

Suggestion: take advantage of symmetry.  Sorting is
remarkably similar to shuffling.

Selection sort:

    for (int i=0; i<deck.cards.length; i++) {
        // find the lowest card at or to the right of i
        // swap the ith card and the lowest card
    }



Mergesort
---------

Algorithm

1) divide

2) conquer

3) merge


Development

Incremental development of recursive method

1) write and test the helper methods independently

   (subdeck and merge)

2) make one recursive step and then use sortDeck to
   solve the subproblem

3) write the fully recursive version


Performance analysis
--------------------

In general, we want to express run time as a function
of problem size.

Run time might be in units of seconds, number of recursions,
number of operations, etc.

Problem size might be the size of an array or matrix, or
sometimes the total number of bytes of input.

In both cases, we have some choices to make before we can
even begin the analysis.

What operations should we count?

For sorting, we usually count the number of comparison operations.

We ignore operations that are considered "overhead", like
incrementing loop variables, method invocation overhead, or
allocating new objects.

How many comparisons for selection sort?


















How many comparisons for mergesort?
















Do the implementations have similar overhead?














hw01 feedback
-------------

Factorial:

1) many of you converted the parameter to a BigInteger
   and then used equals to compare to the BigInteger version of 1.

Why not:

    public static BigInteger factorial (int n) {
	if (n == 0) {
	    return BigInteger.valueOf (1);
	}
	return BigInteger.valueOf(n).multiply (factorial (n-1));
    }


Rational:


2) The minus sign can be either a binary operator or a unary operator!

    (um, a what now?)

    public static void negate (Rational r) {
	r.num = -r.num;
    }
 
3) Typecasting is tricky.

    public static double toDouble (Rational r) {
	return (double) r.num / r.den;
    }

    Does this work?  If so, why?  If not, why not?

	return (double) (r.num / r.den);

4) Classification of methods

   pure function
  
   modifier	

	(fill in method -- kind of modifier)

Exercise: rewrite add as a fill-in method.

Advantages of functions?


Advantages of modifiers?


Include the code that you use to invoke and test your
methods.

Please write your name in the upper-right corner and put
the sections in order.