Activity 6: Battleships—Searching Algorithms

Summary

Computers often have to find specific information inside huge collections of data. To do this quickly, they rely on efficient search methods. This activity introduces three of them: linear searching, binary searching, and hashing.

Curriculum Links

• Mathematics: Number, Level 3 and up — comparing numbers (greater than, less than, and equal to)
• Geometry, Level 3 and up — working with coordinates

Skills

• Logical reasoning

Ages

• 9 years and up

Materials

Each student will need copies of the battleship game sheets:

• 1A and 1B (Game 1)
• 2A and 2B (Game 2)
• 3A and 3B (Game 3)

A few extra copies of the backup sheets (1A′, 1B′, 2A′, 2B′, 3A′, 3B′) may also be useful.

---

Introductory Activity

1. Choose about 15 students to line up at the front of the room. Hand each one a card with a number on it, in random order, keeping the numbers hidden from the rest of the class.

1. Give another student a small container holding four or five sweets. Their task is to find a particular number. They can "pay" one sweet each time they want to check a card. If they find the right number before running out of sweets, they keep whatever is left.

1. Repeat the activity if you'd like.

1. Now shuffle the cards, hand them out again, and have the students arrange themselves in ascending order (smallest to largest). Repeat the search.

Once the numbers are sorted, a smart strategy is to "spend" just one sweet to eliminate half the line at once — by having the student standing in the middle reveal their card. Repeating this trick lets the searcher find any number using only about three sweets. The improvement in efficiency should be obvious to the class.

Activity

Playing the battleship game will help students experience firsthand how a computer searches for information. As they play, encourage them to pay attention to the strategies they use to locate the hidden ships.

---

Battleships — A Linear Searching Game

Instructions:

1. Pair up. One partner uses sheet 1A, the other sheet 1B. Don't let your partner see your sheet!

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

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

1. Count how many guesses ("shots") it takes to find your partner's ship. This 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′ serve the same purpose for the later games.)

Follow-Up Discussion:

1. What scores did people get?

1. What are the lowest and highest possible scores? (The answers are 1 and 26, assuming no one shoots at the same ship twice.) This approach is called a linear search, because it works through every position one at a time, in order.

---

Battleships — A Binary Searching Game

Instructions:

This game works the same way as the last one, except the ship numbers are now arranged in ascending order. Make sure students know this before starting.

1. Pair up. One partner uses sheet 2A, the other sheet 2B. Keep your sheet hidden.

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

1. Take turns guessing the ship's location by naming letters, just as before.

1. Record how many shots it takes to find the ship — this is your score.

Follow-Up Discussion:

1. What scores came up?

1. What strategy did the students with the lowest scores use?

1. Which ship should you guess first? (The one in the middle — its number tells you which half of the line your target must be in.) Which location should you try next? (Again, pick the middle ship of whichever section still might contain the target.)

1. If a player always uses this strategy, how many shots will it take at most to find any ship? (Five.)

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, each partner takes a sheet and tells the other the number of their chosen ship.

1. This time, you can figure out which column (0–9) the ship sits in just by doing some quick math: add together all the digits of the ship's number. The last digit of that sum tells you the column. For example, to locate ship number 2345, add 2+3+4+5 = 14. The last digit of 14 is 4, so the ship must be in column 4. Once you know the column, you only need to guess among the ships within it. This technique is called hashing — the digits of the number are being "squashed together" (or "hashed") to point directly to a location.

1. Play the game using this new strategy. Feel free to play several rounds with the same sheet by choosing ships from different columns each time.

(Note: unlike the earlier games, the spare sheets 3A′ and 3B′ must be used together as a matched pair, since the pattern of ships across columns has to line up between the two sheets.)

Follow-Up Discussion:

1. Gather and compare scores, as before.

1. Which ships were found almost instantly? (The ones that are the only ship in their column.) Which were harder to track down? (Ones sharing a column with many other ships.)

1. Which of the three searching methods was fastest, and why?

What are the trade-offs among the three methods? 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 slow. In the worst case, if every ship happened to land in the same column, hashing would be just as slow as a linear search.

---

Extension Activities

1. Have students design their own versions of each game. For the binary search game, remind them the numbers must be in ascending order. Ask: how could you make the hashing game as difficult as possible? (Put every ship in the same column.) How could you make it as easy as possible? (Spread the ships evenly across all the columns.)

1. What would happen if the ship being searched for wasn't actually on the sheet? In the linear search game, it would take a full 26 shots to prove this. In the binary search game, it would take five shots to be sure. Using the hash method, the answer depends on how many ships happen to share that column.

1. Using binary search, how many shots would it take to search through 100 locations (about 6), 1,000 locations (about 9), or a million locations (about 19)? Notice how slowly the number of shots grows compared to how fast the number of items grows — each time the number of ships doubles, you only need one extra shot. This means the number of shots needed is proportional to the logarithm of the number of items (a mathematical way of describing very slow growth relative to the total size).

---

What's It All About?

Computers store enormous amounts of information, and they need to search through it quickly. One of the largest 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 piece of data a computer is told to look for — a word, a barcode number, an author's name — is called a search key.

Computers process information incredibly fast, so it might seem reasonable for them to simply start at the beginning of their stored data and check each item one by one until they find what they're looking for. That's exactly what happened in the Linear Searching Game. But this method is slow — even for a computer. Consider a supermarket that stocks 10,000 different products. When a barcode is scanned at checkout, the computer may need to check up to 10,000 numbers before finding the matching product and price. Even if checking each code takes only one-thousandth of a second, searching the entire list could take ten full seconds. Imagine how long it would take to scan an entire cart of groceries that way!

A better approach is binary search. Here, the data is sorted in order first. Checking the middle item tells you which half of the list your target must be in, and the process repeats on that smaller half each time. Going back to the supermarket: with binary search, the same 10,000 products could be searched using only about fourteen checks — perhaps two-hundredths of a second, which is essentially instant.

A third method is called hashing. Instead of comparing the search key against a list, the key itself is transformed through a calculation that points directly to where the information is stored. For instance, if the search key is a phone number, you might add together all its digits and divide by 11, keeping only the remainder. In this way, a "hash key" works a bit like the check digits discussed in Activity 4 — a small piece of data whose value is calculated from the rest of the data. Usually, this lets the computer find what it needs almost immediately. There is a small chance, however, that two different keys end up pointing to the same location — a situation the computer must be prepared to handle.