\font\largerbold = cmbx10 scaled \magstep1
\font\largerrm =cmr10 scaled \magstep1
\nopagenumbers
\font\sc=cmcsc10.tfm
\magnification=\magstep1
\rightline{\sevenrm February 8, 2000}
\centerline{\largerbold What's an alligator? \hskip-.87in ////////\  algorithm?}
\bigskip
%\bigskip
\def\e{$\ldots$\ }
\smallskip
A precise definition of the term {\bf algorithm} is difficult, which
is quite interesting since it is a central word in late $20^{\rm th}$
century mathematics and computer science. It is as vital and important
to such study as the {\bf sonnet} is to the history and practice of
poetry.

Here's some information about {\bf algorithms} from volume 1 of {\sl
The Art of Computer Programming} by Donald Knuth (published by Addison
Wesley). This is a foundational multi-volume work. I give some
quotes from the very beginning of it.

\medskip

\noindent From page 1:
\smallskip
{\narrower %\indent 
The word ``algorithm'' itself is quite interesting; at
first glance it may look at though someone intended to write
``logarithm'' but jumbled up the first four letters. \e the true
origin of the word \e comes from the name of a famous Persian textbook
author, Abu Ja`far Mohammed ibn M\^us\^a al-Khow\^arism\^\i\ ({\it c.}\/
825) -- literally, ``father of Ja`far, Mohammed, son of Moses,
native of Khow\^arizm.'' Khow\^arizm is today the small Soviet city of
Khiva. Al-Khow\^arizm\^\i\ wrote the celebrated book {\it Kitab al jabr
w'al-muqabala} (``Rules of restoration and reduction''); another
word, ``algebra'', stems from the title of his book, although the book
wasn't really very algebraic.

}

\medskip
\noindent From pages 4, 5, and 6:
\smallskip

{\narrower %\indent 
The modern meaning for algorithm is quite similar to that
of {\it recipe, process, method, technique, procedure, routine,}\/
except that the word ``algorithm'' connotes something just a little
different. Besides merely being a finite set of rules which gives a
sequence of operations for solving a specific type of problem, an
algorithm has five important features:
\smallskip
\noindent {\bf 1) Finiteness.} An algorithm must always terminate
after a finite number of steps. \e
\smallskip
\noindent {\bf 2) Definiteness.} Each step of an algorithm must be
precisely defined; the actions to be carried out must be rigorously
and unambiguously specified for each case. \e
\smallskip
\noindent {\bf 3) Input.} An algorithm has zero or more inputs, i.e.,
quantities which are given to it initially before the algorithm
begins. These inputs are taken from specified sets of objects. \e
\smallskip
\noindent {\bf 4) Output.} An algorithm has one or more outputs, i.e.,
quantities which have a specified relation to the inputs. \e  
\smallskip
\noindent {\bf 5) Effectiveness.} An algorithm is also generally
expected to be {\it effective}. This means that all of the operations
to be performed in the algorithm must be sufficiently basic that they
can in principle be done exactly and in a finite length of time \e


}
\medskip
\noindent 
Knuth continues on the same page to contrast his definition of
algorithm with what could be found in a cookbook:

\smallskip

{\narrower Let us try to compare the concept of an algorithm with that of a
cookbook recipe: A recipe presumably has the qualities of
finiteness (although it is said that a watched pot never boils), input
(eggs, flour, etc.) and output (TV dinner, etc.) but notoriously lacks
definiteness. There are frequently cases in which the definiteness is
missing, e.g., ``Add a dash of salt.'' A ``dash'' is defined as ``less
than $1\over 8$ teaspoon''; salt is perhaps well enough defined; but
where should the salt be added (on top, side, etc.)? \e \par }
\medskip
\noindent 
He concludes his comparison by writing:

\smallskip 
{\narrower \e a computer
programmer can learn much by studying a good recipe book.

}
\medskip

\noindent I sadly report to you that I personally haven't found
many good cookbooks. That might, of course, have some connection with
my facility as a cook!

\bigskip

%\vfil
%\rightline{\bf Over}
%\eject
%\medskip
\centerline{\largerbold Homework}

\bigskip
{\narrower\narrower\noindent
This assignment is due on Wednesday, February 16. Students
may work together in groups of at most 3 people and hand in a joint
answer. \par}

\medskip
Here are the input and output of two algorithms:

\bigskip
\noindent {\bf Cubing} The input is $X$ and the output is $X^3$.
\smallskip

\noindent  {\sc Example} If the input is $4$, then the output is 64. 

\medskip

\noindent {\bf Cube inquiry} The input is $X$ and the output is {\bf
Yes} if $X$ is the cube of an integer and {\bf No} if $X$ is not the
cube of an integer.

\smallskip 

{\noindent {\sc Examples} If the input is 27, the output is
``Yes''; if the input is 23, the output is ``No''.

}
\bigskip

\leftline{\bf The homework problems}

\medskip

\narrower

\noindent 1.~Use only what we've done in class to estimate the number
of elementary arithmetic operations that some implementation of each
algorithm will take. {\it You}\/ describe the implementation --
\underbar{any} implementation will do. Try to be precise, though, with
your descriptions and your assertions about the number of operations
needed: the number of operations \underbar{will} depend on the
``size'' (the number of digits) of the input (call it $S$), and may
also depend on the input itself (call it $X$). Briefly explain in
standard English sentences why your answer is reasonable and correct.

\medskip

\noindent 2.~Suppose that it takes \underbar{1 second} to do {\bf
Cubing} for a 100 digit number and \underbar{1 minute} to do {\bf Cube
inquiry} for a 100 digit number, then (using your analysis)
approximate the amount of time it will take to do each of these
algorithms for a 200 digit number.

\vfil\eject\end

