Battleships—Searching Algorithms

Summary

Computers often need to find information inside huge piles of data. To do this well, they need fast and smart ways of searching. This activity shows three different ways to search: linear searching, binary searching, and hashing.

Curriculum Links

• Mathematics: Number, Level 3 and up. Exploring numbers: greater than, less than, and equal to.
• Geometry, Level 3 and up. Exploring shape and space: coordinates (using letters and numbers to find a spot on a grid).

Skills

• Logical reasoning

Ages

• 9 years and up

Materials

Each child needs a copy 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 a game needs to be replayed.

---

Battleships: Introductory Activity

1. Pick about 15 children to line up at the front of the classroom. Give each child a card with a number on it, in random order. Keep the numbers hidden from the rest of the class.

1. Give another child a container with four or five sweets. Their job is to find a certain number. They can "pay" one sweet each time they want to look at a card. If they find the right number before running out of sweets, they keep the leftover sweets.

1. Repeat this a few times if you like.

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

If the numbers are in order, a smart plan is to spend just one "payment" to have the middle child show their card. This lets the searcher cut the group in half right away. By repeating this trick, they can find the number using only three sweets. You'll clearly see how much faster this is!

Activity

Playing the battleship game helps children understand how a computer searches for information. While they play, ask them to think about the strategy they are using to find the ships.

---

Battleships—A Linear Searching Game

Instructions:

1. Get into pairs. One person uses sheet 1A, the other uses sheet 1B. Don't show your sheet to your partner!

1. Both players circle one battleship on the top line of their sheet and tell their partner its number.

1. Take turns guessing where your partner's ship is. Say the letter of a ship, and your partner tells you the number written at that letter.

1. Count how many guesses it takes to find your partner's ship. That number is your score.

(Sheets 1A' and 1B' are extra copies for children who want to play again or who accidentally saw their partner's sheet. Sheets 2A', 2B', 3A', and 3B' are extras for the later games.)

Follow-Up Discussion:

1. What scores did people get?

1. What are the best and worst possible scores? (The best is 1 guess, and the worst is 26 guesses, as long as you never guess the same ship twice. This method is called a linear search because you check each spot one after another, in a line.)

---

Battleships—A Binary Searching Game

Instructions:

This game works just like the last one, but now the numbers on the ships are arranged in order from smallest to largest. Make sure to tell the children this before they start.

1. Get into pairs. One person uses sheet 2A, the other uses sheet 2B. Don't show your sheet to your partner!

1. Both players circle one battleship on the top line of their sheet and tell their partner its number.

1. Take turns guessing where your partner's ship is. Say the letter of a ship, and your partner tells you the number at that letter.

1. Count how many guesses it takes to find the ship. That's your score.

Follow-Up Discussion:

1. What scores did people get?

1. What strategy did the players with the lowest (best) scores use?

1. Which ship should you guess first? (The one in the middle — its number tells you which half of the line your ship must be in.) Which spot should you guess next? (Again, pick the middle ship of whichever half must contain the ship you're looking for.)

1. If you follow this plan every time, how many guesses will you need at most? (Five.) This method is called a binary search, because each guess splits the problem into two smaller parts.

---

Battleships—A Search Game Using Hashing

Instructions:

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

1. In this game, you can figure out which column (0–9) the ship is hiding in. Add together all the digits of the ship's number. The last digit of that sum tells you the column. For example, to find a ship numbered 2345, add 2+3+4+5, which equals 14. The last digit of 14 is 4, so the ship must be in column 4. Once you know the column, you just need to guess which ship in that column is the right one. This trick is called hashing, because you're squashing ("hashing") the digits together to get an answer.

1. Now play the game using this new strategy. You can play more than once using the same sheet — just pick ships from different columns each time.

(Note: Unlike the other games, the backup sheets 3A' and 3B' must be used together as a matching pair, because the pattern of ships in each column has to line up.)

Follow-Up Discussion:

1. Share and discuss everyone's scores.

1. Which ships were super quick to find? (Ones that are the only ship in their column.) Which ships were harder to find? (Ones sharing a column with lots of other ships.)

1. Which of the three searching methods was fastest? Why?

What's good about each method? (Binary search is faster than linear search, but linear search doesn't require the ships to be sorted in order first. Hashing is usually the fastest of all three — but sometimes, by bad luck, it can be 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 children design their own battleship games using all three formats. For the binary search game, remind them the numbers must be in ascending order. Ask: How could you make the Hashing Game really hard? (Put all the ships in the same column!) How could you make it as easy as possible? (Spread the ships out evenly, with the same number in each column.)

1. What would happen if the ship you were searching for wasn't on the board at all? (In the Linear Search game, it would take all 26 guesses to prove this. In the Binary Search game, five guesses would prove it. In the Hashing game, it depends on how many ships are in that particular column.)

1. Using the Binary Search strategy, how many guesses would you need if there were:
2. 100 spots? (About 6 guesses)
3. 1,000 spots? (About 9 guesses)
4. 1,000,000 spots? (About 19 guesses)

Notice that the number of guesses grows very slowly compared to how many ships there are. Each time the number of spots doubles, you only need one extra guess!

---

What's It All About?

Computers store enormous amounts of information, and they need to search through it fast. One of the biggest searching challenges in the world belongs to internet search engines — they must search through billions of web pages in a tiny fraction of a second. The piece of information a computer is told to look for — like a word, a barcode number, or an author's name — is called a search key.

Computers work incredibly fast, so you might think the easiest way to find something is to just start at the very beginning and check everything one by one until you find it. That's exactly what we did in the Linear Searching Game. But this method is slow — even for a computer!

For example, imagine a supermarket sells 10,000 different products. When a barcode is scanned at the checkout, the computer might have to check up to 10,000 numbers to find the matching product and price. Even if checking each number takes only one-thousandth of a second, going through the whole list could take ten whole seconds. Imagine how long it would take to check out an entire cart of groceries!

A much better strategy is binary search. First, the numbers are sorted into order. Then, checking the middle item tells you which half of the list your item must be in. This process repeats until the item is found. Using our supermarket example again, all 10,000 items could now be searched using just fourteen guesses — taking about two-hundredths of a second. That's hardly noticeable!

A third strategy is called hashing. Here, the search key itself is used to calculate exactly where the information should be. For example, if the search key is a phone number, you could add up all its digits and find the remainder after dividing by 11. In a way, a hash key works a bit like the check digits from Activity 4 — a small piece of data whose value depends on the rest of the number.

Usually, the computer finds what it's looking for right away using hashing. But sometimes several search keys can end up pointing to the same spot — and when that happens, the computer has extra work to do to sort it out.