- Assigned
- Wednesday, Sep 5, 2018
- Due
- Tuesday, Sep 11, 2018 by 10:30pm
- 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.
- 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. Submit your scheme code as an attachment for assignments.

*Topics: algorithms, parts of algorithms*

We can describe a wide variety of activities as algorithms, including activities that have nothing to do with a computer. One such activity is holding a family picnic. As we’ve seen in class, describing activities in unambiguous detail can be challenging; this problem will push you to be detailed while also thinking about the parts of algorithms in a real-world scenario.

You are responsible for organizing a family picnic. Your family members will bring some items that you do not need to worry about, but you must organize a location for the picnic, provide one food item, and run at least one activity such as a game, a family photo, etc.

Respond to each of the following parts:

a. First, you will need to decide on an agenda. What is the location of your picnic? What food item will you prepare? What activity will you run?

b. Write out your algorithm in enough detail that a reasonable person could follow it. The person running your algorithm undertands how to purchase items, go to destinations, make phone calls, etc. but may not be an experienced cook or event organizer. Make sure your algorithm uses each of the parts of algorithms we have discussed in class.

c. What are the building blocks for your picnic algorithm? Identify any basic operations you will be able to perform, and any basic values you are assuming are available to you.

d. Identify one use of sequencing in your algorithm.

e. Identify one use of a variable in your algorithm.

f. Identify one use of a conditional in your algorithm.

g. Identify one use of repetition in your algorithm.

h. Identify one use of a subroutine in your algorithm.

i. List the inputs and outputs for your algorithm.

*Topics: Scheme basics, Numeric computation*

Many computers, including those on MathLAN, represent time as the number of seconds elapsed since midnight on January 1, 1970, a time known as the *UNIX epoch*. We’ll use these *timestamps* to compute the day of week from a timestamp.

We will represent days of the week with integers; Sunday is represented by `0`

, Monday by `1`

, Tuesday by `2`

, and so on until Saturday, which is represented by `6`

. January 1, 1970 was a Thursday (or a `4`

in our representation). Write a series of definitions that assign the variable `day-of-week`

to be the day of the week for the day represented by the time in the variable `timestamp`

.

Submit at least four example dates to show that your code works correctly. Here is one such example (which you may include in your four examples):

```
; This timestamp is for 12:00am GMT on May 25, 1977, the original release of Star Wars Episeode IV
; This day was a Wednesday
(define timestamp-1 233366400)
; You may want to include intermediate definitions here to make your final expression simpler
(define day-of-week-1 ...)
; day-of-week-1 should now be define to 3, which represents Wednesday
```

You may find the website http://www.timestampgenerator.com useful for creating test cases.

*Note: You may ignore complicated time and date issues like time zones and leap seconds in your day calculations. To make sure your answers are correct, I recommend choosing times in Greenwich Mean Time.*

*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.

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.

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 b

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).