Algorithms are everywhere. You have probably executed a few already today. In this book, you will read about dozens of algorithms: some simple, some complex, some famous, some unknown, all interesting, and all worth learning. The first algorithm of the book is also the most delicious—it generates a berry granola parfait, and it’s shown in its entirety in Figure 1. You may be accustomed to calling this type of algorithm a “recipe,” but it fits Donald Knuth’s definition of an algorithm: a finite set of rules that gives a sequence of operations for solving a specific type of problem.

Parfait-making is not the only domain of life governed by algorithms. Every year, the US government requires each adult citizen to execute an algorithm, and strives to imprison those who fail to do so correctly. In 2017, millions of Americans fulfilled this duty by completing the algorithm shown in Figure 2, which is taken from a form called 1040-EZ.

How is it that taxes and parfaits can have anything in common? Taxes are inevitable, numeric, difficult, and universally disliked. Parfaits are infrequent, artistic, effortless, and adored without exception. The only trait they share is that people prepare both by following algorithms.

In addition to defining algorithm, the great computer scientist Donald Knuth noted that it is nearly synonymous with recipe, procedure, and rigmarole. In the case of filing taxes via the pictured 1040-EZ form, we have 12 steps (a finite list) that specify operations (like addition in step 4 and subtraction in step 6) to solve a specific type of problem: wanting to avoid being imprisoned for tax evasion. In the case of making a parfait, we have six finite steps that specify operations (like placing in step 1 and covering in step 2) to solve a specific type of problem: wanting to have a parfait in your hand or mouth.

As you learn more about algorithms, you will begin to see them everywhere and come to appreciate just how powerful they can be. In Chapter 1, we will discuss the remarkable human ability to catch a ball, and find out the details of the algorithm in the human subconscious that enables us to do so. Later, we will talk about algorithms for debugging code, deciding how much to eat at a buffet, maximizing revenue, sorting lists, scheduling tasks, proofreading text, delivering mail, and winning games like chess and sudoku. Along the way, we will learn to judge algorithms according to several attributes that professionals believe are important for them to possess. And we will begin to get a sense of the craftsmanship or even, dare we say, the art of algorithms, which provides scope for creativity and personality in an otherwise precise and quantitative endeavor.

Who Is This Book For?

This book provides a friendly introduction to algorithms, with accompanying Python code. To get the greatest possible benefit from it, you should have some experience with the following:

1. Programming/coding. Every major example in the book is illustrated with Python code. We strive to provide walkthroughs and explanations of every code snippet to make the book digestible for someone with no Python experience and not much programming experience. Nevertheless, someone who has at least some basic understanding of the fundamentals of programming—such as variable assignment, for loops, if/then statements, and function calls—will be the most prepared to benefit.
2. High school math. Algorithms are often used to accomplish many of the same goals as math, like solving equations, optimizing, and calculating values. Algorithms also apply many of the same principles that are associated with mathematical thinking, like logic and the need for precise definitions. Some of our discussions veer into mathematical territory, including algebra, the Pythagorean theorem, pi, and the teensiest bit of very basic calculus. We strive to avoid abstruseness and we don’t venture beyond the math taught in American high schools.

Anyone who feels comfortable with these prerequisites should be able to master all the content in this book. It was written with the following groups in mind:

1. Students. This book is suitable for an introductory class on algorithms, computer science, or programming at the high school or undergraduate level.
2. Professionals. Several types of professionals could gain valuable skills from this book, including developers or engineers who want to gain familiarity with Python, and developers who want to learn more about the foundations of computer science and how to improve code by thinking algorithmically.
3. Interested amateurs. The true target audience of this book is interested amateurs. Algorithms touch nearly every part of life, so everyone should be able to find at least something in this book that enhances their appreciation of the world around them.

About This Book

This book does not cover every aspect of every extant algorithm; it’s meant only as an introduction. After reading it, you will have a solid grasp of what an algorithm is, know how to write code to implement important algorithms, and understand how to judge and optimize algorithms’ performance. You will also be familiar with many of the most popular algorithms professionals use today. The chapters are organized as follows:

1. Chapter 1: Problem-Solving with Algorithms, in which we tackle the problem of how to catch a ball, find evidence for a subconscious algorithm governing human behavior, and discuss what that teaches us about the utility of algorithms and how to design them.
2. Chapter 2: Algorithms in History, in which we travel around the world and through history to find out how ancient Egyptians and Russian peasants multiplied numbers, how the ancient Greeks found greatest common divisors, and how medieval Japanese scholars created magic squares.
3. Chapter 3: Maximizing and Minimizing, in which we introduce gradient ascent and gradient descent. These simple methods for finding the maxima and minima of functions are used for optimization, an important goal of many algorithms.
4. Chapter 4: Sorting and Searching, in which we present fundamental algorithms for sorting lists and searching for elements within them. We also introduce how to measure the efficiency and speed of algorithms.
5. Chapter 5: Pure Math, in which we concern ourselves with purely mathematical algorithms, including those for generating continued fractions, calculating square roots, and generating pseudorandom numbers.
6. Chapter 6: Advanced Optimization, in which we cover an advanced method for finding optimal solutions: simulated annealing. We also introduce the traveling salesman problem, a standard problem in advanced computer science.
7. Chapter 7: Geometry, in which we go over how to generate Voronoi diagrams, which can be useful in a variety of geometric applications.
8. Chapter 8: Language, in which we discuss how to intelligently add spaces to a text that’s missing them, and how to intelligently suggest the next words in phrases.
9. Chapter 9: Machine Learning, in which we discuss decision trees, a fundamental machine learning method.
10. Chapter 10: Artificial Intelligence, in which we jump to an ambitious project: implementing an algorithm that can play games against us—and maybe even win. We start with a simple game, dots and boxes, and discuss how we could improve performance.
11. Chapter 11: Forging Ahead, in which talk about how to progress to more advanced work related to algorithms. We discuss how to build a chatbot, and how to win a million dollars by creating a sudoku algorithm.

Setting Up the Environment

We’ll implement the algorithms described in this book by using the Python language. Python is free and open source, and it runs on every major platform. You can use the following steps to install Python on Windows, macOS, and Linux.

Install Python on Windows

To install Python on Windows, follow these steps:

1. Open the page dedicated to the latest version of Python for Windows (make sure you include the final slash): https://www.python.org/downloads/windows/.
2. Click the link for the Python release you want to download. To download the most recent release, click the link Latest Python 3 Release - 3.X.Y, where 3.X.Y is the latest version number, like 3.8.3. The code in this book was tested on both Python 3.6 and Python 3.8. If you’re interested in downloading an older version, scroll down on this page to the Stable Releases section to find a release you prefer.
3. The link you clicked in step 2 takes you to a page dedicated to your chosen Python release. In the Files section, click the Windows x86-64 executable installer link.
4. The link in step 3 downloads a .exe file to your computer. This is an installer file; double-click it to open it. It will execute the installation process automatically. Check the box Add Python 3.X to PATH where X is the release number of the installer you downloaded, like 8. After that, click Install Now and choose the default options.
5. When you see the “Setup was successful” message, click Close to complete the installation process.

There is now a new application on your computer. Its name is Python 3.X, where X is the version of Python 3 that you installed. In the Windows search bar, type Python. When the application appears, click it to open a Python console. You can enter Python commands in this console, and they’ll run there.

Install Python on macOS

To install Python on macOS follow these steps:

1. Open the page dedicated to the latest version of Python for macOS (make sure you include the final slash): https://www.python.org/downloads/mac-osx/.
2. Click the link for the Python release you want to download. To download the most recent release, click the link Latest Python 3 Release - 3.X.Y, where 3.X.Y is the latest version number, like 3.8.3. The code in this book was tested on both Python 3.6 and Python 3.8. If you’re interested in downloading an older version, scroll down on this page to the Stable Releases section to find a release you prefer.
3. The link you clicked in step 2 takes you to a page dedicated to the latest Python release. In the Files section, click the macOS 64-bit installer link.
4. The link in step 3 downloads a .pkg file to your computer. This is an installer file; double-click it to open it. It will execute the installation process automatically. Choose the default options.
5. The installer will create a folder on your computer called Python 3.X, where X is the number of the Python release you installed. In this folder, double-click the icon labeled IDLE. This will open the Python 3.X.Y Shell, where 3.X.Y is the latest version number. This is a Python console where you can run any Python commands.

Install Python on Linux

To install Python on Linux follow these steps:

1. Determine which package manager your version of Linux uses. Two common examples of package managers are yum and apt-get.
2. Open the Linux console (also called the terminal), and execute the following two commands:

   > sudo apt-get update
   > sudo apt-get install python3.8

   If you are using yum or some other package manager, replace both instances of apt-get in these two lines with yum or the name of your package manager. Likewise, if you want to install an older version of Python, replace 3.8 (the latest version number at the time of this writing) with any other release number, like 3.6, one of the versions used to test the code in this book. To see what the latest version of Python is, go to https://www.python.org/downloads/source/. There, you will see a Latest Python 3 Release - Python 3.X.Y link, where 3.X.Y is a release number; use the first two digits in the installation command just shown.

3. Run Python by executing the following command in the Linux console:

   python3

The Python console opens in the Linux console window. You can enter Python commands here.

Installing Third-Party Modules

Some of the code we’ll introduce in this book will rely on Python modules that are not part of the core Python software that you downloaded from Python’s official website. To install third-party modules on your computer, follow the instructions at http://automatetheboringstuff.com/2e/appendixa/.

Summary

Our study of algorithms will take us around the world and many centuries back through history. We’ll explore innovations from ancient Egypt, Babylon, Periclean Athens, Baghdad, medieval Europe, Edo Japan, and the British Raj, all the way up to our remarkable present day and its breathtaking technology. We’ll be pushed to find new ways around problems and through constraints that initially seem impossible to confront. In doing so, we’ll connect not only to the pioneers of ancient science but also to anyone today who uses a computer or catches a ball, to generations of algorithm users and creators yet unborn who will build on what we leave to them in faraway times. This book is the beginning of your adventure with algorithms.