CSC151.01 2015S, Class 45: Binary Search
========================================

* Continue partners!
* Welcome to our visitors!

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Project Notes.
    * Questions.
* The problem of searching.
* Making searching more efficient using divide-and-conquer.
* A demo: Destructive binary search.
* Lab.

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

### Admin

* Review sessions Thursday (9, 1:15, 8pm).
* For office hours this week, check <http://rebelsky.youcanbook.me>.
* Today: 5-10 min admin, 5-10 min project, 15-20 min sorting, remainder lab.
* Reminder: ASK QUESTIONS ON TAKE-HOME EXAMS!
* When you send me email questions of the form "this doesn't work",
    * Send me all the code I will need in order to run examples, including
      any utilities you are using.
    * Send me the expression that you are using that's not working.
    * Explain to me what's happening.

### Upcoming Work

* Project images due today.
* Projects due next Tuesday.
* Lab writeup: 
  <http://bit.ly/151-2015S-lab44>
* Reading for Wednesday:  Review
  [Search Algorithms](../readings/searching-reading.html)

### Extra Credit Opportunities

#### Academic 

* Convocation April 22nd, Erica Lehrer '92 (Post-Conflict Memory, Ethnography)
* CS Talks Wednesday: 

#### 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.    Drag.
* Sunday at 2pm Orchestra in Herrick with Choir - Requiem

#### Miscellaneous

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

### Other Good Things (no extra credit)

* Contra Dance April 24 in Main Hall.

### Project Tips

Image-making techniques

* Drawings as values, with or without recursion
* `image-variant`, `image-transform!
    * Also `(image-redo! image (lambda (col row color) ...)`
    * `image-transform!` and `image-redo!` behave differently with
      selections.
* `image-compute`
* Gimp tools, with or without recursion
* Turtle graphics

I've added a variety of project tips that I thought we'd look at
quickly.  

* Recoloring a turtle's drawing.  (Needs improvement.)
* Selecting a polygon.

You can also find a few others on the tips page, such as a procedure 
to copy and paste.

### Questions

The problem of searching
------------------------

* What does `assoc` do?
    * Search for an entry by key in a list in which each element has the form
* How do we search?
    * If unordered - look at the first then the second then the third
    * If multiple people - divide the work
* How does it help to have them in order?
    * If you look in the middle, you can get rid of half of the deck
      really quickly
* How much does this help?
* To find a Grinnellian in the directory, how many names will I have
  to look at using this model?
* 1600 
        * 800
        * 400
        * 200
        * 100
        * 50
        * 25
        * 12
        * 6
        * 3
        * 1
* The order in which you store the data matters.  A lot.
* Some algorithms require even more than linear time 1+2+3+4+...+1600
  = 800*1601

Making searching more efficient using divide-and-conquer
--------------------------------------------------------

A demo: Destructive binary search
---------------------------------

Lab, Continued
--------------