Class 02: Algorithms: Thinking Formally

Held: Tuesday, 21 January 2003

Summary: We continue our introduction to Computer Science by trying to formally give instructions for an everyday problem.

Due

• Introductory survey.
• Consideration of course web.
• Administrivia survey.

Assignments

• Read SamR's Quick HTML Reference.

Notes:

• You will note that three students are absent today, two of whom I misnamed in class yesterday. Don't worry! They haven't dropped the class. They simply made prior arrangements to do Tuesday's work at a different time.
• I teach three introductory courses in this room each day. Please excuse me if I occasionally get confused as to what I've told you or failed to tell you.
• I've started to prepare my responses to your questions from the introductory survey.
• I was unavailable for office hours today. Sorry.
• Okay, my history sucks. I looked up the etymology of Algorithm and came up with the following:

  The word algorithm is derived from the last name of Abu Ja'far Muhammad ibn-Musa Al-Khowarizmi, a famous Persian mathematician and author of the 8th and ninth centuries. Al-Khowarizmi was a teacher at the Mathematical Institute in Baghdad and the author of the book Kitab al jabr w'al muqabala, which in English means Rules of Restoration and Reduction. It was one of the earliest mathematical textbooks, and its title gave us the world algebra (the Arabic word al jabr means reduction).

  In [C.E.] 825, Al-Khowarizmi wrote another book about the base-10 positional numbering system that had recently been developed in India. In this book, he described formalized, step-by-step procedures for doing arithmetic operations, such as addition,s ubtraction, and multiplication, on numbers represented in this new decimal system. In the twelfth century this book was translated into Latin, introducting the base-10 Hindu-Arabic numbering system to Europe, and Al-Khowarizmi's name became closely associated with these formal numerical techniques. When written in Latin characters rather than Arabic, his last name became rendered as Algorismus, and eventually the formalized procedures that he pioneered and developed became known as algorithms in his honor. (Schneider and Gersting, An Invitation to Computer Science, 2nd Edition, 1998, p. 7).

Overview:

• Introduction; What is CS?
• An algorithm for making sandwiches.
• The parts of an algorithm.

An Everyday Algorithm

• We'll explore the problems of writing clear instructions through a simple exercise.
• Challenge: Write a clear, unambiguous, and detailed set of instructions for making a peanut butter and jelly sandwich.
• Format: Work in groups of about four.
• Each group will write its solution on one of the boards.
• SamR will play the role of the sentient, but malicious and clueless follower of instructions.
• I may give you a chance to rewrite your algorithms after some initial attempts to apply your algorithms.
• We'll conclude with some consideration of common parts of algorithms.

The Parts of an Algorithm

• As you may have noted, there are some common aspects to algorithms. That is, there are techniques that we use in many of the algorithms we write.
• It is worthwhile to think about these algorithm parts because we can rely on them when we write new algorithms.

Variables: Named Values

• As we write algorithms, we like to name things.
• Sometimes we use long names, such as the piece of bread in your left hand.
• Sometimes, we use shorter names, such as bread-left.
• As we start to write more formal algorithms, we will need techniques for noting which names we are using and indicating what they name (and, sometimes, what kind of thing they name).
• We call these named values variables, even though they don't always vary.

Parameters: Named Inputs

• Many algorithms take data as input (and generate other data as output).
• Our PBJ algorithm takes bread, jelly, and such as input.
• A find square root algorithm would take a number as input.
• A look up a telephone number algorithm might take a phone book and a name to lok for as inputs.
• In each case, the algorithm should works on many different inputs.
• The algorithm works as long as the input is reasonable (we can't find the square root of a piece of bread and we can't make a PBJ sandwich with tunafish).
• We call these inputs parameters.

Conditionals: Handling Different Situations

• At times, our algorithms have to account for different conditions, doing different things depending on those conditions.
• In our PBJ algorithm, we might check whether the jar of peanut butter is open or what kind of lid is on the jelly jar. We call such operations conditionals.
• Conditionals typically take either the form
  if some condition holds then do something
• Here's a slightly more complex form
  if some condition holds then do something otherwise do something else
• At times, we need to decide between more than two possibilities. Typically, we organize those as a sequence of tests (called guards) and corresponding things to do.

Repetition

• At times, our algorithms require us to do something again and again.
• In our PBJ algorithm, we may have had to turn the twisty-tie again and again until it was untwisted.
• We call this technique repetition.
• Again, repetition takes many forms.
• We might do work until we've reached a desired state.
• We might continue work as long as we're in some state.
• We might repeat an action a fixed number of times.
• You can probably think of many other forms of repetition.

Subroutines: Named Helper Algorithms

• Many algorithms require common actions for their operation.
• For example, to make N sandwiches, you benefit from knowing how to make one sandwich.
• To make a peanut butter and jelly sandwich, it helps to know how to spread something on bread.
• We can write additional algorithms for these common actions and use them as part of our broader algorithm.
• We can also use them in other algorithms.
• We call these helper algorithms subroutines.