This week’s topic is algorithms. You should complete the Hour of Code before beginning this topic; I will assume you know things like sequence, if/else, repeat-until, and repeat-N-times.
Become able to:
In the Hour of Code, you learned about putting instructions together in these structures: sequence, repeat until, repeat N times, if, and if/else. You did this in a very concrete, graphical environment where your program controlled an angry bird or a zombie. Your wrote programs, not by typing very much, but by dragging blocks of code around to organize them.
Algorithms are, so to speak, programs for human computers: organized sets of instructions presented in a way that human beings can understand, not in a form that electronic computers can execute. The first “computers” were, in fact, human beings who carried out algorithms with the aid of pencil and paper to perform mathematical calculations. Only in the 20th century did the word “computer” come to refer to an electronic machine.
“An algorithm is a complete, step-by-step procedure for solving a specific problem.” — Berman and Paul, Fundamentals of Sequential and Parallel Algorithms (1997).
“a precise rule (or set of rules) specifying how to solve some problem” — WordNet
“A detailed sequence of actions to perform to accomplish some task.” — The Free On-line Dictionary of Computing
“An algorithm is a precise, systematic method for producing a specified result.”
— Snyder, Fluency with Information Technology
There are numerous variations on this (Algorithm characterizations), i.e., authorities do not precisely agree on the definition of algorithm. But obviously, the key idea is that of a procedure that achieves a result or solves a problem.
Snyder adds that “an algorithm must have five properties:
These properties seem to come from Donald Knuth’s The Art of Computer Programming (1968, 1973).
Let’s consider these.
But input and output (I/O) need not always be data in the form of text. What were the inputs and outputs in the Hour of Code? Let’s think in terms of sensors (inputs) and actions (outputs) the agent could perform. The angry bird could sense if there’s a pig here. The zombie could sense if there’s a path ahead, or to the left or right, or if there’s a sunflower here. What could they do? They could move forward, turn left, turn right.
Occasionally, an algorithm might be for a very specific result and need no input. For example, an algorithm to tell the name of the first U.S. President would always answer “George Washington”; there is no need for any input. But usually algorithms are more general, and require a specific input to get a specific answer or output.
It is hard to imagine an algorithm that produces no output, however: since an algorithm is supposed to solve a problem or achieve a result, it has to produce some output or perform some action; otherwise, we don’t get the result.
Let’s take Knuth’s explanations of these terms, which are clearer than Snyder’s:
Definiteness: “Each step of an algorithm must be precisely defined; the actions to be carried out must be rigorously and unambiguously specified for each case”
We wouldn’t want any ambiguous instructions in an algorithm, or any missing steps.
For example, how do you get to the Post Office? “Go east through the woods until you come to the most beautiful tree. Turn left 90 degrees, and go forward a stone’s throw. If water is flowing from the fountain, then turn right a little and move forward 120 paces.”
Effectiveness: “… all of the operations to be performed in the algorithm must be sufficiently basic that they can in principle be done exactly and in a finite length of time by a man using paper and pencil”
We wouldn’t want our algorithm to require creativity or imagination or consulting an oracle. It should be “mechanically” executable.
How do you find the square root of x? “The square root of x is the number which, multiplied by itself, makes x.” That tells me how to recognize it, not how to find it. That won’t do: it requires creativity.
I don’t care if you remember the terms definiteness and effectiveness, but I would like you to remember that algorithms should be clear and unambiguous, mechanically and uncreatively executable.
Finally, an algorithm must (usually) be finite—both in terms of the number of instructions and the time to execute it. You cannot have an algorithm with infinitely many instructions, because you could never write it. What about an algorithm that repeats a finite list of instructions endlessly?
repeat until pig is here
do
turn leftThat does no good either. We never get to a solution that way. Execution of the algorithm must come to an end.
However, sometimes you want an agent to go on performing for as long as possible—ideally, forever. A clock should keep ticking. A security scanner should keep working. A power plant should keep producing power. A web server should keep serving web pages. An operating system should keep operating the computer. Occasionally we may want to shut down and reboot the operating system, but it should be able to run forever. Whether the instructions for such agents should be called “algorithms”, although not finite algorithms—let’s not get into a quarrel about that, though.
We’ve met functions before in the world of spreadsheets. A function usually has a name and one or more arguments and computes a result.
In the world of algorithms, a function is an “operation that the agent already knows how to perform” (Snyder, p. 301).
Functions of the angry bird in the Hour of Code included:
Functions of the zombie included sensing whether there is a path ahead, to the left, or right, and whether there is sunflower here, as well as the turns to left and right and going forward.
A spreadsheet or a calculator can compute the square root of 10, because it has a square root function. An angry bird or zombie might not be able to do this. It might not have the function to do that; so if you wanted it to compute a square root, you would have to tell it how—you would have to give it an algorithm for that task.
So, in specifying algorithms, we want them to be effective—to use only operations that the agent knows how to perform; but we now see that agents can be equipped with different sets of functions, so what is effective for one agent may not be effective for some other agent.
Sometimes an agent needs to remember things. For example, if your mother sent you on an errand to buy five things from five stores, you’d need to remember the five items you have to buy, and the five stores. You might write this information down on a sheet of paper, or you might keep it in your head.
In computer programming, these memories are called variables. A variable is a named “memory” for storing some information. You can store information in the variable, retrieve it, and update it (store a new value). For example, as you visit the stores and purchase the items, you could scratch them off of your list — whether on paper or mentally. Or if you mom called you on your cell phone and told you to buy a sixth item, you’d add that to the list.
In developing algorithms, sometimes we need to give instructions to store and retrieve information in memories (variables). And when we do so, we need to be very explicit about the usage of these memories, just as every other instruction in an algorithm needs to be explicit. That is, we have to say it instead of leaving it as something to be “read between the lines.”
In each example we need to think about the sensors (input devices), actions (output devices), and memories of the agents, as well as their instructions (what are the “functions” or instructions that can be used, which of them do we use, and how do we put them together).
Problem statement: Design an algorithm for a thermostat to control room temperature. To keep it simple, we will consider only a room that is to be heated, not cooled (i.e., no air conditioning).
Procedure (the algorithm itself):
repeat forever
do
if actual temperature < desired temperature
do
turn heat on
else
turn heat offBut how well would that work?
I think it depends on how fast the thermostat executes its instructions and how precisely it measures temperature. If it’s so fast that it checks the temperature every 3 seconds, then as as soon as the temperature gets to be equal to or greater than desired temperature (for example, desired = 68 degrees and actual = 68.00001), the heat is going to be turned off, and then a few seconds later it will have to turn the heat on again, so it will be continually going on and off, and that would not only be very annoying but maybe wasteful as well.
But if it checks the temperature only every two minutes, then the turning on and off repetitively might not be so bad.
Still—maybe we could improve the algorithm by putting a “tolerance” into it: we’ll let the temperature fall 1/2 degree below the desired temperature before turning the heat on, and wait until it’s 1/2 degree above the desired before turning it off.
repeat forever
do
if actual temperature < desired temperature - 1/2
do
turn heat on
else
if actual temperature > desired temeprature + 1/2
do
turn heat off
else
do nothingSometimes, more than one algorithm is correct, and yet one of the correct algorithms is better than the other.
Notice that I said repeat forever. This is not a finite algorithm. (So some people would say it’s not an algorithm at all, strictly speaking; okay, let them say that.) And repeat forever wasn’t one of the structures we learned: there were repeat N times and repeat until. Still, repeat forever is equivalent to repeat until False or repeat until 1 + 1 = 3
Problem: Design a control algorithm for an elevator to pick up passengers and deliver them to their destination floors.
Rough statement:
if people want to get on or off here
do let them get on and off
if people want to get on or off above
and we are going up
do go up to next floor
if people want to get on or off below
and we are going down
do go down to next floorThis is not entirely satisfactory, because
Intention is a variable (memory), meaning the direction the elevator plans to move, if it moves.
start on bottom floor, intention = up
repeat forever
do
if a passenger is calling from or going to the current floor
do
ring bell
open door
wait 5 seconds
wait until door is not in use
close door
if (intention = up and a passenger is calling from or going to
any floor above where we are)
do
go up 1 floor
if newly arrived floor = top floor
do
change intention to down
else
if (intention = down and passenger is calling from or going to
any floor below where we are)
do
go down 1 floor
if newly arrived floor = bottom floor
do
change intention to up
else
do nothingNotice the use of indenting to show the structure: Everything controlled by the “repeat forever do” is indented, everything controlled by an “if” or “if/else” is indented further.
In addition to the sensors and actions identified, we used some memories and some functions.
Memories: the elevator had a planned direction, intention
It knew which floor it was on. Is that a sensor, or a memory? If it’s a memory, the elevator must update it by adding 1 when it goes up, and subtracting 1 when it goes down.
Functions:
What do we do about these? Are they built into the elevator hardware? Are they somebody else’s programming task? Are they a programming task for us to do, later? Often we face complex tasks, and the best thing we can do is divide them into parts, and solve one part at a time.
The remaining problems may be used in a discussion or assignment.