Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Signatures of search methods.
• Analyzing binary search.
• Testing binary search.
• Lab.

Preliminaries

Admin

• Maintain lab partners!
• Office hours
  • Normal (MThF 1:45-3:15; walking 1:15-1:45)
  • In the Grill 8:00-9:30 Wed and Fri
  • In my office 8:00-9:30 Thu

Upcoming Work

• HW 7 due tonight.
• Exam 2 distributed tomorrow. (GHC folks should look online at or after class time.)
• Reading for Wednesday:
  • Loop Invariants
  • There are links to Mr. Walker's readings on loop invariants at the end of the reading. You may want to look at those as an alternative approach.

Cool Things Coming to Campus

• Two versions of Anna Christie!
• Live Streaming of Verdi's Macbeth, Saturday at 11:55 a.m.
• Pop-up Exhibit, Thursday October 9th, all day in BCA 132

Academic

• Grinnell Prize Events this week.
• Artist Talk, Wednesday October 8th at 4:15pm in BCA 152 Rewriting the Application Programming Interface (API) for Art Making
• BCC Faculty Chat, Tuesday, October 14, 7pm

Peer Support

• Ajuna's Radio show Mondays at 8pm. Listen to African music
• Ezra's Radio show Thursdays at midnight. Radio melodrama.
• GC Anna Christie (Mira did costumes), Thursday night, Satuday night, Sunday afternoon

Miscellaneous

Questions

For the interface, should it use a Web client and prompt for the site?

Yes

Can it just do one iteration through the list?

Yes

Can we return a new UshahidiTestingClient or something similar for extra 2?

Yes

Can we do without the array for extra 2?

Yes

Don't we need clients for extra 2?

Yes

Designing search methods

• Goal: Write general code
  • Generics! Work with any type
  • Functions as parameters

• A typical signature

  public static <T> T search(T val, List<T> values, Predicate<T> ok)
  

• Do we need both the value and the predicate?

  public static <T> T search(List<T> values, Predicate<T> ok)
  

• If we're doing binary search, don't we need an order?

  /**
   * Search for val in vals.  Return the index.
   *
   * @pre
   *   vals is sorted by order.  order.compare(vals.get(i),vals.get(i+1)) <= 0 for all reasonable i
   */
  public static <T> int binarySearch(Vector<T> values, Comparator<T> order, T val)
  

Analyzing binary search

    binarySearch(val, values, order
       return binarySearch(val, values, 0, values.length, order)

    // binary search in a subarray
    binarySearch(val, values, lb, ub, order)
      if (lb >= ub)
        thrown an exception
      else 
        mid = average(lb,ub)
        if order.compare(values[mid], val) < 0
          return binarySearch(val,values, mid+1, ub, order)
        else if order.compare(values[mid], val) > 0
          return binarySearch(val,values, lb, mid (or mid-1), order)
        else
          return mid

How long does this take?

    time(n) = c + time(n/2)
    time(1) = d // no recursion

Given a recurrence relation that defines a function, you can write the function in "closed form" with not recursion. Read the rest in the reading. We'll do more later.

Testing binary search

Lab

What do you think about using the following method from java.util.Array?

static int[] copyOfRange(int[] original, int from, int to)

How do we test for an exception?

    boolean failed = false;
    try
      {
        CodeWeExpectToFail;
      }
    catch (Exception e)
      {
        failed = true;
      }
    if (!failed)
      fail("Did not throw an exception in ...");