Human beings write algorithms for a wide variety of activities;
not just numeric computation. One of the most common kinds of
algorithms we write are recipes.
a. Find an interesting recipe. Copy and cite that recipe.
b. For that recipe, list the parameters and variables.
c. For that recipe, indicate any cases in which repetition and
conditionals are used. (If neither repetition nor conditionals are
used, indicate how the recipe might be extended to include
repetition or conditionals.)
d. For that recipe, note what basic operations or subroutines the
recipe author assumes that the reader already knows how to do.
e. Most recipes are written for “average” cooks. Either
rewrite the algorithm for a beginning cook or write a detailed set of
instructions for one of the assumed subroutines of the algorithm.
f. Most recipes are written for “average” cooks. Rewrite
the algorithm for an expert cook.
Part B: Numeric Algorithms
Over the years, mathematicians have developed a large number of
algorithms for a wide variety of numeric computations. You probably
know algorithms for computing one side of a right triangle or for
finding the roots of a quadratic polynomial.
a. Find a non-trivial algorithm for some other interesting
computation, preferably an algorithm you have not seen before.
You might look for algorithms for computing square roots,
for computing xn using fewer than
n multiplications, for computing the
greatest-common-divisor of two integers, for generating a sequence of
“random” (or at least unpredictable) numbers, or anything
else you deem interesting and non-trivial. Copy and cite that algorithm.
b. For that algorithm, list the parameters and variables.
c. For that algorithm, indicate any cases in which repetition and
conditionals are used. (If neither repetition nor conditionals are
used, indicate how the algorithm might be extended to include
repetition or conditionals.)
d. For that algorithm, note what basic operations or subroutines the
algorithm author assumes that the reader already knows how to do.
e. Show the steps involved in running the algorithm by hand on at
least two sets of inputs. For example, if you use the square root
algorithm, you might compute the square root of 2 and the square
root of 100.
Part C: An Additional Algorithm
a. Find another algorithm that is neither a recipe nor a numeric
computation. Copy and cite it.
b. For that algorithm, list the parameters and variables.
c. For that algorithm, indicate any cases in which repetition and
conditionals are used. (If neither repetition nor conditionals are
used, indicate how the algorithm might be extended to include
repetition or conditionals.)
d. For that algorithm, note what basic operations or subroutines the
author assumes that the reader already knows how to do.
Part D: Your Own Algorithm
Pick a non-trivial task you would want to teach a new member of the
Grinnell community how to accomplish. (Please choose a task that is
in good taste.)
a. Write the algorithm for accomplishing the task. The algorithm
must include both repetition and conditionals. If the task you've
chosen does not lend itself to repetition and conditionals, please
pick another task.
b. For your algorithm, list the parameters and variables.
c. For your algorithm, note what basic operations or subroutines the
author assumes that the reader already knows how to do.
Part E: Learning About Scheme's Numeric Functions
Scheme provides a number of numeric procedures that can produce
integer results. In the next lab, you will explore expt,
abs, +, -, *,
and /.
Here are some others. For each, try to learn (by experimentation,
by discussing results with other students, and, eventually, by reading
documentation) how many parameters each procedure can take and what
the procedure does. Make sure to try a variety of input
values for each procedure, including positive and negative; integer,
real, and complex; and exact (no decimal point: whole numbers and
fractions) and inexact (with a decimal point).
- quotient
- remainder
- modulo
- max
- min
- numerator
- denominator
- gcd
- lcm
After you've figured out each procedure, write a short explanation
of what the procedure does, one suitable for your peers in the class
who may not have encountered the procedure before. In writing your
explanation, you should include illustative samples of the use of each
procedure. You should describe what it does with different kinds of
inputs (e.g., if you give it an exact input, do you get an exact output).
You may also find it helpful to include examples of failure.
For example,
The abs function computes the absolute value
of a real number. If given zero or a positive number as input,
it returns the same number. If given a negative number as input,
it returns the opposite of the number.
> (abs 5)
5
> (abs -2.3)
2.3
> (abs 1/3)
1/3
> (abs -2/5)
2/5
The return value is the same type as the input. If
abs is given an integer as input, it returns
an integer. If abs is given an exact input,
it returns an exact output. If abs is given
an inexact input, it returns an inexact output.
The abs function expects an integer or real number
as an input. If given a complex number or non-number as input, it
reports an error. If given zero inputs, or more than one input, it
reports an error.
> (abs 3+4i)
abs: contract violation. expected: real? given: 3+4i
> (abs 'one)
abs: contract violation. expected: real? given: 'one
> (abs abs)
abs: contract violation. expected: real? given: #<procedure:abs>
> (abs)
abs: arity mismatch;
the expected number of arguments does not match the given number
expected: 1
given: 0
> (abs 2 3 4)
abs: arity mismatch;
the expected number of arguments does not match the given number
expected: 1
given: 3
This work is licensed under a
Creative Commons Attribution-NonCommercial 3.0 Unported License
.