CSC152 2005F, Class 30: Arrays and Applications Thereof

Admin:
* No readings.  Sorry.
* New homework strategy: Daily "small" assignments due before next
  class.

Overview:
* Array basics.
* An example: Sum
* More about main
* Another example: Fibonacci 
* Using arrays to improve Fibonacci

Arrays!
* Many problems involve computation with collections of data
* How do we represent collections?
* At least three ways in Scheme
  * List
  * Vector
  * Pair structure (tree)
  * Files
* We will consider many ways to collect data in Java
* Start with arrays
* Basic concepts:
  * Philosophy: A way to organize a collection of data in
     which you have "random" access (access by numeric index)
  * Applications
  * Methods
    * Construct (giving length)
    * Extract any item from the vector (vector-ref in Scheme)
    * Change any item in the vector (set the value at a 
      particular index) (vector-set!)
    * Get the length
  * Implementation
    * Allocate a contiguous area of memory and pretend to
      divide it up for the cells of the vector/array
    * If the area of memory starts at m and each item takes
      w space, item i is at m+i*w
* Notes
  * In most languages, it requires extra computation to extend

In Java:
* Syntax for declaring variables
  * Each array has a base type (e.g., "an array of integers";
    "an array of strings"; "an array of MadLibs")
  * Arrays are homogeneous (although polymorphism works)
  * Format
        TYPE[] NAME;
  * Examples
        int[] grades; // Grades is an array of integers
        TextBlock[] foo; // foo is an array of textblocks
* Syntax for for main operations
    * Construct (giving length)
      * Format
        NAME = new TYPE[SIZE];
      * Examples
        grades = new int[5];
        foo = new TextBlock[23];
      * Default contents is 0/null
        * grades contains 0,0,0,0,0
        * foo contains null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null,null
    * Construct and initialize
       NAME = { VAL1, VAL2, VAL3, ..., VALN };
       * Examples
         grades = { 90+5, 80, 102, 31, 100 };
         foo = { null, new TextLine("Hello"), null, null };
       * You must specify all the elements
      * AND THE SIZE CAN'T CHANGE
      * Example, revised
        TextBlock[] foo = { null, new TextLine("Hello"), null, null };
    * Extract any item from the array (vector-ref in Scheme)
      NAME[pos]
      pen.println("The first grade is " + grades[0]);
      for (int i = 0; i < grades.length; i++) {
        pen.println("Grade number " + i + " is " + grades[i]);
      } // for
    * Change any item in the array (set the value at a 
      particular index) (vector-set!)
      NAME[pos] = NEW_VALUE;
      for (int i = 0; i < grades.length; i++) {
        grades[i] = grades[i] + 5;
      } // for
    * Get the length
      NAME.length

Problem: Given an array of doubles, vals, sum the values in vals
  * Strategy one: Recursion
        public static double sum(double[] vals, int pos)
        {
        }
  * Most programmers use for loops for processing arrays
        double total = 0.0;
        for (int i = 0; i < vals.length; i++) {
          total = total + vals[i];
        } // for
        return total;

To convert an array to a string, use
        java.util.Arrays.toString(nameOfArray)

ASSIGNMENT: Update the sum program so that it ignores non-numbers 
  entered on the command line
If I type 
        ji username.arrays.Sum 12 hello 13 goodbye
the output should be
        The sum of [12,13] is 25

---
Fibonacci numbers
Rules for computing Fibonacci numbers
        0th Fibonacci number is 1
        1st Fibonacci number is 1
        ith Fibonacci numbers is i-1st Fibonacci number + i-2nd Fibonacci numbers

        1,1,2,3,5,8,13,21...