Getting Started with Algorithms

  Introducing Algorithms

If you’re in the majority of people, you’re likely confused as you open this book and begin your adventure with algorithms, because most texts never tell you what an algorithm is, much less why you’d want to use one. Hearing about algorithms is like being in school again with the teacher droning on; you’re falling asleep from lack of interest because algorithms don’t seem particularly useful to understand at the moment.

 The first section of this chapter is dedicated to helping you understand precisely what the term algorithm means and why you benefit from knowing how to use algorithms. Far from being arcane, algorithms are actually used all over the place, and you have probably used or been helped by them for years without really know ing it. So, they’re stealth knowledge! In truth, algorithms are becoming the spine that supports and regulates what is important in an increasingly complex and technological society like ours.

 The second section of this chapter discusses how you use computers to create solutions to problems using algorithms, how to distinguish between issues and solutions, and what you need to do to manipulate data to discover a solution. The goal is to help you differentiate between algorithms and other tasks that people confuse with algorithms. In short, you discover why you really want to know about algorithms, as well as how to apply them to data..

The third section of the chapter discusses algorithms in a real-world manner, that is, by viewing the terminologies used to understand algorithms and to present algorithms in a way that shows that the real world is often less than perfect. Understanding how to describe an algorithm in a realistic manner also helps to temper expectations to reflect the realities of what an algorithm can actually do.

The final section of the chapter discusses data. The algorithms you work with in this book require data input in a specific form, which sometimes means changing the data to match the algorithm’s requirements. Data manipulation doesn’t change the content of the data. Instead, it changes the presentation and form of the data so that an algorithm can help you see new patterns that weren’t apparent before (but were actually present in the data all along).

Describing Algorithms

 Even though people have solved algorithms manually for thousands of years, doing so can consume huge amounts of time and require many numeric computa tions, depending on the complexity of the problem you want to solve. Algorithms are all about finding solutions, and the speedier and easier, the better. A huge gap exists between mathematical algorithms historically created by geniuses of their time, such as Euclid and modern algorithms created in universities as well as private research and development laboratories. The main reason for this gap is the use of computers. Using computers to solve problems by employing the appro priate algorithm speeds up the task significantly. You may notice that more prob lem solutions appear quickly today, in part, because computer power is both cheap and constantly increasing

 When working with algorithms, you consider the inputs, desired outputs, and the process (a sequence of actions) used to obtain a desired output from a given input. However, you can get the terminology wrong and view algorithms in the wrong way because you haven’t really considered how they work in a real-world setting.

 Sources of information about algorithms often present them in a way that proves confusing because they’re too sophisticated or even downright incorrect. Although you may find other definitions, this book uses the following definitions for terms that people often confuse with algorithms (but aren’t)

 Equation: Numbers and symbols that, when taken as a whole, equate to a specific value. An equation always contains an equals sign so that you know that the numbers and symbols represent the specific value on the other side of the equals sign. Equations generally contain variable information presented as a symbol, but they’re not required to use variables.

 Formula: A combination of numbers and symbols used to express informa tion or ideas. Formulas normally present mathematical or logical concepts, such as defining the Greatest Common Divisor (GCD) of two integers (the video at https://www.khanacademy.org/math/cc-sixth-grade-math/ cc-6th-factors-and-multiples/cc-6th-gcf/v/greatest-common- divisor tells how this works). Generally, they show the relationship between two or more variables.

Algorithm: A sequence of steps used to solve a problem. The sequence presents a unique method of addressing an issue by providing a particular solution. An algorithm need not represent mathematical or logical concepts, even though the presentations in this book often do fall into those categories because people most commonly use algorithms in this manner. In order for a process to represent an algorithm, it must be

Finite: The algorithm must eventually solve the problem. This book discusses problems with a known solution so that you can evaluate whether an algorithm solves the problem correctly.

Well-defined: The series of steps must be precise and present steps that are understandable. Especially because computers are involved in algorithm use, the computer must be able to understand the steps to create a usable algorithm.

Effective: An algorithm must solve all cases of the problem for which someone defined it. An algorithm should always solve the problem it has to solve. Even though you should anticipate some failures, the incidence of failure is rare and occurs only in situations that are acceptable for the intended algorithm use

With these definitions in mind, the following sections help to clarify the precise nature of algorithms. The goal isn’t to provide a precise definition for algorithms, but rather to help you understand how algorithms fit into the grand scheme of things so that you can develop your own understanding of what algorithms are and why they’re so important.

The right way to make toast: Defining algorithm uses

 An algorithm always presents a series of steps and doesn’t necessarily perform these steps to solve a math formula. The scope of algorithms is incredibly large. You can find algorithms that solve problems in science, medicine, finance, indus trial production and supply, and communication. Algorithms provide support for all parts of a person’s daily life. Anytime a sequence of actions achieving some thing in our life is finite, well-defined, and effective, you can view it as an algo rithm. For example, you can turn even something as trivial and simple as making toast into an algorithm. In fact, the making toast procedure often appears in com puter science classes, as discussed at http://brianaspinall.com/now-thats- how-you-make-toast-using-computer-algorithms/.

 Unfortunately, the algorithm on the site is flawed. The instructor never removes the bread from the wrapper and never plugs the toaster in, so the result is dam aged plain bread still in its wrapper stuffed into a nonfunctional toaster (see the discussion at http://blog.johnmuellerbooks.com/2013/03/04/procedures- in-technical-writing/ for details). Even so, the idea is the correct one, yet it requires some slight, but essential, adjustments to make the algorithm finite and effective

 One of the most common uses of algorithms is as a means of solving formulas. For example, when working with the GCD of two integer values, you can perform the task manually by listing each of the factors for the two integers and then selecting the greatest factor that is common to both. For example, GCD (20, 25) is 5 because 5 is the largest number that divides evenly into both 20 and 25. However, process ing every GCD manually is time consuming and error prone, so the Greek mathe matician Euclid created a better algorithm to perform the task. You can see the Euclidean method demonstrated at https://www.khanacademy.org/computing/ computer-science/cryptography/modarithmetic/a/the-euclidean- algorithm

 However, a single formula, which is a presentation of symbols and numbers used to express information or ideas, can have multiple solutions, each of which is an algorithm. In the case of GCD, another common algorithm is one created by Derrick Henry Lehmer (https://www.imsc.res.in/~kapil/crypto/notes/ node11.html). Because you can solve any formula multiple ways, people spend a great deal of time comparing algorithms to determine which one works best in a given situation. (See a comparison of Euclid to Lehmer at http://citeseerx. ist.psu.edu/viewdoc/download?doi=10.1.1.31.693&rep=rep1&type=pdf.)

 Because our society and its accompanying technology are changing quickly, we need algorithms that can keep the pace. Scientific achievements such as sequencing the human genome were possible in our age because scientists found algorithms that run fast enough to complete the task. Measuring which algorithm is better in a given situation, or in an average usage situation, is really serious stuff and is a topic of discussion among computer scientists.

When it comes to computer science, the same algorithm can have multiple presentations; why do it one way when you can invent multiple methods just for fun? For example, you can present the Euclidean algorithm in both recursive and iterative forms, as explained at http://cs.stackexchange.com/questions/1447/ what-is-most-efficient-for-gcd. In short, algorithms present a method of solving formulas, but it would be a mistake to say that just one acceptable algo rithm exists for any given formula or that only one acceptable presentation of an algorithm exists. Using algorithms to solve problems of various sorts has a long history — it isn’t something that has just happened.

Even if you limit your gaze to computer science, data science, artificial intelli gence, and other technical areas, you find many kinds of algorithms — too many for a single book. For example, The Art of Computer Programming, by Donald E. Knuth (Addison-Wesley), spans 3,168 pages in four volumes (see http:// www.amazon.com/exec/obidos/ASIN/0321751043/datacservip0f-20/) and still doesn’t manage to cover the topic (the author intended to write more volumes). However, here are some interesting uses for you to consider 

 Searching: Locating information or verifying that the information you see is the information you want is an essential task. Without this ability, you couldn’t perform many tasks online, such as finding the website on the Internet selling the perfect coffee pot for your office. These algorithms change constantly, as shown by Google’s recent change in its algorithm (https://www.youaretech. com/blog/2021/1/26/webpage-experience-a-major-google-algorithm- update-in-2021nbsp).

 Sorting: Determining which order to use to present information is important because most people today suffer from information overload, and putting information in order is one way to reduce the onrush of data. Imagine going to Amazon, finding that more than a thousand coffee pots are for sale there, and yet not being able to sort them in order of price or the most positive review. Moreover, many complex algorithms require data in the proper order to work dependably, so ordering is an important requisite for solving more problems

 Transforming: Converting one sort of data to another sort of data is critical to understanding and using the data effectively. For example, you might understand imperial weights just fine, but all your sources use the metric system. Converting between the two systems helps you understand the data

 Scheduling: Making the use of resources fair to all concerned is another way in which algorithms make their presence known in a big way. For example, timing lights at intersections are no longer simple devices that count down the seconds between light changes. Modern devices consider all sorts of issues, such as the time of day, weather conditions, and flow of traffic

 Graph analysis: Deciding on the shortest path between two points finds all sorts of uses. For example, in a routing problem, your GPS couldn’t function without this particular algorithm because it could never direct you along city streets using the shortest route from point A to point B. And even then, your GPS might direct you to drive into a lake (https://theweek.com/articles/464674/8- drivers-who-blindly-followed-gps-into-disaster).

 Cryptography: Keeping data safe is an ongoing battle with hackers constantly attacking data sources. Algorithms make it possible to analyze data, put it into some other form, and then return it to its original form later.

 Pseudorandom number generation: Imagine playing games that never varied. You start at the same place; perform the same steps, in the same manner, every time you play. Without the capability to generate seemingly random numbers, many computer tasks become impossible

 This list presents an incredibly short overview. People use algorithms for many different tasks and in many different ways, and constantly create new algorithms to solve both existing problems and new problems. The most important issue to consider when working with algorithms is that given a particular input, you should expect a specific output. Secondary issues include how many resources the algorithm requires to perform its task and how long it takes to complete the task. Depending on the kind of issue and the sort of algorithm used, you may also need to consider issues of accuracy and consistency.

 Finding algorithms everywhere

 The previous section mentions the toast algorithm for a specific reason. For some reason, making toast is probably the most popular algorithm ever created. Many grade-school children write their equivalent of the toast algorithm long before they can even solve the most basic math. It’s not hard to imagine how many variations of the toast algorithm exist and what the precise output is of each of them. The results likely vary by individual and the level of creativity employed. There are also websites dedicated to telling children about algorithms, such as the one at https://www.idtech.com/blog/algorithms-for-kids. In short, algo rithms appear in great variety and often in unexpected places.

Every task you perform on a computer involves algorithms. Some algorithms appear as part of the computer hardware. The very act of booting a computer involves the use of an algorithm. You also find algorithms in operating systems, applications, and every other piece of software. Even users rely on algorithms. Scripts help direct users to perform tasks in a specific way, but those same steps could appear as written instructions or as part of an organizational policy statement.

 Daily routines often devolve into algorithms. Think about how you spend your day. If you’re like most people, you perform essentially the same tasks every day in the same order, making your day an algorithm that solves the problem of how to live successfully while expending the least amount of energy possible. After all, that’s what a routine does; it makes us efficient.

Using Computers to Solve Problems

 The term computer sounds quite technical and possibly a bit overwhelming to some people, but people today are neck deep (possibly even deeper) in computers. You wear at least one computer, your smartphone, most of the time. If you have any sort of special device, such as a pacemaker, it also includes a computer. A car can contain as many as 150 computers in the form of embedded microprocessors that regulate fuel consumption, engine combustion, transmission, steering, and stability (see https://spectrum.ieee.org/software-eating-car for details), provide Advanced Driver-Assist Systems (ADAS), and more lines of code than a jet f ighter. A computer exists to solve problems quickly and with less effort than solving them manually. Consequently, it shouldn’t surprise you that this book uses still more computers to help you understand algorithms better.

 Computers vary in a number of ways. The computer in a watch is quite small; the one on a desktop quite large. Supercomputers are immense and contain many smaller computers all tasked to work together to solve complex issues, such as predicting tomorrow’s weather. The most complex algorithms rely on special computer functionality to obtain solutions to the issues people design them to solve. Yes, you could use lesser resources to perform the task, but the trade-off is waiting a lot longer for an answer, or getting an answer that lacks sufficient accuracy to provide a useful solution. In some cases, you wait so long that the answer is no longer important. With the need for both speed and accuracy in mind, the following sections discuss some special computer features that can affect algorithms