5. Algorithms ( Terminal Session on this Machine )

5.1 Introduction

An algorithm is a sequence of steps or procedure which solves a given problem in a finite amount of time.

Algorithms usually have one or more inputs which are the objects used by the algorithm and have outputs which are the results produced by the algorithm.

The steps of an algorithm must be given in a manner so as to be understandable and unambiguous to the person or mechanism which performs the algorithm.

It must be possible to perform the steps of an algorithm in a finite amount of time.

For example, a step in an algorithm which says "add up all of the integers" cannot be done in a finite amount of time. Or the step which says "compose a sonata" or "write a poem" is not precise enough to be performed by most persons or perhaps any machine.

5.2 Notation for Algorithms

Algorithms are problem solving processes. They must be expressed in some language (such as natural language) or notation (such as mathematical notation or a programming language) so that they may be comunicated to a person or a machine.

It is sometimes difficult to separate the pure idea of an algorithm from its expression in some language or notation. The idea for an algorithm exists independently from its expression in some language or notation. We don't fully understand how humans get some of their ideas for algorithms, however we do know that our algorithm development skills and abilities are influenced by the languages we know and the notational skills we have, as well as our ability to deal with complexity and abstractions.

When we describe an algorithm in some language (such as a programming language or natural language), we may not capture all aspects of that problem solving procedure. The language or notation we use may limit our description in some manner.

Programs are expressions of algorithms in some notation (programming language) which is suitable for interpretation by a machine. A computer is a machine which interprets a programming language. We will use the Scheme programming notation to express algorithms A Scheme program consists of one or more Scheme expressions. A Scheme system usually operates using a person - machine dialog, that is, the system waits for an expression (program) to be typed. Once an expression has been entered, the system evaluates that expression and prints its result and then waits for the next expression, etc. We call this the read-eval-print loop of the Scheme system.

You may wish to review the discussion of the Scheme notation which appears in Chapter 1 in preparation for the examples which follow.

One important activity for computer scientists is the analysis of algorithms. We wish to estimate or measure the amount of "work" done when a computer interprets a program. Since a program is an expression of an algorithm we often make an attempt, by analyzing the algorithm, to predict how much work will be done. There are a number of ways to define what we mean by the "work" done by a computer as it interprets a program. First, we may be interested in the execution time of the program. This is often proportional to the number of operations performed. A second measure of "work" might be the number of memory cells used by the program as it executes. Often there is a relationship between the execution time and memory spaced used by a program. One rule of thumb is that the more space you give an algorithm, the faster it will run, but as with most rules of thumb there are many exceptions to such rules. Most algorithms must be analyzed independently for both space and time to completely determine the relationship. Finally, there are other measures of work done, but our analyses will focus mainly on time and space.

The following simple algorithms provide practice in counting numbers of operations performed and numbers of memory cells used.

5.3 Some Simple Algorithms

We next consider some examples of Scheme programs which implement algorithms for adding the number one n times, adding the first n integers, computing the product of the first n integers and for computing the n th term of the Fibonacci sequence.

5.3.1 sum-ones

(define sum-ones
  (lambda (n)
    (if (= n 0)
      0
      (+ 1 (sum-ones (- n 1))))))
      
(sum-ones 10) ==> 10

We can trace the interpretation of this algorithm to help us understand how it works.

(trace sum-ones) ==> <#unspecified>
(sum-ones 10)
Entry (sum-ones 10)
|Entry (sum-ones 9)
| Entry (sum-ones 8)
|  Entry (sum-ones 7)
|  |Entry (sum-ones 6)
|  | Entry (sum-ones 5)
|  |  Entry (sum-ones 4)
|  |  |Entry (sum-ones 3)
|  |  | Entry (sum-ones 2)
|  |  |  Entry (sum-ones 1)
|  |  |  |Entry (sum-ones 0)
|  |  |  |==> 0
|  |  |  ==> 1
|  |  | ==> 2
|  |  |==> 3
|  |  ==> 4
|  | ==> 5
|  |==> 6
|  ==> 7
| ==> 8
|==> 9
==> 10
10

When we analyze the behavior of this function we notice that when n is greater than 0, the function is stopped with a pending operation of adding 1 to the result of starting the function again with an input of n - 1, and so forth until an input of 0 is obtained. At this point an answer of 0 is returned. Then, the most recently suspended instance of sum-ones is restarted. The pending execution of adding 1 is continued producing a result of 1. Next, the second most recently suspended instance of sum-ones is restarted. Its pending execution of adding 1 is continued producing a result of 2. This process continues, eventually producing a result of 10. We call the pending operation of adding 1 after computing (sum-ones (- n 1)), the continuation of sum-ones after finishing (sum-ones (- n 1)).

Exercise: Predict what happens when the computer attempts to evaluate (sum-ones -3).

5.3.2 Algorithms and Their Processes

The idea of a continuation, introduced in section 5.3.1, needs to be formalized into a more precise definition. Suppose f is a compound expression and e is a sub-expression of f. The continuation of e in f is that function of a single argument x, (lambda (x) ...) which contains the execution in f which remains to be done after evaluating the sub-expression e. This means that the value of the entire expression f may be obtained by evaluating ((lambda (x) ...) e).

5.3.2.1 Example

Suppose f is the expression (* 2 (+ 3 4)) and e is the subexpression (+ 3 4). Then the continuation of e in f is:

(lambda (x) (* 2 x))

and the entire expression may be written as:

((lambda (x) (* 2 x)) (+ 3 4))

5.3.2.2 Example

The continuation of the recursive call to sum-ones in sum-ones is:

(lambda (x) (+ 1 x))

An algorithm which refers to itself in its definition is said to be recursive. sum-ones is recursive. When we analyze the trace of the execution of sum-ones, we notice that the Scheme system must keep track of 10 different continuations. The process resulting from executing sum-ones on a computer is said to be recursive since each continuation contains an operation of adding 1.

Notice that we are discussing two different aspects of an algorithm; its expression in a programming notation (its definition) and the resulting process when intrepreted (its execution). sum-ones has a recursive definition and produces a recursive process when interpreted.

Next consider a second algorithm which sums 1, n times.

5.3.3 sum-ones1

(define sum-ones1
  (lambda (n)
    (sum-ones-iter n 0 1)))
    
(define sum-ones-iter
  (lambda (n acc i)
    (if (> i n)
      acc
      (sum-ones-iter n (+ acc 1) (+ i 1)))))

This algorithm is decomposed into two parts. The first, sum-ones1, simply refers to the second after providing some necessary setup.

(sum-ones1 10) ==> 10
(trace sum-ones-iter) ==> <#unspecified>
(sum-ones1 10)
Entry (sum-ones-iter 10 0 1)
|Entry (sum-ones-iter 10 1 2)
| Entry (sum-ones-iter 10 2 3)
|  Entry (sum-ones-iter 10 3 4)
|  |Entry (sum-ones-iter 10 4 5)
|  | Entry (sum-ones-iter 10 5 6)
|  |  Entry (sum-ones-iter 10 6 7)
|  |  |Entry (sum-ones-iter 10 7 8)
|  |  | Entry (sum-ones-iter 10 8 9)
|  |  |  Entry (sum-ones-iter 10 9 10)
|  |  |  |Entry (sum-ones-iter 10 10 11)
|  |  |  |==> 10
|  |  |  ==> 10
|  |  | ==> 10
|  |  |==> 10
|  |  ==> 10
|  | ==> 10
|  |==> 10
|  ==> 10
| ==> 10
|==> 10
==> 10
10

To analyze the behavior of sum-ones1 we first note that the continuation of the recursive call to sum-ones-iter can be written as:

(lambda (x) x)

When the continuation of each recursive call in a definition has no pending operations, i.e., the continuation is the identity function, that definition is said to betail recursive. All standard Scheme programming systems are required to recognize tail recursive functions and re-write them in a more efficient, optimized, manner replacing the recursion with iterative loop. That this is possible to do is partially evident in the fact that the trace of the above function always returns the same value of 10 from each of the above calls. It should also be evident in the above example that there is no need for the Scheme system to store multiple values for acc since the answer may be accumulated using a single memory cell each use of sum-ones-iter. Similarly, the value of n is always the same for each use of sum-ones-iter and the value of the counter, i, may be replaced by its new value, i+1, each time sum-ones-iter is used. Since there is no need to have different instances of the symbols n, acc and i for each use of sum-ones-iter, this program may be re-written in an equivalent form by having the processor repeatedly perform the steps inside sum-ones-iter rather than using recursion. We call each repetition an iteration.

The process which results from the interpretation of a tail recursive definition is said to be iterative.

5.3.4 sum

This example is a recursive function to sum the integers 1 to n. This example is very similar to sum-ones. Rather than adding 1 in each continuation, sum adds n in its continuation. Otherwise the analysis is similar.

(define sum
  (lambda (n)
    (if (= n 0)
      0
      (+ n (sum (- n 1))))))
      
(sum 10) ==> 55
(trace sum) ==> <#unspecified>
(sum 10)
Entry (sum 10)
|Entry (sum 9)
| Entry (sum 8)
|  Entry (sum 7)
|  |Entry (sum 6)
|  | Entry (sum 5)
|  |  Entry (sum 4)
|  |  |Entry (sum 3)
|  |  | Entry (sum 2)
|  |  |  Entry (sum 1)
|  |  |  |Entry (sum 0)
|  |  |  |==> 0
|  |  |  ==> 1
|  |  | ==> 3
|  |  |==> 6
|  |  ==> 10
|  | ==> 15
|  |==> 21
|  ==> 28
| ==> 36
|==> 45
==> 55
55

Notice that sum is a recursive definition. When we write the continuation of the recursive call to sum we have:

(lambda (x) (+ n x))

Notice that each continuation contains the operation of adding n to x and each continuation has a different value binding for n. In the first continuation, the value for n is 10, the second, 9 and so on down the last continuation which has a value of 1 for n. The process which results from execution of this definition is not tail recursive since the continuation is not the identity function.

5.3.5 sum1

This example is an iterative function to sum the integers 1 to n. The analysis of this algorithm is very similar to sum-ones1.

(define sum1
  (lambda (n)
    (sum-iter n 0 1)))
    
(define sum-iter
  (lambda (n acc i)
    (if (> i n)
      acc
      (sum-iter n (+ acc i) (+ i 1)))))
      
(sum1 10) ==> 55
(trace sum-iter) ==> <#unspecified>
(sum1 10)
Entry (sum-iter 10 0 1)
|Entry (sum-iter 10 1 2)
| Entry (sum-iter 10 3 3)
|  Entry (sum-iter 10 6 4)
|  |Entry (sum-iter 10 10 5)
|  | Entry (sum-iter 10 15 6)
|  |  Entry (sum-iter 10 21 7)
|  |  |Entry (sum-iter 10 28 8)
|  |  | Entry (sum-iter 10 36 9)
|  |  |  Entry (sum-iter 10 45 10)
|  |  |  |Entry (sum-iter 10 55 11)
|  |  |  |==> 55
|  |  |  ==> 55
|  |  | ==> 55
|  |  |==> 55
|  |  ==> 55
|  | ==> 55
|  |==> 55
|  ==> 55
| ==> 55
|==> 55
==> 55
55

Notice that sum-iter is tail recursive since the continuation of the recursive call to sum-iter is

(lambda (x) x)

and therefore is optimized to an iterative process.

5.3.6 fact

This example is a recursive definition which multiplies the integers 1 to n.

(define fact
  (lambda (n)
    (if (< n 2)
        1
        (* n (fact (- n 1))))))

(fact 10) ==> 3628800
(trace fact) ==> <#unspecified>
(fact 10)
Entry (fact 10)
|Entry (fact 9)
| Entry (fact 8)
|  Entry (fact 7)
|  |Entry (fact 6)
|  | Entry (fact 5)
|  |  Entry (fact 4)
|  |  |Entry (fact 3)
|  |  | Entry (fact 2)
|  |  |  Entry (fact 1)
|  |  |  ==> 1
|  |  | ==> 2
|  |  |==> 6
|  |  ==> 24
|  | ==> 120
|  |==> 720
|  ==> 5040
| ==> 40320
|==> 362880
==> 3628800
3628800

Notice that fact is a recursive definition which results in a recursive process since the continuation of its recursive call is

(lambda (x) (* n x))

5.3.7 fact1

This example is an iterative definition which multiplies the integers 1 to n

(define fact1
  (lambda (n)
    (fact-iter n 1 1)))
    
(define fact-iter
  (lambda (n acc i)
    (if (> i n)
      acc
      (fact-iter n (* i acc) (+ i 1)))))
      
(fact1 10) ==>3628800
(trace fact-iter) ==> <#unspecified>
(fact1 10)
Entry (fact-iter 10 1 1)
|Entry (fact-iter 10 1 2)
| Entry (fact-iter 10 2 3)
|  Entry (fact-iter 10 6 4)
|  |Entry (fact-iter 10 24 5)
|  | Entry (fact-iter 10 120 6)
|  |  Entry (fact-iter 10 720 7)
|  |  |Entry (fact-iter 10 5040 8)
|  |  | Entry (fact-iter 10 40320 9)
|  |  |  Entry (fact-iter 10 362880 10)
|  |  |  |Entry (fact-iter 10 3628800 11)
|  |  |  |==> 3628800
|  |  |  ==> 3628800
|  |  | ==> 3628800
|  |  |==> 3628800
|  |  ==> 3628800
|  | ==> 3628800
|  |==> 3628800
|  ==> 3628800
| ==> 3628800
|==> 3628800
==> 3628800
3628800

Notice that fact-iter is a tail recursive definition which results in an iterative process since the continuation of its recursive call is the identity function.

5.3.8 fibonacci

This example is a recursive definition which calculates the nth term of a fibonacci sequence, 0 1 1 2 3 5 8 13, ...

(define fibonacci
  (lambda (n)
    (if (< n 2)
      n
      (+
        (fibonacci (- n 1))
        (fibonacci (- n 2))))))
        
(fibonacci 5) ==> 5
(trace fibonacci) ==> <#unspecified>
(fibonacci 5)
Entry (fibonacci 5)
|Entry (fibonacci 4)
| Entry (fibonacci 3)
|  Entry (fibonacci 2)
|  |Entry (fibonacci 1)
|  |==> 1
|  |Entry (fibonacci 0)
|  |==> 0
|  ==> 1
|  Entry (fibonacci 1)
|  ==> 1
| ==> 2
| Entry (fibonacci 2)
|  Entry (fibonacci 1)
|  ==> 1
|  Entry (fibonacci 0)
|  ==> 0
| ==> 1
|==> 3
|Entry (fibonacci 3)
| Entry (fibonacci 2)
|  Entry (fibonacci 1)
|  ==> 1
|  Entry (fibonacci 0)
|  ==> 0
| ==> 1
| Entry (fibonacci 1)
| ==> 1
|==> 2
==> 5
5

The analysis of the fibonacci process is a bit more complex. First, notice that the definition is not tail recursive. The fibonacci definition makes two references to fibonacci and adds these two results together. The continuation of the first recursive call to fibonacci is:

(lambda (x) (+ x (fibonacci (- n 2))))

and the continuation of the second recursive call to fibonacci is:

(lambda (x) (+ (fibonacci (- n 1)) x))

Also notice that the fibonacci process repeatedly re-evaluates smaller fibonacci values which it may have already evaluated earlier.

Consider the task of evaluating (fibonacci 5) . We abbreviate (fibonacci 5) as (f 5) in the following diagram.

When we compute (f 5),

(f 4) is computed 1 time
(f 3) is computed 2 times
(f 2) is computed 3 times
(f 1) is computed 5 times
(f 0) is computed 3 times

It seems reasonable to attempt to quantify this behavior. To do this, define an estimate of the work done in evaluating (fibonacci n) to be the number of times (fibonacci j) is evaluated for each possible j <= n. We will call this function (fib-work n). We have

(fib-work 0) ==> 1
(fib-work 1) ==> 1
(fib-work 2) ==> 3
(fib-work 3) ==> 5
(fib-work 4) ==> 9
(fib-work 5) ==> 15
...

A little observation indicates that

(fib-work n) ==> (+ 1 (fib-work (- n 1)) (fib-work (- n 2)))

which is a kind of Fibonacci series. However, we have the same kind of difficulty evaluating (fib-work n) as we have evaluating (fibonacci n).

5.3.9 fib-work

(define fib-work
  (lambda (n)
    (if (< n 2)
      1
      (+ 1
        (fib-work (- n 1))
        (fib-work (- n 2))))))

(fib-work 5) ==> 15

fib-work tells us that to evaluate (fibonacci 5), 15 uses of the fibonacci function must be made.

5.3.10 An Iterative Fibonacci Function

(define fibonacci1
  (lambda (n) (fib-iter 1 0 n)))

(define fib-iter
  (lambda (a b count)
    (if (= count 0)
      b
      (fib-iter (+ a b) a (- count 1)))))
      
(fibonacci1 5) ==> 5
(trace fib-iter) ==> <#unspecified>
(fibonacci1 5)
Entry (fib-iter 1 0 5)
|Entry (fib-iter 1 1 4)
| Entry (fib-iter 2 1 3)
|  Entry (fib-iter 3 2 2)
|  |Entry (fib-iter 5 3 1)
|  | Entry (fib-iter 8 5 0)
|  | ==> 5
|  |==> 5
|  ==> 5
| ==> 5
|==> 5
==> 5
5

The above trace shows us the terms of the fibonacci sequence being developed in the second input to fib-iter. fib-iter is tail recursive since the continuation of its recursive call may be written as:

(lambda (x) x)

5.3.11 Quantifying an Algorithm

We define a notation which we use to quantify the approximate work done, or execution time or space used by an algorithm.

We say that an algorithm is of order f(n) , written as O(f(n)), if there is some constant k such that the work done (execution time or number of operations or space used, etc.) is not more than k * f(n)

5.3.12 Order Examples

In each of the recursive and iterative functions for sum-ones, sum and fact, if we count the work done as the number of uses of the function, we see that the work done is O(n). That is f(n) = 1 * n = n. Since each of those algorithms results in a recursive process when interpreted by a computer, each is O(n) in space used. The iterative versions of these algorithms is O(n) in time, but O(1) in space used.

In the case of the iterative Fibonacci function, the work done is O(n) also.

The recursive Fibonacci function has a completely different behavior. Although the analysis is beyond the scope of this course, it can be shown (a proof is beyond the scope of these notes) that sequences of the form

xn = A * xn-1 + B * xn-2 + C

can be generated according to the formula:

xn = e * qⁿ + f * rⁿ

for suitably chosen constants e, f, q and r. This means that the recursive Fibonacci function is O(xⁿ) which is also why it is not practical to evaluate (fibonacci n) for n much larger than about 30.

5.3.13 Exercise

Estimate how long it would take a computer to evaluate (fibonacci 100).