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

_Overview_

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

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

### Admin

* Continue partners!
* Review sessions Thursday.
* For office hours this week, check <http://rebelsky.youcanbook.me>
* 5-10 min admin, 5-10 min project, 15-20 min sorting, remainder lab.
* 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 (Afternoon Section)

* Contra Dance April 24 in Main Hall.
* Financial Literacy workshop Monday night 7-8 in JRC 226.

#### 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.  

* 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
------------------------

* Look at each card in a group to see if it's the one you want
* Recursion!
* `assoc` - finds an element of a list of lists by comparing a sought
  value to the car of each of those lists.
* How many names do I have to look at to find a student in all 1600 
  Grinnell students?
* 1600 -> 800 -> 400 -> 200 -> 100 -> 50 -> 25 -> 12 -> 6 -> 3 -> 1
* Requires that the values are "in order"

We try to write algorithms that are fast in terms of the size of the
input

* Writing the simple search over a list
    * compare to the car
         * matches - done
         * doesn't match - go on to the next thing
         * look at each pair once
    * for each index from 0 to n-1
         * if the value is at (list-ref lst index) - done
         * doesn't match - go on to the next index
         * But list-ref requires cdr.  This takes 1 + 2 + 3 + 4 + ...

Lab
---

* Why color-name->irgb is slow

        (define color-name->irgb
          (let ([named-colors
                  (list (list "black" (irgb 0 0 0))
                        (list "white" (irgb 255 255 255))
                        (list "green" (irgb 128 0 0))
                        (list "wheat" (irgb 245 222 179))
                        (list "sarah" (irgb 240 0 230))))
            (lambda (name)
              (let ([result (assoc name named-colors)])
                (if result
                    result
                    (error "Not a valid colir name: " name))))))