Chapter 12
Designing Algorithms

An algorithm is a set of steps that accomplishes a task, such as the steps involved in synthesizing caffeine. Each function in a program, as well as the program itself, is an algorithm that is written in a programming language like Python. Writing a program directly in Python, without careful planning, can waste hours, days, or even weeks of effort. Instead, programmers often write algorithms in a combination of English and mathematics and then translate it into Python.

In this chapter, you’ll learn an algorithm-writing technique called top-down design. You start by describing your solution in English and then mark the phrases that correspond directly to Python statements. Those that don’t correspond are then rewritten in more detail in English, until everything in your description can be written in Python.

Looking Ahead: Testing Your Algorithms

Top-down design is easy to describe, but doing it requires a little practice. Often, parts of an algorithm written in English will be tricky to translate into Python; in fact, an implementation may look reasonable but will contain bugs. This is common in many fields. In mathematics, for example, the first versions of “proofs” often handle common cases well but fail for odd cases (Proofs and Refutations [Lak76]). Mathematicians deal with this by looking for counterexamples, and programmers (good programmers, at least) deal with it by testing their code as they write it.

In this chapter, we have skipped a discussion of how we tested the algorithms we present. The first versions we wrote had minor bugs in them, and we found them only by doing thorough testing. We will talk more about testing in Chapter 15, ​Testing and Debugging​.