5. Algorithms

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 (interprets) 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 (usually a programming language) which is suitable for interpretation by a machine. A computer is a machine which interprets a programming language. We will use the J programming notation to express algorithms A J program consists of one or more J expressions (sentences). A J system usually operates using a person - machine dialog, that is, the system waits for an expression or sentence (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 J system.

You may wish to review the discussion of the J 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 space 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


sum_ones =: monad define
if. y. = 0
  do. 0
  else. 1 + sum_ones y. - 1
end.
)

sum_ones 10 ==> 10

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


traced_sum_ones =: monad define
entering y.
if. y. = 0
  do. leaving 0
  else. leaving 1 + traced_sum_ones y. - 1
end.
)

   traced_sum_ones 10
Entering, input = 10
Entering, input = 9
Entering, input = 8
Entering, input = 7
Entering, input = 6
Entering, input = 5
Entering, input = 4
Entering, input = 3
Entering, input = 2
Entering, input = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Leaving, result = 2
Leaving, result = 3
Leaving, result = 4
Leaving, result = 5
Leaving, result = 6
Leaving, result = 7
Leaving, result = 8
Leaving, result = 9
Leaving, result = 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 y. - 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 y. - 1, the continuation of sum_ones after finishing sum_ones y. - 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 monad having input y., monad def '... y. ...' 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:


monad def '... y. ...' 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:


monad def '2 * y.'

and the entire expression may be written as:


monad def '2 * y.' 3 + 4

5.3.2.2 Example

The continuation of the recursive call to sum_ones in sum_ones is:


monad def '1 + y.'

An algorithm which refers to itself in its definition is said to be recursive. sum_ones is recursive. When we analyze the execution of traced_sum_ones, we notice that the J 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


sum_ones1 =: monad def 'sum_ones_iter y. , 0 1'

sum_ones_iter =: monad define
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. acc
  else. sum_ones_iter n , (acc + 1) , i + 1
end.
)

This algorithm is decomposed into two parts. The first, sum_ones1, simply refers to the second providing an appropriate input. Following is the traced version of sum_ones1.


traced_sum_ones1 =: monad def 'traced_sum_ones_iter y. , 0 1'

traced_sum_ones_iter =: monad define
entering y.
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. leaving acc
  else. leaving traced_sum_ones_iter n , (acc + 1) , i + 1
end.
)
   traced_sum_ones1 10
Entering, input = 10 0 1
Entering, input = 10 1 2
Entering, input = 10 2 3
Entering, input = 10 3 4
Entering, input = 10 4 5
Entering, input = 10 5 6
Entering, input = 10 6 7
Entering, input = 10 7 8
Entering, input = 10 8 9
Entering, input = 10 9 10
Entering, input = 10 10 11
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 10
Leaving, result = 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:


monad def 'y.'

This function simply returns a value of its input, y., . We call this verb the identity verb. 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. A J programming system could 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 J 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.


sum =: monad define
if. y. = 0
  do. 0
  else. y. + sum y. - 1
end.
)

sum 10 ==> 55

traced_sum =: monad define
entering y.
if. y. = 0
  do. leaving 0
  else. leaving y. + traced_sum y. - 1
end.
)

   traced_sum 10
Entering, input = 10
Entering, input = 9
Entering, input = 8
Entering, input = 7
Entering, input = 6
Entering, input = 5
Entering, input = 4
Entering, input = 3
Entering, input = 2
Entering, input = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Leaving, result = 3
Leaving, result = 6
Leaving, result = 10
Leaving, result = 15
Leaving, result = 21
Leaving, result = 28
Leaving, result = 36
Leaving, result = 45
Leaving, result = 55
55

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


monad def 'n + y.'

Notice that each continuation contains the operation of adding n to y. 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.


sum1 =: monad def 'sum_iter y. , 0 1'

sum_iter =: monad define
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. acc
  else. sum_iter n , (acc + i) , i + 1
end.
)

sum1 10 ==> 55

The traced version of sum1 works as follows:


traced_sum1 =: monad def 'traced_sum_iter y. , 0 1'

traced_sum_iter =: monad define
entering y.
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. leaving acc
  else. leaving traced_sum_iter n , (acc + i) , i + 1
end.
)

   traced_sum1 10
Entering, input = 10 0 1
Entering, input = 10 1 2
Entering, input = 10 3 3
Entering, input = 10 6 4
Entering, input = 10 10 5
Entering, input = 10 15 6
Entering, input = 10 21 7
Entering, input = 10 28 8
Entering, input = 10 36 9
Entering, input = 10 45 10
Entering, input = 10 55 11
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
Leaving, result = 55
55

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


monad def 'y.'

and therefore can be optimized to an iterative process.

5.3.6 fact

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


fact =: monad define
if. y. < 2
  do. 1
  else. y. * fact y. - 1
end.
)

fact 10 ==> 3628800

The traced version of fact works as follows:


traced_fact =: monad define
entering y.
if. y. < 2
  do. leaving 1
  else. leaving y. * traced_fact y. - 1
end.
)

   traced_fact 10
Entering, input = 10
Entering, input = 9
Entering, input = 8
Entering, input = 7
Entering, input = 6
Entering, input = 5
Entering, input = 4
Entering, input = 3
Entering, input = 2
Entering, input = 1
Leaving, result = 1
Leaving, result = 2
Leaving, result = 6
Leaving, result = 24
Leaving, result = 120
Leaving, result = 720
Leaving, result = 5040
Leaving, result = 40320
Leaving, result = 362880
Leaving, result = 3628800
3628800

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


monad def 'n * y.'

5.3.7 fact1

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


fact1 =: monad def 'fact_iter y. , 1 1'

fact_iter =: monad define
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. acc
  else. fact_iter n , (i * acc) , i + 1
end.
)

fact1 10 ==>3628800

The traced version of fact1 works as follows:


traced_fact1 =: monad def 'traced_fact_iter y. , 1 1'

traced_fact_iter =: monad define
entering y.
('n' ; 'acc' ; 'i') =. y.
if. i > n
  do. leaving acc
  else. leaving traced_fact_iter n , (i * acc) , i + 1
end.
)

   traced_fact1 10
Entering, input = 10 1 1
Entering, input = 10 1 2
Entering, input = 10 2 3
Entering, input = 10 6 4
Entering, input = 10 24 5
Entering, input = 10 120 6
Entering, input = 10 720 7
Entering, input = 10 5040 8
Entering, input = 10 40320 9
Entering, input = 10 362880 10
Entering, input = 10 3628800 11
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 3628800
Leaving, result = 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, ...


fibonacci =: monad define
if. y. < 2
  do. y.
  else. (fibonacci y. - 1) + fibonacci y. - 2
end.
)

fibonacci 5 ==> 5

The traced version of fibonacci works as follows:


traced_fibonacci =: monad define
entering y.
if. y. < 2
  do. leaving y.
  else. leaving (traced_fibonacci y. - 1) + traced_fibonacci y. -2
end.
)

   traced_fibonacci 5
Entering, input = 5
Entering, input = 4
Entering, input = 3
Entering, input = 2
Entering, input = 1
Leaving, result = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Entering, input = 1
Leaving, result = 1
Leaving, result = 2
Entering, input = 2
Entering, input = 1
Leaving, result = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Leaving, result = 3
Entering, input = 3
Entering, input = 2
Entering, input = 1
Leaving, result = 1
Entering, input = 0
Leaving, result = 0
Leaving, result = 1
Entering, input = 1
Leaving, result = 1
Leaving, result = 2
Leaving, result = 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:


monad def 'y. + fibonacci n - 2'

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


monad def '(fibonacci n - 1) + y.'

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


fib_work =: monad define
if. y. < 2
  do. 1
  else. 1 + (fib_work y. - 1) + fib_work y. - 2
end.
)

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


fibonacci1 =: monad def 'fib_iter 1 0 , y.'

fib_iter =: monad define
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. b
  else. fib_iter (a + b) , a , count - 1
end.
)

fibonacci1 5 ==> 5

The traced version of fibonacci1 works as follows:


traced_fibonacci1 =: monad def 'traced_fib_iter 1 0 , y.'

traced_fib_iter =: monad define
entering y.
('a' ; 'b' ; 'count') =. y.
if. count = 0
  do. leaving b
  else. leaving traced_fib_iter (a + b) , a , count - 1
end.
)

   traced_fibonacci1 5
Entering, input = 1 0 5
Entering, input = 1 1 4
Entering, input = 2 1 3
Entering, input = 3 2 2
Entering, input = 5 3 1
Entering, input = 8 5 0
Leaving, result = 5
Leaving, result = 5
Leaving, result = 5
Leaving, result = 5
Leaving, result = 5
Leaving, result = 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:


monad def 'y.'

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

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

can be generated according to the formula:

x_n = 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.