============================================================-

Topics to discuss

• How do I get CSC207.xml on my laptop?
• Can we talk about how we might think about the average problem?
• Making random arrays (for problem 1).
• Anonymous functions and comparators.
• Anonymous inner classes and comparators.
• Generics
• More on loop invariants.

How do I get CSC207.xml on my laptop?

Open a terminal window.

    $ cd Desktop
    $ sftp username@ftp.cs.grinnell.edu
    Password: MathLAN Password
    sftp> cd /home/rebelsky/share/
    sftp> get CSC207.xml$a
    sftp> bye

Open Eclipse and Import

How do I think about average?

• First big issue: Worry about overflow or underflow. (Particularly bad with Long.MAX_VALUE.)

• Strategy: Think back to how you solved the "average two numbers correctly" How do we safely average a and b, assuming that they are both positive?

  a/2 + b/2
  

• Check! Average 3 and 3. 3/2 + 3/2 = 1 + 1 = 2.

• What else might we do?

  a + (b-a)/2
  

• Only works if the are both positive. Need to check that it rounds down. It doesn't: Suppose a is 1 and b is 0. The average is 0. But 1 + (-1/2) = 1 + 0 = 1

• Let's go back to the first strategy

  a/2 + b/2
  

• Issue: If both are odd and positive we are off by one

  if ((a % 2 == 1) && (b % 2 == 1) && (a >= 0) && (b >= 0))
    return a/2 + b/2 + 1
  else
    return a/2 + b/2;
  

• Also need to think about other special cases. It will be long and ugly, but sometimes it's best to start with code that's correct but ugly.

• Slightly generalize: What if we have three elements?

  a/3 + b/3 + c/3
  

• Example (average 4, 3, and 8):

  4/3 + 3/3 + 8/3 = 1 + 1 + 2 = 4; off by one
  
  
  4/3 + 4/3 + 7/3 = 1 + 1 + 2 = 4; off by one
  
  
  3/3 + 3/3 + 3/3 = 1 + 1 + 1 = 3; correct
  
  
  5/3 + 5/3 + 7/3 = 1 + 1 + 2 = 4; should be 5; off by 1
  
  
  5/3 + 5/3 + 8/3 = 1 + 1 + 2 = 4; should be 6; off by 2
  

How do I make a random array?

I really mean "how do I make a lot of random arrays"?

We could look at the sorting code.

"A lot" probably means I should use a loop

    Random generator = new Random();
    for (size = 3; size < 10000; size = size + generator.nextInt(100))
      {
        int[] arr = new int[size];
        for (int i = 0; i < size; i++)
          {
            arr[i] = generator.nextInt();
          } // inner for
      } // outer for

• For average, you need to be a bit more careful in how you make the "random" arrays, given that you have to know what the average is supposed to be.

Kitchen Sink

Comparators.

• strcmp and strcasecomp in C?

• Java suggests that when you have multiple "things" that are similar and you might want to substitute one for the other, you build an interface.

  public interface StringComparator
  {
    /**
     * Compare str1 to str2.  Return a negative number if
     * str1 comes before str2, zero if they are equal, and
     * a positive number if str1 comes after str2.
     */
    public int compare(String str1, String str2);
  } // interface StringComparator
  

• We want to generalize this.

  public interface THINGComparator
  {
    /**
     * Compare str1 to str2.  Return a negative number if
     * str1 comes before str2, zero if they are equal, and
     * a positive number if str1 comes after str2.
     */
    public int compare(THING str1, THING str2);
  } // interface THINGComparator
  

• Use language feature: Generics!

  public interface Comparator<T>
  {
    /**
     * Compare val1 to val2.  Return a negative number if
     * val1 comes before val2, zero if they are equal, and
     * a positive number if val1 comes after val2.
     */
    public int compare(T val1, T val2);
  } // interface Comparator<T>
  

• We want to build one of these things. Let's say an IntegerComparator

  public class StandardIntegerComparator
    implements Comparator<Integer>
  {
    public int compare(Integer val1, Integer val2)
    {
      if (val1 < val2)
        return -1;
      else if (val1 == val2)
        return 0;
      else 
        return 1;
    } // compare(Integer, Integer)
  } // class StandardIntegerComparator
  

• Alternative

  public class StandardIntegerComparator
    implements Comparator<Integer>
  {
    public int compare(Integer val1, Integer val2)
    {
      return val1.compareTo(val2);
    } // compare(Integer, Integer)
  } // class StandardIntegerComparator
  

• Later

  Comparator<Integer> comp = new StandardIntegerComparator();
  sort(stuff, comp);
  

• Make the programmer more efficient (anonymous inner classes)

  Comparator<Integer> comp = new Comparator<Integer>()
    {
      public int compare(Integer val1, Integer val2)
      {
        return val1.compareTo(val2);
      } // compare(Integer, Integer)
    };
  sort(stuff, comp);
  

• Make the programmer even more efficient (anonymous functions)

  Comparator<Integer> comp = 
    (val1,val2) -> { return val1.compareTo(val2); }
  sort(stuff, comp);
  

• And more

    (val1,val2) -> val1.compareTo(val2);
  

Loop Invariants

Issues: Problems are getting hard -> Programmers screw up.

• Usually subtleties in dealing with arrays
• A way to think about the problem that increases the odds that
  • We write correct code
  • If we write correct code, we are better able to identify where it is incorrect
• We think about
  • "What is the state of the system?"
  • "How do I get closer to achieving the goal of the function/algorithm?"
  • "How do I know that I have the correct answer when I'm done?"
• Draw pictures!