← Back to course
Intro to CS 9-10 / Week 05 / Mission Quest
6/6
Week 05 · Lists

Mission Quest

Mission Quest: Face-Down Search
// Keeping track of many values at once
⏱ about 20 min

Mission Quest: Face-Down Search

It is game night in the greenhouse, and Comet has a deck of numbered cards.

"I am the list," she says, laying eight cards face down in a row. "You are the search."

Wren grabs a notepad to count checks. "I will be the trace."

Nova hovers above the row, her lights twinkling. "Every flip is one check," she says.

"The fewest checks wins the round, but no peeking."

Comet shuffles the cards again, just to be sure.

Wren smiles. "Let's investigate."

  1. A list is an ordered sequence of elements. Each element has a unique index.
  2. On the AP reference sheet, indexes run from 1 to the length of the list. Any other index is an error.
  3. FOR EACH visits each element in order, from first to last.
  4. Common list algorithms find a minimum or maximum, a sum or an average.
  5. A linear search checks elements in order until it finds the value or runs out.
  6. One list can replace many separate variables and make code shorter and clearer.
◇ FACE-DOWN SEARCH
You need eight to twelve paper cards, one extra card for a helper, and a pencil.
One player writes a different number on each card and lays them face down in a row.
Number the spots from 1 so everyone can name each index.
Another player picks a target number and searches by flipping cards in order, from index 1.
The player who wrote the cards keeps count of the checks. Stop when the target is found or the row runs out.
Play a round where the target is not in the row. How many checks did it take?
Bonus round: turn the row face up and walk it to find the biggest number. Write the biggest so far on the helper card.
For a grown-up
This week your student learned lists: one name that holds many values in order.
Ask: why is one list better than many separate variables?
Ask: when searching cards in order, why does a missing number take the most checks?
Everything in this course is done on paper. No app, website or account is needed.
QUEST CHECK
  • Read the question.
  • Tap your answer.
The row has 10 cards and the target is missing. How many checks before you can say it is not there?
The target is at index 3. How many checks does a linear search need?
A player asks for card 0 in the row. What happens on the AP reference sheet?
Quest reviewTrue or false?
In the game, each flip counts as one check.?
Finding the biggest card needs a helper card that remembers the biggest so far.?
A missing target is found faster than one at index 1.?
WHY THIS EXERCISECounting checks is the first step toward judging how fast a search is.
← Friday