The Self-Taught Computer Scientist. Cory Althoff

1 What Is an Algorithm?

       Whether you want to uncover the secrets of the universe or you just want to pursue a career in the 21st century, basic computer programming is an essential skill to learn.

      Stephen Hawking

      An algorithm is a sequence of steps that solves a problem. For example, one algorithm for making scrambled eggs is to crack three eggs over a bowl, whisk them, pour them into a pan, heat the pan on a stove, stir them, and remove them from the pan once they are no longer runny. This section of the book is all about algorithms. You will learn algorithms you can use to solve problems such as finding prime numbers. You will also learn how to write a new, elegant type of algorithm and how to search and sort data.

      In this chapter, you will learn how to compare two algorithms to help you analyze them. It is important for a programmer to understand why one algorithm may be better than another because programmers spend most of their time writing algorithms and deciding what data structures to use with them. If you have no idea why you should choose one algorithm over another, you will not be a very effective programmer, so this chapter is critical.

      While algorithms are a fundamental concept in computer science, computer scientists have not agreed on a formal definition. There are many competing definitions, but Donald Knuth's is among the best known. He describes an algorithm as a definite, effective, and finite process that receives input and produces output based on this input.

      A common addition to this list is correctness. An algorithm should always produce the same output for a given input, and this output should be the correct answer to the problem the algorithm solves.

Most, but not all, algorithms fulfill these requirements, and some of the exceptions are important. For example, when you create a random number generator, your goal is to generate randomness so someone can't use the input to guess the output. Also, many algorithms in data science are not strict about correctness. For example, it may be sufficient for an algorithm to estimate output, as long as the estimate's uncertainty is known. In most cases, however, your algorithms should fulfill all the previous requirements. If you write an algorithm for making scrambled eggs, the user might not be happy if, occasionally, the algorithm produces an omelet or boiled eggs instead.

Analyzing Algorithms

      There is often more than one algorithm we can use to solve a problem. For example, there are several different ways to sort a list. When several algorithms solve a problem, how do you know which one is best? Is it the simplest? The fastest? The smallest? Or something else?

      One way to judge an algorithm is by its run time. An algorithm's run time is the amount of time it takes your computer to execute an algorithm written in a programming language like Python. For example, here is an algorithm in Python that counts from 1 to 5 and prints each number:

      for i in range(1, 6): print(i)

      You can measure this algorithm's run time using Python's built-in time module to track how long your computer takes to execute it:

      import time start = time.time() for i in range(1, 6): print(i) end = time.time() print(end – start) >> 1 >> 2 >> 3 >> 4 >> 5 >> 0.15141820907592773

      When you run your program, it prints the numbers from 1 to 5 and outputs the time it took to execute. In this case, it took 0.15 seconds.

      Now, rerun your program:

import time start = time.time() for i in range(1, 6): print(i) end = time.time() print(end – start) >> 1 >> 2 >> 3 >> 4 >> 5 >> 0.14856505393981934

      The second time you run your program, you should see a different run time. If you rerun your program, you will see yet another run time. The algorithm's run time keeps changing because the available processing power your computer has when it runs your program varies and in turn affects the program's run time.

      Further, this algorithm's run time would be different on another computer. If you run it on a computer with less processing power, it would be slower, whereas it would be faster on a more powerful computer. Furthermore, this program's run time is affected by the programming language you wrote it in. For example, the run time would be faster if you run this same program in C because C can be faster than Python.

      Because an algorithm's run time is affected by so many different variables, such as your computer's processing power and the programming language, run time is not an effective way to compare two algorithms. Instead, computer scientists compare algorithms by looking at the number of steps they require. You can input the number of steps involved in an algorithm into a formula that can compare two or more algorithms without considering the programming language or computer. Let's take a look at an example. Here is your program from earlier that counts from 1 to 5:

      for i in range(1, 6): print(i)

      Your program takes five steps to complete (it goes through a loop five times and prints i each time). You can express the number of steps your algorithm requires with this equation:

      f(n) = 5

      If you make your program more complicated, your equation will change. For example, you may want to keep track of the sum of all the numbers you are printing:

      count = 0 for i in range(1, 6): print(i) count += i

Now, your algorithm takes 11 steps to complete. First, it assigns the variable count to zero. Then, it prints five numbers and increments five times (1 + 5 + 5 = 11).

      This is the new equation for your algorithm:

      f(n) = 11

      What happens if you change the 6 in your code to a variable?

      count = 0 for i in range(1, n): print(i) count += i

      Your equation changes to this:

      f(n) = 1 + 2n

      Now the number of steps your algorithm takes depends on whatever the value of n is. The 1 in the equation represents the first step: count = 0 . Then, there are two times n steps after that. For example, if n is