Author:
Duncan deBruin
Subject:
Computer Science
Material Type:
Lesson Plan
Level:
High School
Grade:
9, 10, 11, 12
Tags:
  • Algorithms
  • Battleship
  • Battleship Algorithms
  • Searching Algorithms
  • License:
    Creative Commons Attribution Non-Commercial
    Language:
    English

    Education Standards

    Searching Algorithms

    Searching Algorithms

    Overview

    Computers are often required to find information in large collections of data. They need to develop quick and efficient ways of doing this. This activity demonstrates three different search methods: linear searching, binary searching and hashing.

    Battleship

    Introductory Activity

    1. Choose 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.

    2. Give another child a container with four or five sweets in it. Their job is to find a given number. They can “pay” to look at a particular card. If they find the correct number before using all their sweets, they get to keep the rest.

    3. Repeat if you wish to.

    4. Now shuffle the cards and give them out again. This time, have the children sort themselves into ascending order. The searching process is repeated.

      If the numbers are sorted, a sensible strategy is to use just one “payment” to eliminate half the children by having the middle child reveal their card. By repeating this process they should be able to find the number using only three sweets. The increased efficiency will be obvious.

    Battleships—A Linear Searching GameRead the following instructions to the children

    1. Organise yourselves into pairs. One of you has sheet 1A, the other sheet 1B. Don’t show your sheet to your partner!

    2. Both of you circle one battleship on the top line of your game sheet and tell your partner its number.

    3. Now take turns to guess where your partner’s ship is. (You say the letter name of a ship and your partner tells you the number of the ship at that letter.)

    4. How many shots does it take to locate your partner’s ship? This is your score for the game.

      (Sheets 1A' and 1B' are extras provided for children who would like to play more games or who “inadvertently” see their partner’s sheet. Sheets 2A', 2B' and 3A', 3B' are for the later games.)

      Follow Up Discussion

    1. What were the scores?

    2. What would be the minimum and maximum scores possible? (They are 1 and 26 respectively, assuming that the children don’t shoot at the same ship twice. This method is called ‘linear search’, because it involves going through all the positions, one by one.)

    page3image2077887808page3image2077888064

    Battleships—A Binary Searching GameInstructions

    The instructions for this version of the game are the same as for the previous game but the numbers on the ships are now in ascending order. Explain this to the children before they start.

    1. Organise yourselves into pairs. One of you has sheet 2A, the other sheet 2B. Don’t show your sheet to your partner!

    2. Both of you circle one battleship on the top line of your game sheet and tell your partner its number.

    3. Now take turns to guess where your partner’s ship is. (You say the letter name of a ship and your partner tells you the number of the ship at that letter.)

    4. How many shots does it take to locate your partner’s ship? This is your score for the game.

      Follow Up Discussion

    1. What were the scores?

    2. What strategy did the low scorers use?

    3. Which ship should you choose first? (The one in the middle tells you which half of the line the chosen ship must be in.) Which location would you choose next? (Again the best strategy is always to choose the middle ship of the section that must have the selected ship.)

    4. If this strategy is applied how many shots will it take to find a ship? (Five at most). This method is called ‘binary search’, because it divides the problem into two parts.

    page4image2078733312page4image2078733568

    Battleships—A Search Game using HashingInstructions

    1. Each take a sheet as in the previous games and tell your partner the number of your chosen ship.

    2. In this game you can find out which column (0 to 9) the ship is in. You simply add together the digits of the ship’s number. The last digit of the sum is the column the ship is in. For example, to locate a ship numbered 2345, add the digits 2+3+4+5, giving 14. The last digit of the sum is 4, so that ship must be in column 4. Once you know the column you need to guess which of the ships in that column is the desired one. This technique is called ‘hashing’, because the digits are being squashed up (“hashed”) together.

    3. Now play the game using this new searching strategy. You may like to play more than one game using the same sheet—just choose from different columns.

      (Note that, unlike the other games, the spare sheets 3A' and 3B' must be used as a pair, because the pattern of ships in columns must correspond.)

      Follow Up Discussion

    1. Collect and discuss scores as before.

    2. Which ships are very quick to find? (The ones that are alone in their column.) Which ships may be harder to find? (The ones whose columns contain lots of other ships.)

    3. Which of the three searching processes is fastest? Why?

      What are the advantages of each of the three different ways of searching? (The second strategy is faster than the first, but the first one doesn’t require the ships to be sorted into order. The third strategy is usually faster than the other two, but it is possible, by chance, for it to be very slow. In the worst case, if all the ships end up in the same column, it is just as slow as the first strategy.)

    page5image2078913968

    Extension Activities

    1. Have the children make up their own games using the three formats. For the second game they must put the numbers in ascending order. Ask how they might make the Hashing Game very hard. (The hardest game is when all the ships are in the same column.) How could you make it as easy as possible? (You should try to get the same number of ships into each column.)

    2. What would happen if the ship being sought wasn’t there? (In the Linear Search game it would take 26 shots to show this. In the Binary Search game you would need five shots to prove this. When using the Hash System it would depend on how many ships appeared in the relevant column.)

    3. Using the Binary Search strategy how many shots would be required if there were a hundred locations (about six shots), a thousand locations (about nine), or a million (about nineteen)? (Notice that the number of shots increases very slowly compared to the number of ships. One extra shot is required each time the size doubles, so it is proportional to the logarithm of the number of ships.)