CS151 lecture notes, Fall 1999
Week 10 Monday

What's an algorithm (review)
-------------------

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

It's mechanical, meaning that it can be executed without
intelligence, or understanding of what you are going.

Tends to be generative -- that is, it creates the solution
rather than just looking up solutions in a table.

Also,

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

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

Inventing algorithms is one of the most interesting and
challenging aspects of "programming", much more so than
"coding".

For example, one of the reasons I asked for you birthdays
was to find out if two people in the class had the same
birthday.

Question: what's a good algorithm for taking a stack of
30 papers and comparing each birthday to the others?

1) bad answer: pick up the first page.  Compare it to
   the other 29.  Repeat for all 30.

2) better answers?


Notice that your answer is constrained by the kinds of
operations people can perform easily.  For example,
we can only hold two pieces of paper at a time, or we
can lay out 5-6 on a table, but we cannot easily look
at 30 things at once.

Keep that in mind as we start to design algorithms for
computers: what are the basic operations that we can
perform?


Arrays
------

An array is a set or collection of values, sort of like an
object, except:

  All the values have the same type.

  The values are indicated by number, rather than name.

For every primitive type, there is a corresponding array
type:

	int	int[]	  (array of int)
	double	double[]  (array of double)

You can declare array variables in the usual way:

    int[] count;
    double[] doubleArray;

Just as with objects, these declarations create references
to arrays.  To allocate space for the array itself, you have
to use the new command:

   count = new int[4];
   doubleArray = new double[size];

The number in the square brackets is the size of the array.

It can be any integer expression.

By default, the elements of the array are initialized to zero.


Elements of an array
--------------------

The elements are numbered from zero.

count[0] = 7;
count[1] = count[0] * 2;
count[2]++;
count[3] = count[3] - 60;

You can use any integer expression as an index.

If you use an index that is negative or >= size, you get
an ArrayOutOfBoundsException.

You can use loops to traverse arrays:

    int i = 0;
    while (i<4) {
      System.out.println (count[i]);
      i++;
    }

Example:

Given an array of doubles, a, how would you make a copy?

  double[] a = new double[3];
  double[] b = a;

This copies a reference to the array, which means that
a and b are now aliased.

To build a new array, we have to use new to allocate
space, and a loop to copy the elements of the array.

    double[] b = new double [3];

    int i = 0;
    while (i < 4) {
      b[i] = a[i];
      i++;
    }

Passing arrays as parameters
----------------------------

Good news.  Everything is the same as passing objects
as parameters.

1) A reference gets passed

2) Caller and callee have two references to the same object
   (aliasing)

3) Callee can modify the contents of the array.


Example:

  public static int banana (int[] a) {
    int i = 0;
    int grape = 0;
    while (i < a.length) {
      grape += a[i];
      i++;
    }
    return grape;
  }

  public static void main (String[] args) {
    int[] a = new int[10];
    // put values into the array

    System.out.println ("max = " + max2(a));   
  }

Hey, look!  The parameter to main makes sense, finally!


Traversals
----------

Different kinds of traversals:

ACCUMULATION

  public static int sum (int[] a) {
    int i = 0;
    int total = 0;
    while (i < a.length) {
      total += a[i];
      i++;
    }
    return total;
  }
	
COUNTING

  public static int frequency (int[] a, int p) {
    int i = 0;
    int count = 0;
    while (i < a.length) {
      if (a[i] == p) count++;
      i++;
    }
    return count;
  }

EUREKA: finding the first thing that satisfies a criterion

  public static int find (int[] a, int p) {
    int i = 0;
    while (i < a.length) {
      if (a[i] == p) return i;
      i++;
    }
    return -1;
  }		

EXTREME VALUE FINDING

  public static int max (int[] a) {
    int max = a[0];
    int i = 1;
    while (i < a.length) {
      if (a[i] > max) max = a[i];
      i++;
    }
    return max;
  }
	

How to generalize these things?
------------------------------

Specify a range of indices over which to sum/count/search.