CSC151.02 2015S, Class 46: Binary Search Lab
============================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Exploring the search API.
* Lab.

Preliminaries
-------------

### Admin

* Continue partners!
* Review sessions Thursday at 9am, 1:15 pm, and 8pm.
    * A particularly good place to ask questions on today's lab :-)
* For office hours this week, check <http://rebelsky.youcanbook.me>

### Upcoming Work

* Quiz Friday: higher-order procedures, analyzing procedures, `assoc`, 
  and searching.
* Projects due next Tuesday.
* Exam 4 assigned next Monday, due following Monday.
* Lab writeup: Exercise 4.
  <http://bit.ly/151-2015S-lab46>
* No reading for Friday.  Friday will be project work time (after the quiz).

### Extra Credit Opportunities

#### Academic 

* CS Talks Wednesday.
* CS Talks Thursday.
* Diversity as Arbitrage: Silicon Valley and Asian America, Friday, 4:15,
  Bucksbaum 152.

#### Peer Support (Afternoon Section)

* Contra Dance. Friday, April 24, at 8pm in Main Hall.
* Dance Ensemble. Thursday 7:30; Friday 7:30; Saturday 7:30;
  Sunday 2:00.  Flanagan.  Get tickets!
* Titular head.

#### Miscellaneous

* Town hall April 23, noon or 7:30 p.m., "How we have conversations."

### Other Good Things (no extra credit)

* CS Pub Night Thursday 7:00-8:00 p.m.

### Questions

Exploring the search API
------------------------

    ;;; Procedure:
    ;;;   binary-search
    ;;; Parameters:
    ;;;   vec, a vector we're searching
    ;;;   key, the thing we're searching for
    ;;;   get-key, a procedure that extracts a key from an entry
    ;;;   may-precede?, a binary predicate (that tells you whether
    ;;;     the first argument can come before the second argument
    ;;;     in whatever ordering you're use)
    ;;; Purpose:
    ;;;
    ;;; Produces:
    ;;;
    ;;; Preconditions:
    ;;;    vec is not empty
    ;;;    vec is ordered by the column.  That is, for all "reasonable" i
    ;;;       (may-precede? (get-key (vector-ref vec i))
    ;;;                     (get-keyu (vector-ref vec (+ i 1))))
    ;;; Postconditions:
    ;;; Practica:
    ;;;    (binary-search campus-events-by-name "Contra Dancing"
    ;;;    (binary-search campus-events-by-location "Main"

Notes:

* We use a vector, rather than a list, because we can quickly get any
  element of a vector.  And binary search requires "look in the middle"

If it helps, here's a set of data, organized by event name

    ; Each event has name, location, date, expected audience
    (define campus-events-by-name
      (vector (list "Contra Dancing" "Main" "2015-04-24" 60)
              (list "Convo-Memory" "JRC 101" "2015-04-22" 100)
              (list "Diversity as Artibrage" "Bucksbaum" "2015-04-24" 6)))
    (define campus-events-by-name
      (vector 
       (list "Diversity as Artibrage" "Bucksbaum" "2015-04-24" 6)
       (list "Titular Head" "Harris" "2015-04-25")
       (list "Convo-Memory" "JRC 101" "2015-04-22" 100)
       (list "Contra Dancing" "Main" "2015-04-24" 60)))

Lab
---