Assignment 2 – Exploring Algorithms

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.

Problem 1: Organizing A Family Picnic

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.

Problem 2: Timestamps

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.

Problem 3: 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.

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