Held: Wednesday, 22 April 2015

Back to Outline 45 - Binary Search. On to Outline 47 - Pause for Breath.

Summary

We continue our explorations of binary search, grounding our explorations in practice.

Related Pages

• Reading: Searching
• Lab: Binary Search
• Morning EBoard 46 (Source a.m. 46)
• Afternoon EBoard 46 (Source p.m. 46)

Overview

• Exploring the search API.
• Remaining questions.

Administrivia

• 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: 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 (Post-Conflict Memory, Ethnography)
• 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

Peer Support (Afternoon Section)

• Contra Dance. April 24 in Main Hall.
• Dance Ensemble. Thursday 7:30; Friday 7:30; Saturday 7:30; Sunday 2:00. Flanagan. Get tickets!

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.
• Sunday at 2pm Orchestra in Herrick with Choir - Requiem
• Dance Ensemble. Thursday 7:30; Friday 7:30; Saturday 7:30; Sunday 2:00. Flanagan. Get tickets!

Exploring the Search API

Suppose we have data for various students on campus: Last Name (string), First Name (string), Graduation Year (integer), Box Number (integer), and Phone number (string). We might search by any of the four criteria (and by other criteria) and we might therefore order in various ways.

(define people
  (vector 
    ("Aanderson" "Aan"    2017 4114 "x4410")
    ("Brown"     "Bruin"  2016 8123 "x9000")
    ("Doe"       "J"      2018 9999 "none")
    ("Smith"     "Kieran" 2015 4112 "x9231")
    ("Taylor"    "Mic"    2017 1234 "x0001")))

• Right now, we have things sorted by last name (and, surprisingly, by first name), so we might search by last name (or by first name).
• If we wanted to search by year, we'd order by year (although that's not likely to give particularly useful results).
• If we wanted to search by box number, we'd order by box number.
• Our search algorithm needs to know how to find the key in an entry
  • Last name: car
  • First name: cadr
  • Year: caddr
  • Box number: cadddr
• Our search algorithm needs to know how the keys are ordered
  • Traditionally, strings are ordered alphabetically
  • Traditionally, numbers are ordered numerically, from smallest to largest
• So our binary search algorithm needs four parameters:
  • The vector to search
  • The key to search for
  • The instructions for getting a key from each element
  • The mechanism used to order the elements
• All of this is a bit more complicated if we have a compound key, such as "last name plus first name plus phone number"

Lab

• Do the lab
• Be prepared to reflect.