Problem: A Guessing Game Solution
Let’s play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. The computer is going to randomly select an integer from 1 to 15. You’ll keep guessing numbers until you find the computer’s number, and the computer will tell you each time if your guess was too high or too low:
Once you’ve found the number, reflect on what technique you used when deciding what number to guess next.Maybe you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number. We call this approach linear search, because you guess all the numbers as if they were lined up in a row. It would work. But what is the highest number of guesses you could need? If the computer selects 15, you would need 15 guesses.
Then again, you could be really lucky, which would be when the computer selects 1 and you get the number on your first guess. How about on average? If the computer is equally likely to select any number from 1 to 15, then on average you’ll need 8 guesses.But you could do something more efficient than just guessing 1, 2, 3, 4, …, right? Since the computer tells you whether a guess is too low, too high, or correct, you can start off by guessing 8. If the number that the computer selected is less than 8, then because you know that 8 is too high, you can eliminate all the numbers from 8 to 15 from further consideration.
If the number selected by the computer is greater than 8, then you can eliminate 1 through 8. Either way, you can eliminate half the numbers. On your next guess, eliminate half of the remaining numbers. Keep going, always eliminating half of the remaining numbers.We call this halving approach binary search, and no matter which number from 1 to 15 the computer has selected, you should be able to find the number in at most 4 guesses with this technique.Here, try it for a number from 1 to 300. You should need no more than 9 guesses.
A Guessing Game Solution (Hint)
For binary search, the total iterations required to find a number would be atmost log2(total_array_size).
So for an array of size 600 (assuming the array to be sorted) the easiest way to find is,
calculate the total number of times 2 needs to be multiplied to get 600.
Multiplying 2, 9 times (2^9) gives 512.
But 2^9 < 600.
2^10 = 1024. 1024 > 600.
2^9 < 600 < 2^10.
if 2 is multiplied approximately 9.xx times 600 will be achieved. Since decimal counting is not appropriate in this scenario, rounding 9.xx to 10, that will be the maximum iterations required to find the desired number in a set of 600 sorted numbers.
A Guessing Game Solution (Hint 2)
The “size” of each leap isn’t what determines the length of time it takes to find the correct number, only the size of the list (ergo, the number of leaps). An easy way to understand this is to look at what binary actually means: powers of 2.
So, in the first example from the reading it says that you should be able to find the correct number from a selection of 16 in 5 attempts. 2^4 = 16, but you can find the number in 4 clicks, but you still might need a 5th click to choose the number. In the second example, it says you should be able to find the correct number from a selection of 300 in 9 attempts. 2^8 = 256 so there’s still the possibility you haven’t found it, but 2^9 = 512 thus encompassing all 300 possibilities, so you will have found it by the 9th click. Please note that 2^8 = 256 and 300 – 256 = 44 does not mean you’ll magically find the correct number out of 44 possible numbers. You’ll only have one number left after the 8th click and will need the 9th to actually choose it
Therefore, with your example of 1000 elements, you just need to find the power of 2 necessary to encompass all 1000 elements. 2^10=1,024 so it will take 10 clicks maximum to choose the correct number.
A Guessing Game Review:
In our experience, we suggest you solve A Guessing Game and gain some new skills from Professionals completely free and we assure you will be worth it.
A Guessing Game is available on Khan Academy for free, if you are stuck anywhere between quiz or graded assessment quiz, just visit Networking Funda to get A Guessing Game Solution.
I hope this A Guessing Game Solution would be useful for you to learn something new from this Course. If it helped you then don’t forget to bookmark our site for more Coursera Quiz Answers.
This course is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisite courses.