You now have some experience writing an algorithm of your own. As you may have guessed, different algorithms often share some common aspects. These are the fundamental “ingredients”. Those who like to cook know that many cookbooks often spend their introductory chapters going over the finer details of the cuisine’s basic ingredients–one of our favorite cookbooks on Italian cuisine has several pages on olive oil alone.
Just as a skilled chef needs to know their basic ingredients in order to be able to use them creatively and effectively, it is worthwhile for us to consider the parts (or ingredients) of algorithms so we can rely on them when we write new algorithms.
In this section we will detail some of the primary ingredients in algorithms. You may find that as the semester progresses, we add other parts.
Almost every algorithm begins with some assumptions about the values the algorithm will work with (e.g., numbers, text, food) and the operations we already know how to perform on those operations (e.g., add or subtract, identify words, mix). Without the basic building blocks, it’s hard to accomplish anything.
One of the important ways you develop power and fluency in writing algorithms in a programming language is to learn the basic values and operations of the language. We will explore a wide variety of kinds of values this semester, as well as a variety of operations on those different values.
Once we have the inputs to the algorithm and the operations we want to perform, what next? We need to indicate the order in which we perform those operations. For example, we might add three numbers and then divide that sum by three. At times, the order will be given by writing an explicit sequence of operations, one after another. At others, additional rules will determine the sequence (as in the precedence rules for standard mathematics). And, in some cases, the order may not matter all that much.
In writing algorithms, particularly when you express those algorithms in a programming language, it is essential that you understand how to sequence the steps of the algorithm.
As we write algorithms, we like to name things. Sometimes we like to use very descriptive long names, such as “the second vertical fold” or “the marker in your left hand.” Other times we use shorter, more abbreviated names such as “fold-2” or “left-marker.”
As we start to write more formal algorithms, we will need techniques for declaring which names we are using and indicating what thing the name refers to. It is also often useful to note what kind of thing they name.
We call these named values variables, even though they don’t always vary. As long as we choose descriptive names, variables help us avoid ambiguity. Perhaps you encountered instructions on the first day’s lab that had references to “it” in them and were misinterpreted because of the vague referent. Using clear variable names helps improve clarity.
At times, our algorithms have to account for different conditions, doing different things depending on those conditions. In a smiley-face drawing algorithm, we might check what kind of face we want to draw, or whether the marker is open or closed. In a paper-airplane folding algorithm, we might want to check whether the paper is oriented the expected way.
We call such operations conditionals. Conditionals typically take either the form
if some condition holds then do something
or a more general form where an alternative action is specified, as in
if some condition holds then do something otherwise do something else
At times, we need to decide between even more than two possibilities. Typically, we organize those as a sequence of tests (called guards) and the corresponding things to do.
Sometimes our algorithms require us to do something again and again, a technique called repetition. Repetition can take many forms. We might,
In all of these cases, we have the advantage of being able to represent in only a few short statements what could become a rather lengthy sequence of operations to conduct.
Many algorithms require the use of some common or more basic operations and actions. We can typically make use of a collection of commands that are parameterized (i.e., take named inputs) and are referred to by a single name. For instance, given the task of creating a drawing, one might wish to utilize a “draw a circle” subroutine.
It is very useful to write algorithms for such common actions so that we can use them in other algorithms. Such helper algorithms are called subroutines. In this course, we will also often call them procedures or even functions.
This strategy of decomposing a task into manageable units is one of the most important techniques in algorithmic problem solving. It is much easier both to write and debug algorithms that solve small, specialized problems, and then use these subroutines to accomplish bigger, more complicated tasks. This helps the problem solver (and the reader!) to think about and understand the “big picture” as well as iteratively refine coarse steps of an algorithm into more detail.
If all the program does is compute some results given data it already has, and does not share the results, computation is pointless. Hence, programs will often take input from elsewhere (the terminal, a file, a network connection) and provide output somewhere else (the screen, a file, a network connection).
We will generally work in a model in which we can explicitly provide the input to our algorithms and will see the results on the screen, but it is worth remembering that there are other approaches.
On the first day of class, you wrote an algorithm for a task. Provide examples from your algorithm of each component.
GrinCo has decided to add a robotic receptionist to each building. That robot is supposed to smile (or grin) whenever someone is in its vicinity. To what extent is a conditional, subroutine, and/or repetition necessary for this task?