Q3) Another guessing game: (10 points) 1) Write a code executing the following: a) First, randomly...

Transcribed Image Text:

Q3) Another guessing game: (10 points) 1) Write a code executing the following: a) First, randomly generate three numbers [0..9] (***The order among three numbers matters***) b) Then, continuously guess all three numbers until all three are guessed correctly. See below for two different ways of guessing three random numbers. c) Keep track of the number of guesses for the three random numbers d) Repeat the steps a) - c) x number of times in an outer loop, where x should be equal to or larger than 10,0000 e) Compute the average of guesses per try computed from x number of tries. 2) For the algorithm of guessing 3 random numbers in [0.. 9], you use two different algorithms listed below: a) Deterministic brute-force algorithm: In each try, it permutates 3 numbers in a deterministic way so that it guesses each set of 3 numbers only once while guessing the 3 random numbers. Each permutation of 3 numbers will be compared against three random numbers until they are correctly guessed. Guess the average number of guesses per try before you write your program and compare it against your simulation results. b) Pure random algorithm It will not use any prior information to guess the numbers. For each guess, it makes a fresh new guess for three new numbers randomly from scratch, and then it checks if the numbers are correct. If they are incorrect, it repeats the same process until the numbers are guessed correctly. Note that each set of guesses is completely independent. Theoretically, the upper bound of the number of guesses of this algorithm is unlimited. So, your program may stop guessing when the number of guesses reaches a certain max number (say 10,000) tries. You may record and display the number of such bailed-out cases if it happens. What would be the average number of guesses per try? Try to guess before you write your program and compare it against your simulation results. 3) This exercise may give some ideas on the difference between randomized algorithms (we will learn it later) and brute-force algorithms. Expected Output: announcements a) Deterministic brute-force guessing algorithm: Number of Tries: 10000 The highest number of guesses in a try: 998 The lowest number of tries: 3 The average number of tries: xxx.xx b) Pure random guessing algorithm Number of Tries: 10000 The highest number of guesses in a try: 8944 The lowest number of tries: 1 The average number of tries: xxX.XX Q3) Another guessing game: (10 points) 1) Write a code executing the following: a) First, randomly generate three numbers [0..9] (***The order among three numbers matters***) b) Then, continuously guess all three numbers until all three are guessed correctly. See below for two different ways of guessing three random numbers. c) Keep track of the number of guesses for the three random numbers d) Repeat the steps a) - c) x number of times in an outer loop, where x should be equal to or larger than 10,0000 e) Compute the average of guesses per try computed from x number of tries. 2) For the algorithm of guessing 3 random numbers in [0.. 9], you use two different algorithms listed below: a) Deterministic brute-force algorithm: In each try, it permutates 3 numbers in a deterministic way so that it guesses each set of 3 numbers only once while guessing the 3 random numbers. Each permutation of 3 numbers will be compared against three random numbers until they are correctly guessed. Guess the average number of guesses per try before you write your program and compare it against your simulation results. b) Pure random algorithm It will not use any prior information to guess the numbers. For each guess, it makes a fresh new guess for three new numbers randomly from scratch, and then it checks if the numbers are correct. If they are incorrect, it repeats the same process until the numbers are guessed correctly. Note that each set of guesses is completely independent. Theoretically, the upper bound of the number of guesses of this algorithm is unlimited. So, your program may stop guessing when the number of guesses reaches a certain max number (say 10,000) tries. You may record and display the number of such bailed-out cases if it happens. What would be the average number of guesses per try? Try to guess before you write your program and compare it against your simulation results. 3) This exercise may give some ideas on the difference between randomized algorithms (we will learn it later) and brute-force algorithms. Expected Output: announcements a) Deterministic brute-force guessing algorithm: Number of Tries: 10000 The highest number of guesses in a try: 998 The lowest number of tries: 3 The average number of tries: xxx.xx b) Pure random guessing algorithm Number of Tries: 10000 The highest number of guesses in a try: 8944 The lowest number of tries: 1 The average number of tries: xxX.XX