Functional Problem Solving (CSC 151 2014F) : Assignments
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] - [FAQ] [Teaching & Learning] [Grading] [Rubric] - [Calendar]
Current: [Assignment] [EBoard] [Lab] [Outline] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Readings]
Reference: [Setup] [VM] [Errors] - [Functions A-Z] [Functions By Topic] - [Racket] [Scheme Report (R5RS)] [R6RS] [TSPL4]
Related Courses: [Davis (2013F)] [Rebelsky (2014S)] [Weinman (2014F)]
Misc: [Submit Questions] - [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] - [Issue Tracker (Course)]
Assigned: Wednesday, 17 September 2014
Due: The due dates for various tasks are as follows.
This is a take-home examination. You may use any time or times you deem appropriate to complete the exam, provided you return it to me by the due date.
This examination has a prologue that must be completed by the Friday afternoon before the exam is due. The prologue is intended to help you get started thinking about the examination. The prologue is optional. However, if you intend to invoke the “there's more to life” option (see below), you must turn in the prologue by the specified deadline.
There are seven problems on this examination. Each problem is worth the same number of points. Although each problem is worth the same amount, problems are not necessarily of equal difficulty.
Read the entire exam before you begin.
We expect that someone who has mastered the material and works at a moderate rate should have little trouble completing the exam in a reasonable amount of time. In particular, this exam is likely to take you about three to four hours, depending on how well you've learned the topics and how fast you work. You should not work more than five hours on this exam. Stop at five hours and write “There's more to life than CS” and you will earn at least the equivalent of 70% on this exam, provided you filled in the prologue by the specified deadline. You may count the time you spend on the prologue toward those five hours. With such evidence of serious intent, your score will be the maximum of (1) your actual score or (2) the equivalent of 70%. The bonus points for errors are not usually applied in the second situation.
We would also appreciate it if you would write down the amount of time each problem takes. Each person who does so will earn two points of extra credit for the exam. Because we worry about the amount of time our exams take, we will give two points of extra credit to the first two people who honestly report that they have completed the exam in four hours or less or have spent at least four hours on the exam. In the latter case, they should also report on what work they've completed in the four hours. After receiving such notices, we may change the exam.
This examination is open book, open notes, open mind, open computer, open Web. However, it is closed person. That means you should not talk to other people about the exam. Other than as restricted by that limitation, you should feel free to use all reasonable resources available to you.
As always, you are expected to turn in your own work. If you find ideas in a book or on the Web, be sure to cite them appropriately. If you use code that you wrote for a previous lab or homework, cite that lab or homework as well as any students who worked with you. If you use code that you found on the course Web site, be sure to cite that code. You need not cite the code provided in the body of the examination.
Although you may use the Web for this exam, you may not post your answers to this examination on the Web. And, in case it's not clear, you may not ask others (in person, via email, via IM, via IRC, by posting a please help message, or in any other way) to put answers on the Web.
Because different students may be taking the exam at different times, you are not permitted to discuss the exam with anyone until after I have returned it. If you must say something about the exam, you are allowed to say “This is among the hardest exams I have ever taken. If you don't start it early, you will have no chance of finishing.” You may also summarize these policies. You may not tell other students which problems you've finished. You may not tell other students how long you've spent on the exam.
You must include both of the following statements on the cover sheet of the examination.
Please sign and date each statement. Note that the statements must be true; if you are unable to sign either statement, please talk to me at your earliest convenience. You need not reveal the particulars of the dishonesty, simply that it happened. Note also that inappropriate assistance is assistance from (or to) anyone other than Professor Rebelsky.
Exams can be stressful. Don't let the stress of the exam lead you to make decisions that you will later regret.
You must present your exam to me in two forms: both physically and
electronically. That is, you must write all of your answers using
the computer, print them out, number the pages, put your name on the
top of every page, staple them together, and hand me the printed
copy. You must also email me a copy of your exam with the subject
CSC 151.01 Exam 1 (Your Name)
. You should create the
emailed version by copying the various parts of your exam and pasting
them into an email message. In both cases, you should put your answers
in the same order as the problems. Failure to name and number the
printed pages will lead to a penalty of at least two points. Failure
to turn in both versions may lead to a much worse penalty.
While your electronic version is due at 10:30 p.m. Tuesday, your physical copy will be submitted in class on Wednesday. It is presumed the physical copy matches the electronic copy. Any discrepancies (other than formatting) will be considered a misrepresentation of your work and referred to the Committee on Academic Standing.
In many problems, we ask you to write code. Unless we specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. You should use examples other than those that may be provided with the exam. Do not include resulting images; we should be able to regenerate those.
Unless we explicitly ask you to document your procedures, you need not write introductory comments.
Just as you should be careful and precise when you write code and documentation, so should you be careful and precise when you write prose. Please check your spelling and grammar. Because we should be equally careful, the whole class will receive one point of extra credit for each error in spelling or grammar you identify on this exam. We will limit that form of extra credit to five points.
We will give partial credit for partially correct answers. We are best able to give such partial credit if you include a clear set of work that shows how you derived your answer. You ensure the best possible grade for yourself by clearly indicating what part of your answer is work and what part is your final answer.
I may not be available at the time you take the exam. If you feel that a question is badly worded or impossible to answer, note the problem you have observed and attempt to reword the question in such a way that it is answerable. If it's a reasonable hour (8am-10pm), feel free to try to call me (cell phone - 641-990-2947).
I will also reserve time at the start of each class before the exam is due to discuss any general questions you have on the exam.
Topics: Documentation, unit testing, writing procedures, numeric values
Expressing numbers in their rational, fractional form often helps us avoid errors due to rounding. Moreover, to keep simple fractions from being expressed with arbitrarily large numbers (for example, 1/2 = 123456789/246913578), we typically like to express them in what is called “reduced” form.
What does it mean for a fraction to be reduced? Simply put, the numerator and denominator should share no factors in common. Put another way, we should not be able to divide the numerator and denominator by the same whole number to get smaller whole numbers.
Conveniently, a mathematical quantity known as the “greatest common divisor” (or gcd, as it is sometimes called) expresses a notion that will help us reduce fractions. The gcd is simply the largest factor shared by two given numbers. Thus, if the fraction's numerator and denominator do not have a gcd of 1, then the fraction could be reduced by dividing both terms by this number. Hence to reduce a fraction, it seems we should divide both the numerator and denominator by the gcd. The results would subsequently have a gcd of one, so we would know the fraction is reduced.
We will put this knowledge to use with a simple set of routines to add two fractions. You might recall that to add fractions, we need to place the numerator over a common denominator. The simplest way to do this is to just multiply the two denominators. In order to make sure we are preserving the fractions' values, multiplying each by one, the numerator of each would also need to be multiplied by the same number; that is, the other fraction's denominator.
More precisely, to add two fractions a/b
and
c/d
, we put the result over the common denominator
b*d
, and the two numerators become a*d
and
c*b
, respectively. Putting it all together we have the
sum a/b + c/d = (a*d + c*b) / (b*d)
. We could write a
pair of routines, (
and
numerator-sum-fraction
num1
den1
num2
den2
)(
to
calculate these simple results.
denominator-sum-fraction
num1
den1
num2
den2
)
>
(numerator-sum-fraction 1 8 1 16)
; 1/8+1/16 = (1*16 + 1*8)/(8*16) = 24/12824
>
(denominator-sum-fraction 1 8 1 16)
128
>
(numerator-sum-fraction 1 8 -1 16)
; 1/8 - 1/16 = (1*16 + (-1)*8)/(8*16) = 8/1288
>
(denominator-sum-fraction 1 8 -1 16)
128
You may have noticed that these fractions are not reduced. To
accomplish that, we could write a procedure
(
that
calculates the (unreduced) numerator and denominator of the fraction
sum and finds their greatest common divisor. Luckily, the built-in
Scheme function reduction-factor
num1
den1
num2
den2
)(
can do
this for you. This algorithm works when we follow the common and
decent convention of using only positive denominators.
gcd
a
b
)
How would you implement
(
and
numerator-sum-fraction-reduced
num1
den1
num2
den2
)(
to
calculate the reduced fraction sum? Now that we have broken down
the problem, it should be relatively easy: Give the simple numerator
divided by the reduction factor. You would do likewise for the
denominator.
denominator-sum-fraction-reduced
num1
den1
num2
den2
)
numerator-sum-fraction-reduced
Recall that writing documentation for a procedure before you write
the implementation can help you clarify the contractual behavior and
inspire your design. Using the 6Ps, document the procedure numerator-sum-fraction-reduced
described
above.
Your documentation may make reference to
numerator-sum-fraction
,
reduction-factor
,
denominator-sum-fraction
, and/or
denominator-sum-fraction-reduced
.
numerator-sum-fraction-reduced
Recall that writing tests for a procedure before you write the procedure itself is also useful for thinking about how to design the procedure and what sorts of inputs it should work or fail on, especially so-called "corner cases" at the boundary of different behaviors.
Of course, it's hard to run a test without a procedure to test, so we'll start with a “stub” procedure - one that's not guaranteed to work correctly, but that has the proper form.
(define numerator-sum-fraction-reduced (lambda (first-numerator first-denominator second-numerator second-denominator) ; STUB 0))
Write a comprehensive unit test suite for the procedure
numerator-sum-fraction-reduced
.
That is, your
tests should verify the correctness of results for inputs from a
variety of different regions of the problem space, as well as the
borders of those regions.
For example, unit tests for a drawing manipulation procedure would
likely include tests on inputs from all four quadrants of the image
plane (as well as those touching the axes), simple drawings
(ellipses and rectangles) and compound drawings (e.g., the results
of calling drawing-group
). Depending on the
functionality being tested, one might also test drawings of
different colors, too.
Your responsibility in this problem is to think about the range of valid inputs for adding rational numbers represented by a numerator and a denominator, testing the results for each.
numerator-sum-fraction-reduced
Finally, implement the procedures described above:
(numerator-sum-fraction
num1
den1
num2
den2
)
(denominator-sum-fraction
num1
den1
num2
den2
)
(reduction-factor
num1
den1
num2
den2
)
(numerator-sum-fraction-reduced
num1
den1
num2
den2
)
(denominator-sum-fraction-reduced
num1
den1
num2
den2
)
Topics: Drawings as values, writing procedures
Many students are puzzled by the behavior of scale-drawing
.
In particular, scale-drawing
scales not just the width and
height of a drawing, but also the horizontal and vertical offset of the
drawing. (In effect, scale-drawing
scales the drawing around
the position (0,0).)
What should we do if we want to scale a drawing around the center of
the drawing, rather than around the position (0,0)? We could write
our own scaling procedure, say scale-drawing-centered
.
Here's some documentation for that procedure.
;;; Procedure: ;;; scale-drawing-centered ;;; Parameters: ;;; scale-factor, a positive real number ;;; drawing, a drawing ;;; Purpose: ;;; Scale the original drawing by the scale factor, centering ;;; at the same location. ;;; Produces: ;;; scaled, a drawing ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; scaled appears the same as drawing (i.e., if drawing is a rectangle, ;;; then scaled is a rectangle; if drawing is an ellipse, then scaled ;;; is an ellipse; if drawing is compound, then scaled is compound, ;;; and the components of scaled are appropriate scaled versions of ;;; drawing, with the offset between components equally scaled). ;;; Alternately, ;;; (scale-drawing-centered scaled (/ 1 scale-factor)) = drawing. ;;; (drawing-width scaled) = (* scale-factor (drawing-width drawing)) ;;; (drawing-height scaled) = (* scale-factor (drawing-height drawing)) ;;; (drawing-center-x scaled) = (drawing-center-x drawing) ;;; (drawing-center-y scaled) = (drawing-center-y drawing)
To check the postconditions, we need definitions of
drawing-center-x
and drawing-center-y
.
;;; Procedure: ;;; drawing-center-x ;;; Parameters: ;;; drawing, a drawing ;;; Purpose: ;;; Find the x coordinate of the center of drawing. ;;; Produces: ;;; x, a real number ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; x is a point midway between the left edge and the right edge ;;; of drawing. That is, ;;; (- x (drawing-left drawing)) = (- (drawing-right drawing) x) (define drawing-center-x (lambda (drawing) (+ (drawing-left drawing) (* 1/2 (drawing-width drawing))))) ;;; Procedure: ;;; drawing-center-y ;;; Parameters: ;;; drawing, a drawing ;;; Purpose: ;;; Find the y coordinate of the center of drawing. ;;; Produces: ;;; y, a real number ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; y is a point midway between the top edge and the bottom edge ;;; of drawing. That is, ;;; (- y (drawing-left drawing)) = (- (drawing-bottom drawing) x) (define drawing-center-y (lambda (drawing) (+ (drawing-top drawing) (* 1/2 (drawing-height drawing)))))
Implement scale-drawing-centered
.
Note: An appendix to this examination provides a test suite for
scale-drawing-centered
.
Topics: Drawings as values, documentation, writing procedures, side effects, pixels
We have seen that it is possible to convert a drawing to an image
using the drawing->image
procedure. Is it possible
to do the reverse? That is, can we convert an image to a corresponding
drawing? Perhaps not so surprisingly, the answer is yes. How can
we do this conversion? We can grab the color of a pixel at each location
and build a small square (or circle, depending on the effect we want)
of that color and at that location.
But that's a lot of work for a whole image. It also involves stepping through all of the positions in the image, and you do not yet know how to repeat actions. So, let's look at a simpler problem.
Let's suppose that we want to take an image and make a grid of
four ellipses, corresponding to four points in the image. What
form should that drawing take? It will be a compound drawing
(created by drawing-group
or something similar) of
four ellipses with the following characteristics.
Write a procedure, sample-four
, that takes as input an
image and returns a compound drawing of a grid of four ellipses
as described above.
As an example, consider the following code and images.
> (define kitten (image-load "/home/rebelsky/Desktop/kitten.jpg")) ; Use /home/student/Desktop/kitten.jpg on virtual machines > (image-show kitten) 11 > (image-show (drawing->image (sample-four kitten) (image-width kitten) (image-height kitten))) 12 > (define kit2 (image-load "/home/rebelsky/Desktop/kitten.jpg")) > (drawing-render! (sample-four kitten) kit2) 13 > (image-show kit2) 13
Hint: You will likely find it useful to write one or more helper procedures to handle common parts of the algorithm.
Topics: Procedures, raster graphics, RGB colors, generalization
A quincunx is a formation of four items in a square or rectangle, plus a fifth in the center, such as on the side of a standard die with five dots.
Write a procedure (
that changes the pixels in the four corners and the center
of image-quincunx!
image
irgb-color
)image
to irgb-color
.
Topics: Documentation, code reading, drawings as values
Consider the following procedure, which is not only poorly named, but also has poorly-named parameters.
(define f (lambda (a b c d e)(hshift-drawing (+ b (* 1/2 d))(vshift-drawing (+ c (* 1/2 e))(hscale-drawing d (vscale-drawing e (recolor-drawing a drawing-unit-circle)))))))
Make this procedure definition easier to read as follows.
First, reformat the procedure so that the indentation properly demonstrates nesting. That is, you should choose appropriate points to put in spaces and carriage returns. Remember that DrRacket will re-indent for you after you put in those returns, as long as you select the text and type Tab.
Then, figure out what the procedure does. You might analyze the
code to understand it. You might run it and look at the results.
You might do a combination of the two. After doing so, change the
names in the procedure to clarify the roles of various things. You
should certainly rename the procedure f
and the
parameters; both the procedure and the parameters should have clear
names that the average reader would understand. (As a hint, start
by figuring out what type each parameter should be.)
Finally, write introductory comments (the six Ps) to explain
the purpose (and the other Ps) of the procedure formerly named
f
.
When you format your exam, please put the introductory comments before the revised procedure definition.
The following code defines a test suite,
suite-scale-drawing-centered
, that runs a large number of
tests on scale-drawing-centered
. You may find it useful
as you develop your code.
;;; Procedure: ;;; tests-scale-drawing-centered-postconditions ;;; Parameters: ;;; drawing, a drawing ;;; scale, a positive real number ;;; scaled, a drawing ;;; Purpose: ;;; Builds a suite of tests that check if scaled meets the postconditions ;;; of scale-drawing-centered. ;;; Produces: ;;; suite, a test suite ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; If the postconditions of scale-drawing-centered are not met, ;;; suite reports an error when it is run. ;;; Otherwise, ;;; suite has no output when run (define tests-scale-drawing-centered-postconditions (lambda (drawing scale scaled) (test-suite "tests of postconditions" (test-case "Same center x coordinates" (check-= (drawing-center-x drawing) (drawing-center-x scaled) .01)) (test-case "Same center y coordinates" (check-= (drawing-center-y drawing) (drawing-center-y scaled) .01)) (test-case "Correct width" (check-= (drawing-width scaled) (* scale (drawing-width drawing)) .01)) (test-case "Correct height" (check-= (drawing-height scaled) (* scale (drawing-height drawing)) .01)) (test-case "Correct type" (check-eq? (drawing-type scaled) (drawing-type drawing)))))) ;;; Procedure: ;;; tests-scale-drawing-centered-helper ;;; Parameters: ;;; drawing, a drawing ;;; scale, a scale ;;; Purpose: ;;; Builds a scaled version of drawing using scale-drawing-centered, ;;; then calls test-scale-drawing-centered-postconditions to build ;;; a suite to verify those postconditions ;;; Produces: ;;; suite, a test suite ;;; Preconditions: ;;; [No additional] ;;; Postconditions ;;; Suite ensures that (scale-drawing-centered drawing scale) meets ;;; the stated postconditions. (define tests-scale-drawing-centered-helper (lambda (drawing scale) (tests-scale-drawing-centered-postconditions drawing scale (scale-drawing-centered scale drawing)))) ;;; Procedure: ;;; tests-scale-drawing-centered ;;; Parameters: ;;; drawing, a drawing ;;; Purpose: ;;; Checks to see if scale-drawing-centered produces a reasonable ;;; answer for the given drawing using a variety of scales. ;;; Produces: ;;; suite, a test suite ;;; Preconditions: ;;; [No additional] ;;; Postconditions: ;;; When suite is run, if no errors are generated, then ;;; scale-drawing-centered is likely to work correctly on drawing. (define tests-scale-drawing-centered (lambda (drawing) (test-suite "Tests of one drawing" (test-suite "Same size" (tests-scale-drawing-centered-helper drawing 1)) (test-suite "Smaller, exact scale factor of 1/2" (tests-scale-drawing-centered-helper drawing 1/2)) (test-suite "Smaller, inexact scale factor of 0.37" (tests-scale-drawing-centered-helper drawing 0.37)) (test-suite "Smaller, exact scale factor of 27/31" (tests-scale-drawing-centered-helper drawing 27/31)) (test-suite "Larger, exact scale factor of 2" (tests-scale-drawing-centered-helper drawing 2)) (test-suite "Larger, inexact scale factor of 1.35" (tests-scale-drawing-centered-helper drawing 1.35)) (test-suite "Larger, exact scale factor of 31/27" (tests-scale-drawing-centered-helper drawing 31/27))))) ;;; Value: ;;; suite-scale-drawing-centered ;;; Type: ;;; RackUnit test suite ;;; Description: ;;; Tests of scale-drawing-centered with various drawings and ;;; various scale factors. (define suite-scale-drawing-centered (test-suite "Tests of scale-drawing-centered" (test-suite "Unit circle" (tests-scale-drawing-centered drawing-unit-circle)) (test-suite "Circle h-shifted right" (tests-scale-drawing-centered (scale-drawing 10 (hshift-drawing 5 drawing-unit-circle)))) (test-suite "Square v-shifted down" (tests-scale-drawing-centered (scale-drawing 15 (vshift-drawing 3 drawing-unit-square)))) (test-suite "Square h-shifted left" (tests-scale-drawing-centered (scale-drawing 11 (hshift-drawing -1 drawing-unit-square)))) (test-suite "Circle v-shifted up" (tests-scale-drawing-centered (scale-drawing 13 (vshift-drawing -2 drawing-unit-circle))))))
You can run these tests with the following instruction.
>
(run-tests suite-scale-drawing-centered)
Here we will post answers to questions of general interest. Please check here before emailing your questions!
Here you will find errors of spelling, grammar, and design that students have noted. Remember, each error found corresponds to a point of extra credit for everyone. We usually limit such extra credit to five points. However, if we make an astoundingly large number of errors, then we will provide more extra credit. (And no, we don't count errors in the errata section or the question and answer sections.)
numerator-sum-fraction-reduce
appeared twice
in place of reduction-factor
on problem
3. [ZS and MI, 1 point]
drawing-unit-centered
instead of scale-drawing-centered
in the description of the test suite for problem 4. [EH, 1 point]
Some of the problems on this exam are based on (and at times copied from) problems on previous exams for the course. Those exams were written by Janet Davis, Rhys Price Jones, Samuel A. Rebelsky, John David Stone, Henry Walker, and Jerod Weinman. Many were written collaboratively, or were themselves based upon prior examinations, so precise credit is difficult, if not impossible.
Some problems on this exam were inspired by conversations with our students. We thank our students for that inspiration. Usually, a combination of questions or discussions inspired a problem, so it is difficult and inappropriate to credit individual students.
The photograph of the kitten was released for public use at
http://public-photo.net/displayimage-2485.html
.
It appears that site is now down.