CS 4, Summer 2006: Lecture 6: Intro to Algorithms

Overview

Recipes and algorithms
The types of operations used in an algorithm
Remembering things: variables
Combining operations: sequence, conditional, and iteration

Recipes

Computer science is primarily the study of problems that can be solved automatically by some kind of machine. For example:

Finding someone's number in the phone book
Sorting emails by date, sender, subject, etc.
Computing the total amount of time taken by the songs in your music library
Deciding whether or not there is a restaurant at which everyone would like to eat
Determining the shortest route from here to your home

But a computer, by itself, is nothing more than a blind calculating machine -- we have to tell it precisely what to do. In order for a computer to solve a problem automatically, we need to specify a "recipe". What do recipes consist of?

Ingredients: The list of things you need.
Method: A list of steps to be followed, in order.
Results: What you get, how many it serves, etc.

Example: Making a peanut butter and jelly sandwich.

Algorithms

Computer recipes are called algorithms, named after an 8th C. Persian mathematician. As we saw with recipes, we must specify the "ingredients" needed (the input to the algorithm), a clear and unambiguous set of instructions, and what we'll get when we're finished.

An algorithm is an ordered collection of unambiguous and effectively computable operations that, when followed produces an observable result, and completes (halts) in a finite amount of time.

Ordered collection: We can always tell which instruction is to be followed next.
Unambiguous: There is only one possible interpretation of the instruction.
Effectively computable: You can figure out how to do it automatically with a machine.
Observable result: You can tell what has happened, at the end.
Halts in a finite amount of time: It doesn't go on forever without stopping.

Operations

In order to design algorithms to solve specific problems, we need to develop a kind of language we can use to speak precisely about the "unambiguous and effectively computable operations" we will use to accomplish our tasks. This will give us a common understanding of what the computer can and cannot do. Depending on the application, different operations are the "primitives". The most basic ones include:

Add, subtract, multiply, or divide.
Display something for the user to see.
Compare two values, and choose what to do based on the results of the comparison.
Repeat the same sequence of actions again and again.
Halt. Stop computing and return some value.

Variables

As the computer executes an algorithm, it computes various values it needs to remember for later. In order for this to work, a computer has a "memory", where values can be stored away and retrieved later on. When we are writing an algorithm, the values we store in memory are represented by variables. A variable, in the computer sense, is a name that corresponds to some location in memory. For instance, we can use names like "x", "y", "name", "address", etc. as variables.

Sequence

An algorithm is generally specified by listing a sequence of operations. Generally speaking, the computer begins at the first operation, and executes the operations one at a time, in order, until it reaches the end of the sequence.

Here is a simple algorithm to compute the sum of the squares of the integers 1 through 3, that is: 1*1 + 2*2 + 3*3:

1.  Set sum to 0           -- stores the value zero in variable "sum"
2.  Set square to 1 * 1    -- stores the value 1 in variable "square"
3.  Add square to sum      -- adds the value in "square" to "sum"
4.  Set square to 2 * 2    -- stores the value 4 in variable "square"
5.  Add square to sum
6.  Set square to 3 * 3
7.  Add square to sum
8.  Halt and return sum

We can do this by hand, and see that 1*1 + 2*2 + 3*3 = 1 + 4 + 9 = 14. So, let's verify that the algorithm computes this correctly:

After step    Value of "sum"     Value of "square"
1.            0                  ?
2.            0                  1
3.	      1		         1
4.	      1		         4
5.	      5		         4
6.	      5		         9
7.	      14		 9

Step (8) causes the algorithm to halt and return the value of "sum". This value is 14, as we'd expect.

Conditional

Another thing we want an algorithm to be able to do is to choose between different courses of action. For example, suppose you want to design an algorithm that prints out a greeting message based on the date. When the date is something special (e.g., July 4), the greeting message should be different:

to PrintMessage given month, day:
1. If month = 7 and day = 4 then
2.   print "Happy fourth of July!"
3. Else
4.   print "Good afternoon!"

The key here is the ability to "test" certain conditions. Breaking down this algorithm, what it says is:

In order to execute the PrintMessage algorithm, you must provide values for the "month" and "day" variables.
If "month" is equal to 7 (corresponding to July), and "day" is equal to 4 (corresponding to the 4th), then Step (2) should be taken;
Otherwise (it's a different month or a different day), step (2) should be skipped, and Step (4) should be taken instead.

A conditional has this basic structure:

If test then
  consequent
Else
  alternate

The test yields either "true" or "false". If it is "true", then the consequent is executed; otherwise, the alternate is.

Iteration

A computer should also have the ability to repeat the same set of instructions over and over again. Analogy: When you're searching for your keys, you keep looking in places you haven't checked yet, until you either find the keys, or run out of places. In algorithmic terms, that's like saying:

to FindKeys:
1. While (there is another place to search), do
2.   If (your keys are in the next unsearched place) then
3.     Halt and return "true"  -- your keys are found!
4. End
5. Halt and return "false"     -- your keys are lost!

This idea of repeating a sequence of instructions over and over again until some condition is met is very common in algorithms. This kind of repetition is called iteration or "looping", since you are going over a "loop" of instructions over and over.

An iteration has this basic structure:

While test do
  instructions
End of loop.

Let's write an algorithm called SumUp, that when you give it a positive integer "target", computes the sum of all the even positive integers between 1 and target inclusive:

to SumUp given target:
1. Set counter to 1
2. Set sum to 0

3. While (counter ≤ target) do
4.   If (remainder of counter / 2) = 0 then
5.     Add counter to sum.

6.   Add 1 to counter
   End of loop.
7. Halt and return sum.

How could you shorten this algorithm? (Hint: Can you eliminate the "if" instruction?)

Synopsis

Some problems can be solved automatically; you figure out a solution once, and it can be applied mechanically by a machine.

Computer science is especially interested in these sorts of problems, and there turn out to be all kinds of interesting things that happen. We start from a set of "primitive operations" that a computer is capable of, and build algorithms to solve specific problems.

In the next couple of lectures, we'll look at more complex algorithms for some common problems, and later next week, we'll start learning how to actually program the computer to execute some algorithms, using JavaScript.