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
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.
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,
remain correct, even if we change the values associated with
(define total-score ...)
ii. Write a definition that assigns the name
average-score to a
computed average of the scores by the usual means.
iii. Write a definition that assigns the name
highest-score to a
computed highest score.
iv. Write a definition that assigns the name
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
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
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
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.
precision is a non-negative integer and
is the value you computed above. Write another set of instructions
robust-average to use exactly
after the decimal point.
> (define precision 3) > (*your-instructions* ... robust-average ... precision ...)
As you write your instructions, you may find the
(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).