Battleships—Searching Algorithms

Summary

Computers often need to find specific pieces of information inside huge collections of data. To do this well, they need fast and efficient methods. This activity introduces three different ways to search: linear searching, binary searching, and hashing.

Curriculum Links

• Mathematics: Number (Level 3 and up) — exploring numbers, including greater than, less than, and equal to
• Geometry (Level 3 and up) — exploring shape and space, including coordinates

Skills

• Logical reasoning

Ages

• 9 years and up

Materials

Each child will need copies of the battleship game sheets:

• 1A and 1B for Game 1
• 2A and 2B for Game 2
• 3A and 3B for Game 3

You may also want extra copies of the backup sheets (1A′, 1B′, 2A′, 2B′, 3A′, 3B′) in case they're needed.

---

Introductory Activity

1. Choose about 15 students to line up at the front of the classroom. Give each one a card with a number on it, handed out in random order. Keep the numbers hidden from everyone else.

1. Give another student a container holding four or five sweets. Their job is to find one particular number among the cards. Each time they want to look at a card, they must "pay" one sweet. If they find the number before running out of sweets, they get to keep whatever is left.

1. Repeat the activity if you'd like.

1. Now shuffle the cards, hand them out again, and this time have the students arrange themselves in order from smallest to largest number. Repeat the search.

Once the numbers are in order, there's a much smarter strategy: use just one "payment" to have the middle student reveal their card. This eliminates half of the remaining students at once. By repeating this, the searcher should be able to find the number using only about three sweets. The difference in efficiency should be obvious to the class.

Activity

Students can experience how a computer searches through information by playing the battleship game below. While playing, encourage them to notice and think about the strategies they use to find the hidden ships.

---

Battleships—A Linear Searching Game

Instructions:

1. Get into pairs. One partner uses sheet 1A, the other uses sheet 1B. Don't let your partner see your sheet!

1. Each of you should circle one battleship on the top row of your sheet, then tell your partner its number.

1. Take turns guessing where your partner's ship is hidden. To guess, say the letter of a ship's position, and your partner tells you the number written there.

1. Count how many guesses ("shots") it takes you to find your partner's ship. That number is your score.

(Sheets 1A′ and 1B′ are spares for students who want to play again, or who accidentally saw their partner's sheet. Sheets 2A′/2B′ and 3A′/3B′ work the same way for later games.)

Follow-Up Discussion:

1. What scores did people get?
2. What are the best and worst possible scores? (The best is 1, and the worst is 26 — assuming no one shoots at the same ship twice. This method is called a linear search, because it checks every position one at a time, in order.)

---

Battleships—A Binary Searching Game

For this version, the numbers on the ships are arranged in ascending order (smallest to largest). Make sure students know this before they start.

Instructions:

1. Get into pairs. One partner uses sheet 2A, the other uses sheet 2B. Keep your sheet hidden!

1. Each of you circles one ship on the top row and tells your partner its number.

1. Take turns guessing your partner's ship, just like before.

1. Count your shots. That's your score.

Follow-Up Discussion:

1. What scores did people get?
2. What strategy did the students with the lowest (best) scores use?
3. Which ship should you guess first? (The one in the middle — because knowing its number tells you which half of the list your target must be in.) Which one should you guess next? (Again, pick the middle ship of whichever half still contains your target.)
4. If you always use this strategy, what's the most shots you'd ever need? (Five, at most.)

This method is called a binary search, because each guess splits the remaining possibilities in half.

---

Battleships—A Search Game Using Hashing

Instructions:

1. As before, take a sheet and tell your partner the number of your chosen ship.

1. This time, you can figure out which column (numbered 0–9) the ship is hiding in. Just add up all the digits in the ship's number. The last digit of that sum tells you the column. For example, for the ship numbered 2345: 2+3+4+5 = 14. The last digit of 14 is 4, so the ship is in column 4. Once you know the column, you just need to figure out which ship within that column is the right one. This technique is called hashing, because the digits are squished, or "hashed," together to create a shortcut.

1. Now play the game using this new strategy. You can play multiple rounds with the same sheet by choosing ships from different columns each time.

(Note: Unlike the other games, the spare sheets 3A′ and 3B′ must be used together as a pair, since the pattern of ships in each column has to match between the two sheets.)

Follow-Up Discussion:

1. Collect and compare scores, as before.
2. Which ships were quick to find? (Ones that are the only ship in their column.) Which were harder? (Ones sharing a column with many other ships.)
3. Which of the three searching methods was fastest, and why?
4. What are the strengths of each method? (Binary search is faster than linear search, but linear search doesn't require the ships to be sorted first. Hashing is usually the fastest of all three — but by bad luck, it can sometimes be very slow. In the worst case, if every ship ends up in the same column, hashing becomes just as slow as linear search.)

---

Extension Activities

1. Have students design their own versions of all three games. For the binary search version, remind them the numbers must be in ascending order. Ask: How could you make the Hashing Game as hard as possible? (Put every ship in the same column.) How could you make it as easy as possible? (Spread the ships out evenly across all the columns.)

1. What would happen if the ship being searched for wasn't there at all? (In Linear Search, it would take all 26 shots to prove this. In Binary Search, it would take five shots. With Hashing, it depends on how many ships are in that particular column.)

1. Using Binary Search, how many shots would you need to search through 100 locations? (About six.) A thousand locations? (About nine.) A million locations? (About nineteen.) Notice how slowly the number of shots grows compared to how fast the number of items grows — each time the number of items doubles, you only need one extra shot. This means the number of shots needed grows in proportion to the logarithm of the number of items (a mathematical way of describing very slow, steady growth).

---

What's It All About?

Computers store enormous amounts of information, and they need to search through it quickly. One of the biggest search challenges in the world belongs to internet search engines, which must scan through billions of web pages in a fraction of a second. Whatever the computer is trying to find — a word, a barcode number, an author's name — is called the search key.

Since computers process information so fast, you might assume the simplest approach — starting at the beginning and checking every single item until you find the right one — would work fine. This is exactly what the Linear Searching Game demonstrated. But this method turns out to be far too slow, even for computers.

For example, imagine a supermarket with 10,000 different products on its shelves. When a barcode is scanned at the checkout, the computer might need to look through all 10,000 numbers to find the matching product and price. Even if checking each one takes just one-thousandth of a second, searching the entire list could take ten seconds. Now imagine how long it would take to scan an entire family's groceries!

A much better approach is binary search. Here, all the numbers are first sorted into order. By checking the middle item, the computer can instantly tell which half of the list contains the search key — and then repeats this process on the smaller half, again and again, until it finds the match. Using this method, the supermarket's 10,000 products could be searched in just fourteen steps — taking about two-hundredths of a second, which is practically instant.

A third method is called hashing. Instead of comparing the search key against a list, the key itself is transformed through some calculation to reveal exactly where the matching information is stored. For example, if the search key is a phone number, you might add up all its digits, then divide by 11 and look at the remainder. This is a bit like the check digits described in Activity 4 — a small piece of extra data whose value depends on the rest of the information.

Usually, hashing lets the computer find what it's looking for almost immediately. Sometimes, though, several different keys accidentally end up pointing to the exact same location, and the computer...