Quiz: Searching Algorithms (Battleships)

Multiple Choice Questions

1. In the Battleships games, what are the children trying to find on their partner's sheet?
A) A hidden number
B) A hidden ship
C) A hidden word
D) A hidden card

2. What is the name of the search method used in the very first Battleships game, where ships are NOT in order?
A) Binary search
B) Hashing
C) Linear search
D) Sorting search

3. What is the maximum number of shots needed to find a ship using linear search (with 26 ships)?
A) 5
B) 14
C) 19
D) 26

4. In the Binary Searching Game, how must the numbers on the ships be arranged?
A) In random order
B) In ascending order
C) In descending order
D) Grouped by column

5. When using binary search, which ship should you choose first?
A) The first one on the list
B) The last one on the list
C) The middle one
D) Any ship at random

6. At most, how many shots are needed to find a ship using binary search in the game?
A) Three
B) Five
C) Ten
D) Twenty-six

7. In the Hashing game, how do you work out which column a ship is in?
A) Count the letters in its name
B) Add together the digits of the ship's number and use the last digit of the sum
C) Multiply the digits together
D) Look at the first digit only

8. According to the resource, which searching method is usually the fastest, though it can sometimes be very slow by chance?
A) Linear search
B) Binary search
C) Hashing
D) Sorting

---

Short Answer Questions

9. Explain why linear search is called "linear." What is one disadvantage of this method?

10. Using the binary search strategy, about how many shots would be needed to find one item among a thousand locations, and among a million locations? What pattern do you notice as the number of locations grows?

11. In the Hashing Game, why are some ships very quick to find while others are harder to find? What would make the Hashing Game as easy as possible to play?

---

Answer Key

1. B) A hidden ship
2. C) Linear search
3. D) 26
4. B) In ascending order
5. C) The middle one
6. B) Five
7. B) Add together the digits of the ship's number and use the last digit of the sum
8. C) Hashing

1. Linear search is called "linear" because it involves going through all the positions one by one, in a line. A disadvantage is that it can be very slow, since in the worst case you may need to check every single item (e.g., 26 shots) before finding the one you want.

1. For a thousand locations, about nine shots are needed; for a million locations, about nineteen shots are needed. The pattern is that the number of shots increases very slowly compared to the number of locations — only one extra shot is needed each time the number of locations doubles.

1. Ships that are alone in their column are very quick to find, while ships in columns containing many other ships are harder to find because you still have to guess which specific ship it is within that column. The game would be easiest if the same number of ships were placed in each column (and hardest if all ships were placed in the same column).