← Back to course
Intro to CS 9-10 / Week 07 / Friday
5/6
Week 07 · Search, Speed and Limits

Friday

Impact Friday: One algorithm, many fields
// Binary search, counting steps, heuristics and problems no algorithm can solve
⏱ about 20 min

Friday: Impact Friday: One Algorithm, Many Fields

Wren sorts the greenhouse seed packets alphabetically, then finds the basil packet in three quick looks.

"That was binary search," Comet says. "You started in the middle of the box."

Wren smiles. "Beacon's search does not care whether it is searching water readings or seed names."

Comet thinks about the rover. "And nearest-first could plan any trip with lots of stops."

Nova hovers between them. "I found a pattern," she says. "An algorithm is about steps, not about tomatoes."

"So one algorithm can help in many places," Wren says. "As long as the data fits what it needs."

Steps that travel

An algorithm is a finite set of instructions that does a specific task. The steps do not depend on what the data is about.

Binary search works on any sorted data: numbers, names or dates. Only the sorting rule changes.

Nearest-first works on any trip with several stops, from a rover route to a day of errands.

Using existing correct algorithms as building blocks can reduce development time and testing, and makes errors easier to find.

WHICH ALGORITHM FITS?
  • Read the question.
  • Tap your answer.
Finding one name in a class list sorted alphabetically.
Planning a walk to drop off notes at five neighbors' doors.
Finding one sign-up sheet in a jumbled pile.
Finding a page number in a book.
Try it
Look around your home for three things that are already sorted, such as numbered pages, a calendar or a list in order.
For each one, explain how binary search could find an item in it.

Week review

Week reviewTrue or false?
A decision problem has a yes or no answer.?
Binary search needs sorted data.?
Efficiency can be measured informally by counting how many times statements run.?
Factorial growth runs in a reasonable amount of time.?
A heuristic is guaranteed to find the best solution.?
WHY THIS EXERCISEThese five ideas are the core of searching, speed and limits.
OUR WEEK, IN ORDER
  • ?We asked whether the water ever read 74.
  • ?We traced binary search through Beacon's sorted log.
  • ?We played guess-the-number with 32 sorted cards.
  • ?We planned the rover route with a heuristic.
  • ?We found the same algorithms beyond the greenhouse.
WHY THIS EXERCISEThe week moved from one search, to measuring speed, to limits, to uses everywhere.
A search that starts in the middle of sorted data is called ____ search.
A problem no algorithm can always answer correctly is called ____.
Which kind of search can work on a list that is not sorted? Type one word.
WHY THIS EXERCISEChoosing a search starts with asking whether the data is sorted.
On paper, make a two-column poster: Binary search and Nearest-first. Under each, draw three places outside the greenhouse where it could help.

Excellent week, developer. Tomorrow's Mission Quest is a guessing game for the whole family.

← Thursday