Some notes

Algorithm

The meaning of "procedure" might be clear; that's a method for doing something in terms of individual steps. The usual analogy is a recipe, in cooking. By "effective" we mean that it really tells you how to do something...

Now in computer programming, and in other computer use, the standard of being "effective" is quite strict, for two main reasons:

• unlike with people, you have to be very precise in how you link up new instructions with old instructions. I can say "if you forget your password, go to the CDF office and ask someone there." I haven't told you what to ask them; that you need to talk to someone who actually works there rather than another student also looking for a password reset; or for that matter the proper way to initiate a polite conversation with someone whom you don't know. Obviously you can't just go in and demand "What is my password?" They will want to know your name, you will want to confirm that they are employees there, etc. I say "obviously", but there is in fact a significant body of knowledge underlying this, and you access it all implicitly. With computers, you have to say how to do things, or say clearly upon what prior basis you are building.
• also unlike with people, the computer does not invent. If you ask where the Sid Smith building is and I explain it's two buildings that way and that it's a white building, and really it's three buildings that way but the other buildings are red, you probably won't get lost, or confused, and you may not even notice the fault in the directions. The computer will get completely confused. If you say something meaning "the sum is x - y", when obviously that should have been a "+" because it's a sum, the computer will still subtract, and if it ends up getting a result which causes an error, it will emit an error message, and make no attempt to correct the situation. Even a misspelling which a human might not notice can be enough to prevent the computer from doing what you want it to.

Writing a computer program consists of two very different kinds of activities.
One is the coming up with the underlying algorithms for the various portions of the program.
The other is representing that algorithm as text in the correct form in a computer programming language (formal notation) so as to cause the algorithm to be carried out when the program runs on the computer.

The coming up with the underlying algorithm could be called "inventing an algorithm" or "discovering an algorithm" -- this is a philosophical point which needn't concern us in this course.

More examples of algorithms:

• to log in, type your account name, return, password, return
• to convert Canadian funds to equivalent amounts of American funds, multiply by 0.980584
• to centre a title (like on a typewriter), precede it by the following number of spaces: (then you would give a formula)
• etc.

Note that many algorithms have an idea of input and output. If we're converting Canadian funds to equivalent amounts of American funds, the Canadian dollar amount is input and the American dollar amount is output.

Modern computer systems are what we call "interactive", which basically means that input and output are interspersed. You type one Canadian dollar value, you get its American dollar value, you type another, you get another. Or, you run one application (which you do by providing some input), then the application gives you some output, then you run another application, then it gives you some output. Input and output are usually interspersed in a modern "interactive" computer environment.

Still, this basic analysis of input and output is a good structure for specifying what algorithms are supposed to do.

Definition of "algorithm"

• effective procedure (already discussed)
• (Brookshear) a finite sequence of unambiguous, executable steps which ultimately terminates when followed
  (reasonably comprehensive, reasonably standard)
  • steps
  • executable (part of "effective", as are many of the other parts of this definition)
  • unambiguous ("Mary gave Sally her watch")
  • sequence
  • finite
  • ultimately terminates when followed
    • example where termination is essential for it to be an algorithm: cooking step "beat until smooth"
      • an improvement, guaranteed to terminate, is something like "beat until smooth or until five hours have elapsed". (Something like this is implicit when instructing a person.)
    • example which does not terminate but is still usually considered to be an algorithm: the login / process / logout / repeat sequence exhibited by a CDF computer.

The idea of an algorithmic machine

algorithmic machine
e.g. a clothes washing machine -- explain how it goes through steps, give some algorithm portions.

But the essence of a computer is something more powerful than that. We can see exactly how by examining the terms "hardware", "software", and "data".

Hardware, software, data (intro breakdown)

1. physical stuff ("hardware")
2. programs ("software")
3. data (stuff being operated upon)

Compare with cooking (food preparation):

1. food processor, utensils, oven, ... (like hardware)
2. recipes (like software)
   • Why recipeS, plural?
     • make several things at once (whole meal)
     • make different things different days
     • some recipes use the results of others
3. ingredients (like data)

Note the different nature of the recipe as opposed to the ingredients and the tools.
The recipe is conceptual. If you have the recipe written down, you'd hold up the piece of paper and say this is the recipe. But you would not be entirely correct. If I write it down on a new piece of paper, that is the recipe, too. Or if someone translates it into French: still the same recipe. The recipe is an abstract concept.

Suppose the ingredients include a half a pound of butter.
You are making a cake and you have a half pound of butter, in your hand.
I am also making the same cake, same recipe, and I have a half pound of butter in my hand, in my house, far away from you.
We have different half-pounds of butter.
But even though the recipe I hold is on a different piece of paper than yours, it's the same recipe.
This is a substantive distinction.

recipe: abstract
ingredients: concrete

In computer systems, the stuff being operated upon is abstract, too. This [waving some paper] is the course information sheet, but if I were to go back to my computer and print it again, that would be the course information sheet, too.
And it's not a different course information sheet. It's the same course information sheet.

data: abstract

So it's just the hardware which is "concrete". Another way to say this is the quotation, "Hardware is the part of the computer which can be kicked."

Data includes:

• numbers
• text, such as your essay, the assignment one handout
• software. You'll never see a cooking recipe which says as part of the process to take out your recipe box, select another recipe, and grind it up and mix it in. But recipes and ingredients are of different types, as we discussed earlier, whereas data and software are both abstract. An example of some software which manipulates other software as data is certain kinds of operating system software; to execute a program it has to examine it.
  Another example: using an editor to edit a computer program.
  Also: a compiler...

This is the way that computers are so special.
They are algorithmic machines which can execute algorithms which can modify algorithms which they can execute. It's all the same stuff.
This is known as the "stored program concept", that programs are stored in the same way as data.
Or, I should say, as other data. Programs are data too. Or, "software is data too."