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

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