CS151 lecture notes, Fall 1999
Week 9, Friday

Read Chapter 10 for Monday

Quiz 12

Review
------

0) every time you define a new class, you create a new
   object type

   0.5) to create an object use the new command

1) constuctors are special methods that initialize the
   instance variables of a new object

   1.5) when you invoke the new command, Java invokes
        one of your constructors

WARNING: the syntax for a constructor is a little weird,
and if you get it wrong, the compiler will not recognize
the fact that your method is a constructor.  In that
case, the error messages tend to be incomprehensible.

      a) no static
      b) no return type
      c) the name of the constructor is the same as the
         name of the class
      d) inside the constructor, you can use "this" to
         refer to the current object


Three ways to add
-----------------

functional

  public static Complex add (Complex a, Complex b) {
    return new Complex (a.real + b.real, a.imag + b.imag);
  }


modifier

  public static Complex accumulate (Complex total, Complex term) {
    total.real += term.real;
    total.imag += term.imag
  }


fill-in method

  public static Complex add (Complex a, Complex b, Complex c) {
    c.real = a.real + b.real;
    c.real = a.real + b.real;
  }


None of these is wrong; they have pros and cons.

1) we want to be able to reason about programs and "prove"
   them correct.  Functional programming tends to facilitate
   that, because the state of variables does not change over time

2) one problem with the functional addition is that it creates
   a new object every time you perform an addition

   int i = 0;
   while (i < n) {
     Complex term = ...;
     total = add (total, term);
   }

   Every time through the loop, the old total gets garbage
   collected and the new one gets allocated.

   We would expect the following to be more efficient:

   int i = 0;
   while (i < n) {
     Complex term = ...;
     accumulate (total, term);
   }

   It changes the value of total each time through, but never
   collects or creates objects.

3) The fill-in method has similar advantages (no object
   creation or collection), but is even more versatile, since
   we can put the result into an object without modifying
   either of the operands.

In general, I recommend functional programming, because

1) modifiers make code harder to read and debug

2) correctness is more important than efficiency

I won't go so far as to say that efficiency is not
important, but I will say this:

	   Truly significant performance improvements usually
	   come from better algorithms, not minor changes in
	   the implementation.

Think about performance when you choose an algorithm, then
forget about it while you get the implementation CORRECT,
then think about it again at the end, IF NECESSARY.


By the way...

What's an algorithm
-------------------

An algorithm is a general solution to a class of problems.

Example 1:

How to get out of a specific maze vs. how to get out of any maze

    Right, left, right.

    Follow the right-hand wall.

Example 2:

A table of solutions vs. a way to generate a solution

    Multiplication table

    Rules:  to multiply by nine, print n-1 followed by 10-n

Example 3:

Two ways of performing arithmetic with Time objects

1) add seconds to seconds, minutes to minutes, hours to hours
   if seconds or minutes overflow, fix them

2) convert time (base 60) to #seconds (base 2), then perform
   arithmetic in base 2 (which we can do in hardware) and
   convert back to a Time object


Characteristics of algorithms

1) they can be executed mechanically, without any understanding
   of what you are doing (as in the multiplication by 9)

2) there is usually more than one algorithm for any problem
   (as in the Time example)

3) there are usually many ways to implement a given algorithm
   (as in the Complex add example)