• Pick partners (or sit wherever)!
• Food! (more or less)

Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Notes from the Prologues.
  • Extra Credit.
  • Project Planning.
  • Questions.
• The problem of sorting.
• An object-oriented approach.
• Testing our sorting algorithm.

Preliminaries

Admin

• Office hours
  • Normal this week (MThF 1:45-3:15; walking 1:15-1:45)
  • I have no idea where I'll be during class prep times. Email me.
• I've added a variety of questions and answers to the exam. (Yes, it takes time to do so. I think it's worthwhile.)
• I've slightly cleaned up the eboards from Wednesday and Friday since so many people could not attend those classes.

Upcoming Work

• Exam 1 due Thursday.
  • Required prologue due tonight!
    • Yes, I can send you your prologue.
  • Required epilogue due Friday night.
• Reading for Tuesday:
  • Sorting Basics
  • The reading recaps and extends what we'll discuss in class today.

Notes from the Prologues

• Please don't write "suck up" answers on the prologues. E.g., "Oh, this question will give me the opportunity to learn much more about an important topic." (paraphrased)
• Many of you are saying that you should write average before writing the tests. But that's backwards. If you write the tests first, and think about the corner cases, you'll be much more likely to understand likely problems.
• You should have learned from an early homework that you can't just add up the values and then divide for the averaging problem; integer (or long) overflow will kill you.
• Loop invariants are a way to think more carefully about the state of the program while it is running. (They are also useful for proving things correct.) In general, we'll use pictorial loop invariants for arrays, but also try to write them formally.
  • When describing the values in an array, we may use a series of question marks to indicate that we know nothing about the values in the part of the array.
• In general, Big-O should be intuitive if you think about how algorithms work.
  • If you have to shift the elements in an array, that shifting will generally take O(n) steps
  • If you have to get the ith element of a linked list, that will take O(i) steps.

Good Things to Do

• Vote! (Only if you are a US Citizen and are interested in making your vote count more than it would in your home state.)
  • You can register at the polls
• JRC 101 today and Harris tomorrow (10 am to 4 pm)

Extra Credit

• Don't forget that you can suggest things

Academic

• BCC Faculty Chat, Tuesday, October 14, 7pm
• Thursday Extras, 4:30 p.m. Thursday, October 16, Grad School in CS
• CS Table Friday (Day PDR): Reports from GHC

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music.
  kdic.grinnell.edu
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• Soccer Tuesday afternoon at 4pm vs. Cetnral
• Soccer Saturday at 11am and Sunday at 11am

Project Planning

Question: In the second half of the semester, you will do a project. There are three possibilities right now.

• Set up Ushahidi for someone else on campus.
• Write a JSON parser.
• Build something that creates sport schedules. (We even have a client for this one.)

We'll do a quick discussion and then come back to the question immediately after break.

• JSON parser
  • Uses strings. Yay!
  • But solved many many times.
• Sam should think about separate projects for separate groups.

Questions

The problem of sorting

• What does it mean to sort?
  • To put things in a specific order
  • The things are usually in a data structure or ADT
    • Array
    • List (linked)
    • Vector
    • Characters in a string
  • What does a sort method normally return
    • The same data structure or ADT, although now sorted
    • It could be the same thing, now mutated, or it could be a new one

• Issues

  • Do we rearrange elements in place or create a new object?
  • Is it meaningful to sort one-element or zero-element arrays? (Sam usually says "yes, why not?")

  public interface Sorter { /**

  • Sort an array in place. *
  • @pre
  • The comparator should be applicable to all of the values
  • in whatever.
  • @post
  • For every j, 0 < j < whatever.length
  • order.compare(whatever[j-1],whatever[j]) <= 0
  • The resulting array is a permutation of the original array. */ public void arraySort(T[] whatever, Comparator order); } // Sorter

• With only the "it's sorted" postcondition, the following algorithm meets the requirements

  for (int i = 1; i < whatever.length; ++i)
    whatever[i] = whatever[0];
  

An object-oriented approach

• Interface, so we can build different sorters.
• The comparator is an object (a functional object, but an object)

Testing our sorting algorithm

    public void assertSorted(T[] whatever, Comparator<T> order)
    {
       for (int j = 1; j < whatever.length; j++)
         {
           if (order.compare(T[j-1],T[j]) > 0)
             fail("Order failed at position " + j);
         } // for
    } // assertSorted

    public Comparator<Integer> normalIntComparator = 
      (x,y) -> (x.compareTo(y));
    public Comparator<Integer> closerToZero =
      (x,y) -> { if (Math.abs(x) < Math.abs(y))
                   return -1;
                 else if (Math.abs(x) == Math.abs(y))
                   return 0;
                 else
                   return 1;
               }

    @Test
    public void testEmpty()
    {
      Integer[] empty = new Integer[0];
      arraySort(empty, normalIntegerComparor);
      assertSorted(empty, normalIntegerComparor);
    } // testEmpty

    @Test
    public void testFoo()
    {
      Integer[] foo = new Integer[] { 11, 1, 2, 5, 0, -4, 6 } ;
      arraySort(foo, normalIntegerComparator);
      assertSorted(foo, normalIntegerComparator);
    } // testFoo

    @Test
    public void testOne()
    {
    }

    @Test
    public void testTwo()
    {
    }

    @Test
    public void testThree()
    {
    }