ALGORITHMS AND PROGRAMS

An ALGORITHM is an effective computational procedure.

A PROCEDURE is a finite specification of step-by-step instructions.

A COMPUTATIONAL procedure is one that in principle could be carried
out by a computer. It's result, or output, depends only on the
syntactic form of whatever input is supplied to it, hence its
input-output relation is formal and does not vary from one execution
to another as long as the input is the same. We say it is
deterministic, in that the output is determined by the input.

An EFFECTIVE procedure is one that always terminates after some finite
amount of time, no matter what the input.

A PROGRAM is simply a computational procedure specified in a formal
programming language.

Observations: Not all programs are algorithms: they might not be
effective. For instance, an operating system (ideally) never
terminates. But any program that is guaranteed to always terminate, is
an algorithm.  Conversely, not all algorithms are programs: they might
not be specified in a programming language.

Having all this clarity is nice, but it tells us little about what an
algorithm (or program) actually does.  Roughly speaking, an algorithm
solves a problem; this requires further definitions.



     PROBLEMS and PROBLEM-INSTANCES

A PROBLEM (or problem-class) consists of three things:

1. Specification of an input type, I
2. Specification of an output type, O
3. Specification of a relation R between input and output.

Example: < list-of-integers, integer, least-element > represents
the ``least element'' problem class, where intuitively the problem is
to find the least element of a list of integers. Note that the desired
result, the least element, depends (only) on the input list. And 
< integer, {yes,no}, is-prime > represents the is-prime problem (ie,
given an integer, decide whether or not it is prime).

It is easy to write a program (or algorithm) that finds the least
element of a given list of integers; we call any such algorithm a
SOLUTION of the least-element problem.

In general, an algorithm A ``solves'' problem < I,O,R > if for
every input i of type I, A[i] (the result of applying A to input i)
has relation R to i.

A problem P is SOLVABLE is there exists at least one algorithm that
solves P.

It turns out that some problems are unsolvable. But even among those
that are solvable, some are solvable by ``fast'' algorithms and some
are not.  Just what this might mean, and how we can use such ideas, is
the main topic of this course.

An INSTANCE of a problem P = < I,O,R > is given by specifying a
single input i from I.  Thus < 5, {yes,no}, is-prime > is an
instance of the is-prime problem, and < < 3,2,7 > , integer,
least-element > is an instance of the least-element problem.

It is very important to distinguish a problem-instance from its problem
(class).



   DECISION PROBLEMS

Consider a problem < I,O,R > for which O = {yes,no} and where, for
each i, either ``yes'' or ``no'' but not both, has the relation R to
i. Any such problem is called a DECISION PROBLEM.  Such problems are
an important subclass of problems; we think of a decision problem
intuitively as asking us, for a given input i, to determine (or
decide) whether i is ``yes''-related, or ``no''-related. In other
words, R in effect makes some sort of claim about i that is either
true (yes) or false (no).

Example: < integer, {yes,no}, is-prime > is a decision problem, that
asks, for each integer i, whether i is prime, as we saw earlier.



  INFINITE AND FINITE DECISION PROBLEMS

Some problems have only a finite number of instances (i.e., I is
finite). Such a problem is called a finite problem. Any finite
DECISION problem < I,O,R > is solvable.  For let I = < i_1,i_2,...i_n >,
and let < v_1,v_2,...,v_n > be the corresponding correct truth-values
(or yes-no's) that R specifies.  Then the algorithm A =
{< i_1,v_1 >,< i_2,v_2 >,...,< i_n,v_n >} correctly solves the problem. 
That is, A simply consists of a lookup table of correct answers for each
instance of the problem; think of it as a long case statement.

This may seem like cheating. There seems to be no work, no computing,
no figuring-out of the answers. Or rather, it seems that someone has
to look carefully at R ahead of time, and figure out the answers, and
then code them into A. However, note that for a problem to be solvable,
an algorithm must exist; we do not need to find it ourselves, nor does
it have to be foud at all -- it simply must exist in the mathematical
sense of being possible in principle. And since there are only
finitely many inputs (n of them) and two outputs (yes and no) then
there are only 2^n conceivable lists of pairings between I and O, and
since R determines an answer in O for each i in I, then exacly one of
these lists of pairings gets it right, and that one will be A. We
don't need to find it, it is ``there'' as a possibility in principle.

But if P = < I,O,R > were an infinite decision problem (i.e, if I were
infinite), then there is no automatic guarantee that P is solvable. If
we use the same method we just saw for finite decision problems, we
would get an "algorithm" A with an *infinite* case statement, and this
is not an algorithm at all; so for such problems we must in fact have
a method that does some "computing" of the answer instead.

Some infinite decision problems are solvable, of course. For instance,
the is-prime one above certainly is: it is easy to write an algorithm
to test an input integer for primality. (However, although it is easy
to *write*, all such algorithms that have been discovered tend to
*run* very slowly. This important distinction will come up again.)

(Also, if P has a finite I but is not a decision problem, again it
might be that P is unsolvable, simply because for some instances i,
there might be no output at all that satisfies R).