CSC151.01 2015S, Class 45: Binary Search

Overview

Preliminaries

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.

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

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.

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

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