Algorithms

Recipes for Success

While computer science encompasses a lot more than just writing code, the process of constructing and expressing a detailed sequence of well-specified operations is a key component of harnessing the raw, computing power of our digital world.

As problem solvers, computer scientists and programmers must be able to develop careful and precise algorithmic solutions to whatever problem they are faced with and then communicate those solutions to other individuals and/or machines with clarity and 100% assurance that the instructions not only solve the problem, but that they do so efficiently.

Just like with a cook following a recipe in a cookbook, an algorithm is intended to spell out the step-by-step process for turning an available set of raw data (i.e., the ingredients) into a working solution (i.e., the finished dish). Each instruction represents one incremental step in that transformation and the collective total of all instructions are carefully orchestrated and arranged to perform a very specific, and oftentimes complex, task.

Why Study Algorithms?

At its core, an algorithm is really just a generalized, conceptual solution to a problem that can later be implemented in some real-world form like a computer program. Therefore, it might seem obvious that anyone wanting to be a programmer would need to be proficient at designing and working with algorithms.

But even non-programmers who might never write a program in their life can benefit from the ability to think computationally. Algorithms, with their logical and structured order, enable individuals to more effectively organize their thoughts and manage the complexity of modern life in this digital age.

In fact, much of this course centers on the task of helping you develop the skills to analyze a task at hand, identify what the real problem might be, recognize what you have to work with, and design an effective and efficient solution.

To help get you started, we’ll examine a number of well-known solutions to common, data-oriented problems that computer scientists regularly have to deal with, such as searching and sorting algorithms. While each of the examples we’ll look at are well-known solutions, they also provide an excellent look into the processes and techniques that are used in designing such solutions—techniques that you will learn to master and use in designing your own algorithms.

How Algorithms Work

As we’ve seen previously, most algorithms are composed of a combination of sequencing, selection, and iteration. Computer scientists use these familiar patterns to control the flow of execution that a computer takes through the instructions to ensure that all of the right steps are performed in just the right way and in just the right order.

A well-written algorithm includes all of the relevant information needed to properly implement (i.e., turn ideas into code) and execute (i.e., turn code into actions) a given solution. As such, it is critical that the algorithm be communicated in some form that ensures that the individual steps of the algorithm are perfectly understood and executed exactly the way they were intended.

For example, consider the following simple algorithm:

pants, shoe, shoe, shirt 

Compare that with a slightly revised version of that same algorithm:

1) put on pants
2) put on left shoe
3) put on right shoe
4) put on shirt

Both algorithms contain much the same information, but the second version is much more clearly expressed as a sequence of understandable instructions than the first version. Let’s examine a few of the features that the second version has that make it more useful as an algorithm than the first version.

1) Format: The first version merely lists four words in succession, but doesn’t make clear that this is an algorithm consisting of four discrete steps that must be performed. In the second version, each individual step is written on its own line, helping to make it visually clear each step is separate and unique from the other steps.

2) Imperative statements: Each instruction in the second version is written as a command with a verb phrase that clearly denotes which operation needs to be performed (in this case, “put on"). The first version lacks these verbs and leaves it unclear what is to be done with these pants, shoes, and shirt. Put them on? Take them off? Wash them? Buy them? Sell them? Who knows? The algorithm doesn’t say.

3) Descriptive qualifiers: The first version only lists two shoes, but does not make any distinction between the left shoe and the right shoe. Maybe it doesn’t matter whether you interpret the instructions as “left shoe, right shoe” or “right shoe, left shoe.” But it probably does matter if you interpret it as “left shoe, left shoe.” However, the second version of the algorithm eliminates this possible confusion by explicitly stating which shoe should be put on at each step in the process.

It is important to understand that every step of an algorithm is critically important and that they must be executed exactly as intended. If a step is unimportant, it would just be left out of the algorithm in the first place. The fact that it’s there means it needs to be there. And it needs to be executed exactly as it was intended. If, for example, an algorithm for getting from Point A to Point Z says to turn left at Point F and you decide to turn right instead, it is highly unlikely that the remaining instructions will get you to your intended destination because you’ve deviated from the intended plan laid out by the algorithm.

In all of these cases, it’s important that whoever (or whatever, in the case of computers) reads an algorithm be able to understand with 100% certainty exactly what was intended by a given algorithm.

Fortunately, algorithms can be expressed in many different visual and/or textual formats, including flow diagrams, pseudocode, mathematical notation, programming languages, etc. Each of these formats dictates its own specific style and syntactic structure that is designed to ensure that any algorithm can be expressed in an understandable and clearly unambiguous way. Throughout this course, we’ll examine a number of these formats for writing algorithms that are clear and readable.