Assignment 2: Exploring Algorithms

Due: 10:30 p.m., 27 January 2015

Summary: We consider a variety of issues pertaining to algorithms, including some of the building blocks for algorithms in Scheme.

Purposes: To get you thinking more deeply about algorithms and algorithm design. To help you explore some aspects of Scheme. To encourage you to do work outside of class.

Collaboration: You must do your best to work with assigned partners on this assignment. The partner assignments are available at http://www.cs.grinnell.edu/~rebelsky/Courses/CSC151/2015S/partners/assignment.02.html. You may discuss this assignment with anyone you wish, provided you credit such discussions when you submit the assignment. Note that all partners should contribute to all the problems.

Wrapper (Prologue): Individually read through this assignment and make sure that you understand what is required. Then use the form available at http://bit.ly/151hw2pro to indicate (a) how long you think this assignment will take and (b) what you think will be the most challenging aspect of this assignment.

Wrapper (Epilogue): When you are done with the assignment, fill out the form available at http://bit.ly/151hw2epi to indicate (a) how long the assignment took, (b) what the most challenging part of the assignment was, and (c) something important you learned from doing the assignment. If you find that the assignment took much less or much more time than you expected, also include (d) a note as to what might have led to that difference.

Submitting the main assignment: Email your answer to <grader-151@cs.grinnell.edu>. The title of your email should have the form CSC 151.00 Assignment 2: Exploring Algorithms and should contain your answers to all parts of the assignment in the body of the message.

Warning: So that this assignment is a learning experience for everyone, we may spend class time publicly critiquing your work.

Assignment

Part A: Recipes

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 xⁿ using fewer than ⁿ 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.

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

Important Evaluation Criteria

We will primarily evaluate your work on the care with which you assess the various algorithms and procedures, as well as your creativity in choosing and writing procedures. For part E, we will also consider how carefully you consider the different kinds of input values.