Core Python / Problem Solving by Programming#
Describe the steps outlined in “The Seven Steps” approach for creating algorithms. How does this method facilitate problem-solving in computer programming?
List the seven steps. This method is designed to create a systematic approach for solving a problem. By working through the problem by hand, we can start to elicit the various steps needed to solve the problem. From that, we write down those steps. At this point, we then need to look at how we can solve different instances of the same problem (i.e., create a generic solution). Then we need to make sure our generalized steps can be followed to
solve the problem.How does Step Three in “The Seven Steps” involve generalizing the solution to a problem? Provide an example of how this step can lead to more versatile algorithms.
Ultimately, Step Three involves generalizing the solution to a problem by abstracting away specific details and patterns and identifying the essential components of the problem. It also looks at what possible inputs could be used in the algorithm.
Some of the ways this step can lead to a more versatile algorithm:
Identifying Patterns: Find common patterns or structures that occur across different instances of the problem.
Abstracting Details: Generalization involves abstracting away specific details or constraints that are unique to a particular instance of the problem. Instead of focusing on these specifics, the algorithm should operate on a higher level of abstraction, making it applicable to a broader range of scenarios.
Creating Reusable Components: Generalizing the solution often involves creating reusable components or functions that can be applied to different parts of the problem (as well as other problems).
Adapting to Different Inputs: A generalized algorithm should be able to adapt to different types of inputs or variations of the problem. The algorithm becomes more flexible and can handle a wider range of scenarios without requiring significant modifications.
What is the importance of testing algorithms, as mentioned in Step Four? How do corner cases contribute to testing the robustness of an algorithm? Manually testing algorithms is crucial for several reasons:
Correctness Verification: Testing helps ensure that the algorithm produces the correct output for various inputs. Does the algorithm behave as expected and does the algorithm solve the problem accurately?
Identify Defects and Errors: Testing allows developers to detect and fix bugs and errors in the algorithm implementation. By subjecting the algorithm to different test cases, developers can uncover edge cases or unexpected behavior that may lead to incorrect results.
Performance Evaluation: Testing provides insights into the algorithm’s performance, including how much time and memory may be required. If it’s taking a long time to manually execute an algorithm, explore creating alternate approaches.
Corner cases play a vital role in testing the robustness of an algorithm by examining its behavior under extreme or unusual conditions. These cases represent scenarios that are unlikely to occur in typical usage but are still within the realm of possibility. Examples of corner cases include:
Empty input: What happens when the algorithm receives an empty input or an input with no elements?
Single-element input: How does the algorithm handle inputs with only one element?
Maximum or minimum input values: How does the algorithm behave when presented with the largest or smallest possible input values?
What is an IPOT Chart, and how does it aid in documenting algorithms? Create a generalized version for the travelling saleperson problem listed in the previous notebook.
An IPOT chart, short for Input-Process-Output-Testing chart, is a representation used to document algorithms breaking an algorithm down into those components.
For the problem: (time required to check all permutations)
inputs: number of cities, number of tries per seconds
processing:
Compute the total number of permutations for visiting the different cities (factorial)
Divide that number by the number of tries per second
Convert the number of seconds to days
outputs: number of days to check all permutations of visiting the cities
tests:
20 cities, 20,158 days
0 cities, 0 days
-1 cities, invalid (factorial is not defined for negative numbers)
a large number to look at what happens when the output can not be shown would also be useful.
Why do we need to explicitly document the steps in an algorithm? Create an IPOT chart for making a bowl of cereal. Computers cannot infer activities. They follow directions precisely.
inputs: cereal, milk, bowl
processing:
Prepare Work Surface: Ensure a clean and dry surface area to work on.
Open cereal box: Use hands to open the cereal box by lifting or tearing the top flap.
Retrieve bowl: Reach for a clean bowl from the designated storage area.
Pour cereal into bowl: a. Hold the opened cereal box over the bowl. b. Gently tilt the box to pour the desired amount of cereal into the bowl. c. Stop pouring when the desired portion is reached.
Close cereal box: Seal the cereal box by folding or securing the top flap.
Retrieve milk container: Reach for the milk container from the designated storage area.
Open milk container: Use hands to twist or lift the lid of the milk container.
Pour milk into bowl:
Hold the opened milk container over the bowl containing cereal.
Gently tilt the container to pour the desired amount of milk over the cereal.
Stop pouring when the desired amount is reached.
Close milk container: Securely close the lid of the milk container by twisting or sealing it.
outputs: number of days to check all permutations of visiting the cities
tests:
missing ingredients, unable to proceed
some milk, will need to make a smaller bowl of cereal
proper sizing of cereal, milk, and bowl -> the perfect breakfast
some cereal, use smaller amounts of milk
small bowl - use less cereal and milk
What is an algorithm?
A clear set of steps to solve any instance of a particular class of problems. A key part of programming is developing unique algorithms to solve problems as well as figuring out when to use existing algorithms to aid in those solutions.
If you are unable to complete Step 1 of the Seven Steps, which of the following could be a viable path forward?
Gain more domain knowledge for the particular problem’s domain. You can also look to get help from others - whether it’s fellow students, co-workers, or people on the internet, but recognize the difference between doing the work for you versus helping you overcome a barrier.
What are parameters?
Symbolic placeholders in an algorithm for the values that specify what particular instance of the problem is being solved. For the travelling salesperson person problem, this could be a different number of cities to visit and the number of tries per second.
What are corner cases?
Combinations of parameter values that require special handling. For the travelling salesperson person problem, this could be setting the number of cities to 0,1, or a very large number.