Searches

Essential Question: How does a computer perform a search on a database?

Mastery Objectives: 

• SWBAT create a binary search algorithm on a database.

• SWBAT create a linear search algorithm on a database.

Number Guessing Game

https://snap.berkeley.edu/snap/snap.html#open:https://bjc.edc.org/bjc-r/prog/5-algorithms/U5L1-GuessNumber.xml 

Directions: Open up snap and create the following code:

Talk to your neighbor:

1. Develop a strategy that will identify the secret number in no more than 6 guesses.

2.  Write down your strategy clearly enough for others to use it to play the game.

3.  Then compare your algorithm with another pair of students.

Open the following project: https://snap.berkeley.edu/snap/snap.html#open:https://bjc.edc.org/bjc-r/prog/5-algorithms/U5L1-Spell-Checker.xml 

1. How many five-letter words are in the 10,000 words list?

2. Use the computation time  block provided in this project to determine how long it takes for the computer to answer that question.

3. Click on the computation time expression you just used to answer the previous question three more times and note the range of answers. They're not exactly the same because of other things that your computer is doing at the same time, so you should always take whatever result it gives you as approximate.

4.  How long do you think it would take to count five-letter words if the list had 100,000 words?

5. Use computation time to check using the 100,000 words list.

6. Suppose instead, we count the seven-letter words. Will this take...

   • More time because seven letters is more than five letters?

   • Less time because there are fewer seven-letter words than five-letter words?

   • The same time because it's not the word length that matters; it's the size of the dictionary?

7. Experiment to find out for sure.

How does this compare with the number guessing game?

1. Check whether "seperate" is spelled correctly by using binary search to look for the word in the sorted list 100,000.

2. Try binary search with some words that you know are spelled correctly and some that you know are incorrect.

3. Now use binary search to search for the same words in the unsorted 100,000 words.

4.  Why does binary searching work on one list but not the other? Consider how the binary search algorithm works.