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

_Overview_

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

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

### Admin

* New partners!
* Review sessions Thursday at 9am, 1:15 pm, and 8pm.
* 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: Problem 4
  <http://bit.ly/151-2015S-lab46>
* No reading for Friday.  Friday will be project work time (after the quiz).

### Extra Credit Opportunities

#### Academic 

* Convocation TODAY, Erica Lehrer '92: Public Scholarship, Personal 
  Scholarship: the Work of Memory in Poland Today
* CS Talks Wednesday.
* CS Talks Thursday.
* Diversity as Arbitrage: Silicon Valley and Asian America, Friday, 4:15,
  Bucksbaum 152.

#### Peer Support (Morning Section)

* KY's radio show, "We Think We're Funny", 9-10pm Mondays.
* Julia's radio show, "The Hot Box".  Wednesday night/Thursday 
  morning 1:00-2:00 a.m.  
* Sunday at 2pm Orchestra in Herrick with Choir - Requiem
* Titular Head this weekend.

#### 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.
* Contra Dance April 24 in Main Hall.
* Dance Ensemble. Thursday 7:30; Friday 7:30; Saturday 7:30;
  Sunday 2:00.  Flanagan.  Get tickets!

### Questions

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

    ;;; Procedure:
    ;;;   binary-search
    ;;; Parameters:
    ;;;   vec, a vector of something
    ;;;   key, a value
    ;;;   get-key, a unary procedure
    ;;;   may-precede?, a binary predicate (or comes-before?)
    ;;; Purpose:
    ;;; Produces:
    ;;; Preconditions:
    ;;;   vec is ordered by key.  That is, for all reasonable i,
    ;;;     (may-precede? (get-key (vector-ref vec i)) 
    ;;;                   (get-key (vector-ref vec (+ i 1))))
    ;;; Postconditions:

A few quick examples

    ; Each event has a name, a location, and an expected attendance
    (define events-on-campus
      (vector 
        (list "CS Table" "Day PDF" 10)
        (list "Convo: Personal Memory" "JRC 101" 150)
        (list "Titular head" "Harris Cinema" 1800)))

If ordered by capacity

     (binary-search events-on-campus 150 (o car cdr cdr) <=)

If ordered by title

     (binary-search events-on-campus "Titular Head" car string-ci<=?)

If we use vectors rather than lists, ordered by capacity
    ; Each event has a name, a location, and an expected attendance
    (define events-on-campus
      (vector 
        (vector "CS Table" "Day PDF" 10)
        (vector "Convo: Personal Memory" "JRC 101" 150)
        (vector "Titular head" "Harris Cinema" 1800)))

    (binary-search events-on-campus 211 (r-s vector-ref 2) <=)
    (binary-search events-on-campus 211 (lambda (event) (vector-ref event 2)) <=)

Lab
---

* Get good ideas from review sessions.