← Searching Algorithms (Battleship)
Flashcards
Searching Algorithms (Battleship)
Generated from the original open resource by CS Unplugged. Built only from the resource — nothing invented. Free, no login.
Searching Algorithms (Battleship) — Flashcards
| Front | Back |
|---|---|
| What is a search key? | The data a computer looks up, such as a word, a bar code number, or an author's name. |
| What is linear search? | A search method that goes through all positions one by one until the desired item is found. |
| What is the maximum number of shots in the Linear Searching Game with 26 ships? | 26 shots (if you never shoot the same ship twice). |
| What is the minimum number of shots possible in any search game? | 1 shot. |
| What condition is needed to use binary search? | The items (ship numbers) must be sorted into ascending order. |
| What is binary search? | A search method that repeatedly checks the middle item of a list to eliminate half the remaining possibilities each time. |
| What is the best strategy in binary search? | Always choose the middle ship of the section that must contain the selected ship. |
| Max shots needed to find a ship using binary search (26 ships)? | Five shots at most. |
| What is hashing? | A search method where the search key's digits are combined (squashed together) to calculate exactly where to find the data. |
| How do you find a ship's column using hashing? | Add together the digits of the ship's number; the last digit of the sum gives the column number. |
| Example: Ship number 2345 — which column? | 2+3+4+5=14, last digit is 4, so the ship is in column 4. |
| Which ships are quickest to find using hashing? | Ships that are alone in their column. |
| Which ships are hardest to find using hashing? | Ships whose column contains many other ships. |
| What is the worst-case scenario for hashing? | If all ships end up in the same column, hashing is as slow as linear search. |
| How can you make a Hashing Game very hard? | Put all the ships in the same column. |
| How can you make a Hashing Game as easy as possible? | Spread the ships evenly, so each column has about the same number of ships. |
| Why is linear search sometimes preferred despite being slower? | It doesn't require the ships/items to be sorted into order first. |
| Binary search shots needed for 100 locations? | About six shots. |
| Binary search shots needed for 1,000 locations? | About nine shots. |
| Binary search shots needed for 1,000,000 locations? | About nineteen shots. |
| Why does binary search scale so well? | The number of shots needed grows proportional to the logarithm of the number of items — one extra shot per doubling of size. |
| Real-world example of a huge search problem? | Internet search engines, which must search billions of web pages in a fraction of a second. |
Original licensed under CC BY-NC-SA 4.0. This teaching material is provided free by OER.ai.