Python Algorithms Part 1 – Binary SearchLet's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. If I choose an integer from 1 to 16 and ask you to guess what the number is, you can keep guessing numbers until you hit on it. When you guess wrong, I tell you whether you are too high or too low. Once you've guessed the number, think about the technique you used to decide each of your next guesses.If you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number, you used an approach called “linear search,” meaning you guessed the numbers serially and sequentially, as if they were lined up in a row. This is definitely one way to find the mystery number, but it could require as many as 16 guesses. However, you could get lucky, if the number was 1, you’d only need 1 guess. Using a linear search process, on average, you'd need 8 guesses.There is an approach that is more efficient than just guessing 1, 2, 3, 4, ... Remember that the computer you were told whether a guess was too low, too high, or correct. So, if you started by guessing 8, the target number must be lower, or higher, or you’ve guessed it. If the target number is less than 8, you know that 8 and above are too high, so you can eliminate the numbers 8 to 16 from consideration. If the target number is greater than 8, then 1 through 8 can be eliminated. Whether high or low, half the numbers are eliminated from consideration. The pool of possible numbers is reduced by half. Your next guess, if you don’t guess the number, should also eliminate half of the remaining numbers in the same manner as above. Keep repeating this process until the target number is found. This approach is called a “binary search” because you split the number pool in half on each guess. For any number in the range 1 to 16, you should be able to find a number in at most 4 guesses.Perform the following activities and answer the associated questions. Post your results in a narrative to the Discussion Forum. 1. Perform a binary search for an integer number in the range of 1 to 300. How many guesses did it take? More than 9?2. Perform a binary search for an integer number in the range of 1 to 5000. How many guesses did it take? Why? Part 2 – A Daily TaskNearly all routine tasks that we do virtually every day follow an established pattern of steps that when completed produce a result or outcome. All tasks can be broken into steps that perform a single action on a single input to produce a single output, which, in turn, is likely the input to the next step. Choose a relatively simple (meaning not complex or lengthy) task from everyday life and create an algorithm that achieves its normal objective or outcome. Some common tasks, like brushing your teeth, or shaving (face/legs/whatever), or making a cake, may be way too complicated for this exercise. However, you’re free to do something like these, but it’s recommended that you choose something simpler – maybe just a portion of a larger task. Post your algorithm to the Discussion Form as Part 2 and number each step consecutively

Python Algorithms Part 1 – Binary SearchLet's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. If I choose an integer from 1 to 16 and ask you to guess what the number is, you can keep guessing numbers until you hit on it. When you guess wrong, I tell you whether you are too high or too low. Once you've guessed the number, think about the technique you used to decide each of your next guesses.If you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number, you used an approach called “linear search,” meaning you guessed the numbers serially and sequentially, as if they were lined up in a row. This is definitely one way to find the mystery number, but it could require as many as 16 guesses. However, you could get lucky, if the number was 1, you’d only need 1 guess. Using a linear search process, on average, you'd need 8 guesses.There is an approach that is more efficient than just guessing 1, 2, 3, 4, ... Remember that the computer you were told whether a guess was too low, too high, or correct. So, if you started by guessing 8, the target number must be lower, or higher, or you’ve guessed it. If the target number is less than 8, you know that 8 and above are too high, so you can eliminate the numbers 8 to 16 from consideration. If the target number is greater than 8, then 1 through 8 can be eliminated. Whether high or low, half the numbers are eliminated from consideration. The pool of possible numbers is reduced by half. Your next guess, if you don’t guess the number, should also eliminate half of the remaining numbers in the same manner as above. Keep repeating this process until the target number is found. This approach is called a “binary search” because you split the number pool in half on each guess. For any number in the range 1 to 16, you should be able to find a number in at most 4 guesses.Perform the following activities and answer the associated questions. Post your results in a narrative to the Discussion Forum. 1. Perform a binary search for an integer number in the range of 1 to 300. How many guesses did it take? More than 9?2. Perform a binary search for an integer number in the range of 1 to 5000. How many guesses did it take? Why? Part 2 – A Daily TaskNearly all routine tasks that we do virtually every day follow an established pattern of steps that when completed produce a result or outcome. All tasks can be broken into steps that perform a single action on a single input to produce a single output, which, in turn, is likely the input to the next step. Choose a relatively simple (meaning not complex or lengthy) task from everyday life and create an algorithm that achieves its normal objective or outcome. Some common tasks, like brushing your teeth, or shaving (face/legs/whatever), or making a cake, may be way too complicated for this exercise. However, you’re free to do something like these, but it’s recommended that you choose something simpler – maybe just a portion of a larger task. Post your algorithm to the Discussion Form as Part 2 and number each step consecutively

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Python Algorithms

Part 1 – Binary SearchLet's play a little game to give you an idea of how different algorithms for the same problem can have wildly different efficiencies. If I choose an integer from 1 to 16 and ask you to guess what the number is, you can keep guessing numbers until you hit on it. When you guess wrong, I tell you whether you are too high or too low. Once you've guessed the number, think about the technique you used to decide each of your next guesses.If you guessed 1, then 2, then 3, then 4, and so on, until you guessed the right number, you used an approach called “linear search,” meaning you guessed the numbers serially and sequentially, as if they were lined up in a row. This is definitely one way to find the mystery number, but it could require as many as 16 guesses. However, you could get lucky, if the number was 1, you’d only need 1 guess. Using a linear search process, on average, you'd need 8 guesses.There is an approach that is more efficient than just guessing 1, 2, 3, 4, ... Remember that the computer you were told whether a guess was too low, too high, or correct. So, if you started by guessing 8, the target number must be lower, or higher, or you’ve guessed it. If the target number is less than 8, you know that 8 and above are too high, so you can eliminate the numbers 8 to 16 from consideration. If the target number is greater than 8, then 1 through 8 can be eliminated. Whether high or low, half the numbers are eliminated from consideration. The pool of possible numbers is reduced by half. Your next guess, if you don’t guess the number, should also eliminate half of the remaining numbers in the same manner as above. Keep repeating this process until the target number is found. This approach is called a “binary search” because you split the number pool in half on each guess. For any number in the range 1 to 16, you should be able to find a number in at most 4 guesses.Perform the following activities and answer the associated questions. Post your results in a narrative to the Discussion Forum. 1. Perform a binary search for an integer number in the range of 1 to 300. How many guesses did it take? More than 9?2. Perform a binary search for an integer number in the range of 1 to 5000. How many guesses did it take? Why?

Part 2 – A Daily TaskNearly all routine tasks that we do virtually every day follow an established pattern of steps that when completed produce a result or outcome. All tasks can be broken into steps that perform a single action on a single input to produce a single output, which, in turn, is likely the input to the next step. Choose a relatively simple (meaning not complex or lengthy) task from everyday life and create an algorithm that achieves its normal objective or outcome. Some common tasks, like brushing your teeth, or shaving (face/legs/whatever), or making a cake, may be way too complicated for this exercise. However, you’re free to do something like these, but it’s recommended that you choose something simpler – maybe just a portion of a larger task. Post your algorithm to the Discussion Form as Part 2 and number each step consecutively

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps with 3 images

SEE SOLUTION Check out a sample Q&A here