Algorithms For Dummies. John Paul Mueller

to warfare (see a history of this approach at https://classroom.synonym.com/civilization-invented-divide-conquer-strategy-12746.html). However, people use the same ideas to cut problems of all sorts down to size.

The third section of the chapter refers to the greedy approach to problem solving. Greed normally has a negative connotation (like stealing your friend’s fruit cup from their plate), but not in this case. A greedy algorithm is one that makes an optimal choice at each problem-solving stage. By doing so, it hopes to obtain an overall optimal solution to solve the problem. Unfortunately, this strategy doesn’t always work, but it’s always worth a try. It often yields a good enough solution, making it a good baseline.

      No matter what problem-solving approach you choose, every algorithm comes with costs. Being good shoppers, people who rely heavily on algorithms want the best possible deal, which means performing a cost/benefit analysis. Of course, getting the best deal also assumes that a person using the algorithm has some idea of what sort of solution is good enough. Getting a solution that is too precise (one that offers too much detail) or one that offers too much in the way of output is often wasteful, so part of keeping costs under control is getting what you need as output and nothing more.

      To know what you have with an algorithm, you need to know how to measure it in various ways. Measurements create a picture of usability, size, resource usage, and cost in your mind. More important, measurements offer the means of making comparisons. You can’t compare algorithms without measurements. Until you can compare the algorithms, you can’t choose the best one for a task.

Starting to Solve a Problem

      Before you can solve any problem, you must understand it. Doing so isn’t just a matter of sizing up the problem, either. Knowing that you have certain inputs and require certain outputs is a start, but that’s not really enough to create a solution. Part of the solution process is to

       Discover how other people have created new problem solutions

       Know what resources you have on hand

       Determine the sorts of solutions that worked for similar problems in the past

       Consider what sorts of solutions haven’t produced a desirable result

      The following sections help you understand these phases of solving a problem. Realize that you won’t necessarily perform these phases in order and that sometimes you revisit a phase after getting more information. The process of starting a problem solution is iterative; you keep at it until you have a good understanding of the problem at hand.

      Modeling real-world problems

      Real-world problems differ from those found in textbooks, mostly because the real world has no imagination at all. When creating a textbook, the author often creates a simple example to help the reader understand the basic principles at work. The example models just one aspect of a more complex problem. A real-world problem may require that you combine several techniques to create a complete solution. For example, to locate the best answer to a problem, you may:

      1 Need to sort the answer set by a specific criterion.

      2 Perform some sort of filtering and transformation.

      3 Search the result.

      Without this sequence of steps, comparing each of the answers adequately may prove impossible, and you end up with a less-than-optimal result. A series of algorithms used together to create a desired result is an ensemble. You can read about their use in machine learning in Machine Learning For Dummies, 2nd Edition, by John Paul Mueller and Luca Massaron (Wiley). The article at https://machinelearningmastery.com/tour-of-ensemble-learning-algorithms/ gives you a quick overview of how ensembles work.

      However, real-world problems are even more complex than simply looking at static data or iterating that data only once. For example, anything that moves, such as a car, airplane, or robot, receives constant input. Each updated input includes error information that a real-world solution will need to incorporate into the result in order to keep these machines working properly. In addition to other algorithms, the constant calculations require the proportional integral derivative (PID) algorithm (see https://www.ni.com/en-us/innovations/white-papers/06/pid-theory-explained.html for a detailed explanation of this algorithm) to control the machine using a feedback loop. Every calculation brings the solution used to control the machine into better focus, which is why machines often go through a settling stage when you first turn them on.

When modeling a real-world problem, you must also consider non-obvious issues that crop up. An obvious solution, even one based on significant mathematical input and solid theory, may not work. For example, during WWII, the allies had a serious problem with bomber losses. Therefore, the engineers analyzed every bullet hole in every plane that came back. After the analysis, the engineers used their solution to armor the allied planes more heavily to ensure that more of them would come back. It didn’t work. Enter Abraham Wald. This mathematician suggested a non-obvious solution: Put armor plating in all the places that lacked bullet holes (because the areas with bullet holes are already strong enough; otherwise the plane wouldn’t have returned). The resulting solution did work and is now used as the basis for survivor bias (the fact that the survivors of an incident often don’t show what actually caused a loss) in working with algorithms. You can read more about this fascinating bit of history at https://medium.com/@penguinpress/an-excerpt-from-how-not-to-be-wrong-by-jordan-ellenberg-664e708cfc3d.

      Real-world modeling may also include the addition of what scientists normally consider undesirable traits. For example, scientists often consider noise undesirable because it hides the underlying data. Consider a hearing aid, which removes noise to enable someone to hear better (see the discussion at https://www.ncbi.nlm.nih.gov/pmc/articles/PMC4111515/ for details). Many methods exist for removing noise, some of which you can find in this book starting with Chapter 9 as part of other topic discussions.

      However, as counterintuitive as it might seem, adding noise to the data also requires an algorithm that provides useful output with that noise in place. For example, Ken Perlin wanted to get rid of the machine-like look of computer-generated graphics in 1983, and he created an algorithm to do so. The result is Perlin noise (see https://catlikecoding.com/unity/tutorials/pseudorandom-noise/perlin-noise/ for details). The effect is so useful that Perlin won an Academy Award for his work (see https://cs.nyu.edu/~perlin/doc/oscar.html for details). A real-world scenario often requires choices that may not be obvious when working in the lab or during the learning process.

      

The main gist of this section is that solutions often require several iterations to create, you may have to spend a lot of time refining them, and obvious solutions may not work at all. When modeling a real-world problem, you do begin with the solutions found in textbooks, but then you must move beyond theory to find the actual solution to your problem. As this book progresses, you’re exposed to a wide variety of algorithms — all of which help you find solutions. The important thing to remember is that you may need to combine these examples in various ways and discover methods for