Assignment 2: Exploring algorithms

Due

by 10:30pm on Tuesday, 30 January 2018.

Summary

For this assignment, you will identify the parts of an algorithm, find some problems with that algorithm, and write an improved version. You will then design some of your own algorithms in Scheme.

Purposes

The purpose of this assignment is for you to practice identifying the parts of algorithms, to get some experience thinking carefully about the edge cases where an algorithm could go wrong, and to get you started thinking in Scheme.

Collaboration

You must work with your assigned partner(s) on this assignment. You may discuss this assignment with anyone, provided you credit such discussions when you submit the assignment.

Submitting

Email your answer to csc151-01-grader@grinnell.edu. The subject of your email should be [CSC151 01] Assignment 2 and should contain your answers to all parts of the assignment. Scheme code should be in the body of the message, not in an attachment.

Warning

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

Problem 1: Recipes as algorithms

Topics: algorithms, parts of algorithms

Human beings write algorithms for a wide variety of activities; not just computation by electronic digital computers. One of the most common kinds of algorithms we write are recipes, which are most typically implemented by other human beings.

a. Find an interesting recipe. Copy and cite that recipe.

b. For that recipe, list the parameters and variables.

c. For each parameter, list any implicit or explicit limitations on the input. For example, if you say that “flour” is an input for your recipe, must the flour be wheat flour, or will rice flour do?

d. For that recipe, indicate any situations 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.)

e. For that recipe, indicate what basic operations or subroutines the recipe author assumes that the reader already knows how to do.

f. 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 knowledge” subroutines of the algorithm.

g. Most recipes are written for “average” cooks. Rewrite the algorithm for an expert cook.

Problem 2: Scoring divers, gymnasts, and similar athletes

Topics: Scheme basics, Numeric computation

As you may know, in many sports, such as diving and gymnastics, a group of judges award scores to each athlete. To improve the accuracy of the scoring, they normally drop the top and bottom score and then compute the average. (Yes, there are many variants of this approach.) We’ll call this a robust average.

In this problem, we will work incrementally to build some portions of a program that calculate an overall score from several judges for a athlete’s performance. In addition, we want the program to work for the scores provided for any athlete, so we will generalize the operations with a form of subroutine.

Furthermore, we want the output to be easily readable and meaningful, so we will do some numeric processing to convert the precise scores into something more humanly intelligible.

In the reading on the parts of algorithms, we learned that we can write named subroutines take named parameters. While we have not yet learned how to write our own subroutines (“procedures”, in Scheme), we do have an easy way to import named values from different programs.

Say we define the file contestantA.rkt with the following contents, which represent each judge’s score for the first athlete.

#lang racket
(provide (all-defined-out))
(define judge1 7)
(define judge2 10)
(define judge3 5)
(define judge4 8)
(define judge5 6)
(define judge6 9)
(define judge7 8)
(define judge8 6)

If the file assignment2.rkt is saved in the same folder as contestantA.rkt, we can load the data and, say, calculate the average of the first two judges’ scores as follows.

#lang racket
(require (file "contestantA.rkt"))
(/ (+ judge1 judge2) 2)

Running this program would likely produce the following result.

17/2

Of course, that computed value is incomplete as a score for athlete. To find the complete score in a way that is robust to outliers, we will calculate the average of six judges’ scores after dropping the lowest and highest score, and call it robust-average. The following steps will help you solve the problem incrementally.

Part A: Finding the robust average

i. Write a definition that assigns the name total-score to a computed total of all the scores. (That is, total-score should remain correct, even if we change the values associated with judge1 through judge8.)

(define total-score ...)

ii. Write a definition that assigns the name average-score to a computed average of the scores by the usual means.

(define average-score)

iii. Write a definition that assigns the name highest-score to a computed highest score.

iv. Write a definition that assigns the name lowest-score to a computed lowest score.

v. Write a definition that assigns the name robust-average to the robust average score (that is, the score that results from dropping the lowest and highest scores and then averaging the result).

vi. To complete the notion that assignment2.rkt operates like a subroutine, create a few more contestant files, change the require statement, and verify that the results you generate are different and correct. When submitting the assignment, make sure to submit your sample files along with the assignment2.rkt file.

Part B: Cleaner averages

The averaged scores you may have seen so far may not be all that pretty. Instead of the 22/3 you might get for contestant A, we’d probably prefer 7.3 (which is an approximation of 7.3333333333333…, the decimal representation of 22/3).

You may recall that we have a number of mechanisms for rounding real numbers to integers, such as ceiling and floor. But what if we want to round not to an integer, but to only one digit after the decimal point? Scheme does not include a built-in operation for doing that kind of rounding. Nonetheless, it is fairly straightforward.

i. Add instructions to your program that calculate a version of robust-average rounded to the nearest tenth.

ii. Now, let’s generalize your instructions to round to an arbitrary number of digits after the decimal point.

Suppose precision is a non-negative integer and robust-average is the value you computed above. Write another set of instructions for rounding robust-average to use exactly precision digits after the decimal point.

> (define precision 3)
> (*your-instructions* ... robust-average ... precision ...)

As you write your instructions, you may find the expt function useful. (expt b p) computes bp.

Problem 3: Adding swim times

Topics: Scheme basics, Numeric computation

The swim team needs a program to tally the times for members’ events. Suppose the values time-1-min, time-1-sec, time-2-min, and time-2-sec represent the times of two swimmers - swimmer 1 took time-1-min minutes and time-1-sec seconds and swimmer 2 took time-2-min minutes and time-2-sec. You can assume that all of these times are sensible values (i.e., positive integers, with seconds in the range 0 to 59, inclusive).

Write a series of definitions that assign the names time-total-min and time-total-sec to the computed sum of the two times. For example, if swimmer one took 2 minutes and 15 seconds and swimmer two took 2 minutes and 11 seconds, then the total time is 4 minutes and 26 seconds. Similarly, if swimmer one took 2 minutes and 35 seconds and swimmer two took 2 minutes and 36 seconds, then the total time is 5 minutes and 11 seconds. As the second example suggests, you will need to keep the sum of seconds sum in a sensible range.

Submit at least four examples that show that your code works correctly, including in potentially complex situations. Here is one such example.

> (define time-1-min 2)
> (define time-1-sec 40)
> (define time-2-min 1)
> (define time-2-sec 21)
> (define time-total-min ...)
> (define time-total-sec ...)
> time-total-min
4
> time-total-sec
1

Evaluation

We will primarily evaluate your work on correctness (does your code compute what it’s supposed to and are your procedure descriptions accurate); clarity (is it easy to tell what your code does and how it acheives its results; is your writing clear and free of jargon); and concision (have you kept your work short and clean, rather than long and rambly).