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, 8 October 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 evening 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.
This examination has an epilogue that must be completed by the evening after the exam is due. The epilogue is intended to help you reflect carefully on the examination. The epilogue is required. Failure to fill in the epilogue will incur a penalty of five points on the exam.
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.
You should not count time reviewing readings toward the amount of time you spend on the exam or on individual problems.
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 2 (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. 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 tell you otherwise, you should assume that you need to document every primary procedure with the six P's. You are encouraged to use the six P's for helper procedures. However, a short comment about its purpose will also suffice.
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 (text only) - 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: Boolean values, predicates, integer-encoded RGB colors
Write, but do not document, a suite of three
predicates red-dominates?
,
green-dominates?
,
blue-dominates?
that each take an integer-encoded RGB
color as input and hold only when the named
color channel is greater than both the others.
Note that although you did a similar problem in a previous lab, our definition of dominance here is slightly different than in that lab. For example,
>
(red-dominates? (irgb 128 64 64))
#t
>
(red-dominates? (irgb 64 128 64))
#f
>
(red-dominates? (irgb 64 64 128))
#f
>
(red-dominates? (irgb 128 64 128))
#f
Topics: Color transformations, integer-encoded RGB colors, conditionals
Write, but do not document, the color transform
irgb-color-enhance
that takes an
integer-encoded RGB color as input and applies
irgb-redder
if red dominates the color,
irgb-bluer
if blue dominates the color,
irgb-greener
if green dominates the color, and
leaves the color unchanged otherwise.
![]() |
flowers |
![]() |
(image-variant flowers irgb-color-enhance) |
![]() |
(image-variant flowers (o irgb-color-enhance irgb-color-enhance)) |
Topics: Code reading, anonymous procedures, local bindings, concision, image transforms
There are many ways to make code better, including avoiding unnecessary repeated code and computation. The procedure below applies a color transform that makes an image appear as though it consisted only of a single color, which is the the second parameter. Rewrite this procedure to eliminate as much of the repeated code and computation as you can.
In addition, you could strive to make the code even more elegant by making it as concise as possible. (Hint: The most concise version may require you to rethink the method used to compute the three color channels.)
(define monochrome (lambda (image lens-color) (image-variant image (lambda (color) (irgb (* 0.5 (+ (* 0.30 (irgb-red color)) (* 0.59 (irgb-green color)) (* 0.11 (irgb-blue color)) (irgb-red (color->irgb lens-color)))) (* 0.5 (+ (* 0.30 (irgb-red color)) (* 0.59 (irgb-green color)) (* 0.11 (irgb-blue color)) (irgb-green (color->irgb lens-color)))) (* 0.5 (+ (* 0.30 (irgb-red color)) (* 0.59 (irgb-green color)) (* 0.11 (irgb-blue color)) (irgb-blue (color->irgb lens-color)))))))))
You do not need to document your rewritten version of
monochrome
.
Topics: Color representations (color names and integer-encoded RGB colors), color transformations, list iteration, composition
In our explorations of colors, we found that we could start with a
procedure such as irgb-redder
that takes a color
as a parameter and produces a new color, and use that procedure to
transform a whole image. Let's try a similar thing with lists of
color names. (Yes, it's clear that lists of color names cannot be
directly converted to images, but it is certainly possible to use them
to create images.) That is, let's consider procedures that transform
each color name in a list. Note that this process will be slightly
more difficult, because the color transformations expect integer-encoded
RGB colors rather than color names.
Write, but do not document, a procedure,
(
, that, given a list of color
names, returns a new list of color names, with each color name in the
resulting list an approximation of the color that results from applying
color-names-much-darker
color-names
)irgb-darker
twice to the corresponding color in
the original list. For example,
>
(color-names-much-darker (list "yellow" "green" "blue" "pink" "red" "violet" "black" "white"))
'("gold" "darkgreen" "mediumblue" "tan" "red" "orchid" "black" "gainsboro")
Your procedure will look something like this.
(define color-names-much-darker
(lambda (color-names)
BODY))
Make the body of this procedure as concise as you can. You should be able to write the body with seven units of text (variable or procedure names), plus parentheses.
Note: Very clever programmers can use fewer than the 11 total units of
text we suggest (seven in the body and the four we provided), although
it requires changing some of those we provided. You may receive a
bit of extra credit if you can achieve such a solution. Note that
using the alternative define form of (define (name params) body))
does not count.
Topics: Homogeneous lists, conditionals, composition
Document and write a procedure, (
,
that takes a list of colors and produces a list of the specified length
in which the colors cycle in the same order as in
color-cycle
list-of-colors
list-length
)list-of-colors
.
>
(color-cycle (list "red" "green" "blue") 5)
'("red" "green" "blue" "red" "green")
>
(color-cycle (list "red" "green" "blue") 9)
'("red" "green" "blue" "red" "green" "blue" "red" "green" "blue")
>
(color-cycle (list "red") 6)
'("red" "red" "red" "red" "red" "red")
>
(color-cycle (list "red" "orange" "yellow" "green" "blue" "indigo") 2)
'("red" "orange")
>
(color-cycle (list "red" "orange" "yellow" "green" "blue" "indigo") 9)
'("red" "orange" "yellow" "green" "blue" "indigo" "red" "orange" "yellow")
You may not use recursion to solve this problem. You must use a
map
expression to implement color-cycle
.
Hint: You should know how to make cycles of numbers. Use those cycles to help in this problem.
Topics: Color blends, computing circles, image-compute!
In the reading on building images, you learned how to compute an image of circles using the distance of each image pixel from a center point thresholded by the specified radius. In the corresponding lab, you learned how to generalize a linear (horizontal) blend from one color component's value to another. In this problem we will combine those two approaches.
Write, but do not document, a procedure
(
that generates an image containing
a radial color
blend where the value of the color's green component is
radial-green-blend
width
height
center-col
center-row
radius
initial
final
)initial
at
(center-col
,
center-row
) and final
at all points of a distance of radius
from
the center of the circle, while the red and blue components remain
zero; the pixels between the center and the radius should blend
smoothly from initial
to
final
. Outside the circle, pixels should be
black.
In writing such a procedure, you may find the
euclidean-distance
procedure from the reading
helpful. (If you incorporate it into your exam, please be sure to
cite its source.)
Hint: Your computation of the green component
should look very similar to
horiz-blue-blend
. However, instead of
transitioning from column zero to width
, the
calculation will span a distance (from the center) of zero up to the
radius.
Hint: Locally bind the distance of a given pixel from the center and use that distance both in a conditional test and in the calculation for the color's green component.
![]() |
(radial-green-blend 256 256 64 64 128 0 255) |
![]() |
(radial-green-blend 256 256 64 64 128 255 0) |
Topics: Heterogeneous lists, GIMP tools, conditionals, local bindings
Document and write a procedure,
(
,
that selects the portion of the image described by
image-select-drawing!
image
drawing
)drawing
, using the policies that (a) if the
color of the drawing is black, it adds the outline of the drawing
to the current selection; (b) if the color of the drawing is white,
it subtracts the outline of the drawing from the current selection;
(c) if the color of the drawing is anything else, it replaces the
current selection with the outline of the drawing.
You may choose to support only the two primitive drawing types (ellipses and rectangles). However, if you choose to limit your support to those two types, you need to document that limitation carefully in your preconditions.
As you likely noted in problem 3 above, highly repetitious
code is hard to read and longer than it needs to be. In writing
image-select-drawing!
, you should do your best
to find ways to avoid writing the same expression more than once and
even to avoid expressions that are nearly identical. And, now that
you know how to use local bindings, you should use those preferentially
over global bindings.
Here's an example of image-select-drawing!
in
action.
(define canvas (image-show (image-new 200 200))) (define c1 (scale-drawing 200 drawing-unit-circle)) (define c2 (hshift-drawing -10 (vshift-drawing -40 (recolor-drawing "white" c1)))) (define c3 (hshift-drawing 130 (vshift-drawing 70 c1))) (image-select-nothing! canvas) ; Clears initial selection |
![]() |
(image-select-drawing! canvas c1) ; Adds quarter circle (context-set-fgcolor! "black") (context-set-brush! "2. Hardness 100" 16) (image-stroke! canvas) ; Strokes the quarter circle in a thick black line |
![]() |
(image-select-drawing! canvas c2) ; White, so removes part of a circle (context-set-fgcolor! "red") (context-set-brush! "2. Hardness 100" 12) (image-stroke! canvas) ; Strokes the new selection in a medium red line |
![]() |
(image-select-drawing! canvas c3) ; Black, so adds circle (context-set-fgcolor! "blue") (context-set-brush! "2. Hardness 100" 8) (image-stroke! canvas) ; Strokes the new selection in a medium-thin blue line |
![]() |
(image-select-drawing! canvas (recolor-drawing "grey" c3)) ; Replace (context-set-fgcolor! "green") (context-set-brush! "2. Hardness 100" 4) (image-stroke! canvas) ; Strokes the new selection in a thin green line |
![]() |
(image-select-drawing! canvas c2) ; White, so removes part of a circle (context-set-fgcolor! "white") (context-set-brush! "2. Hardness 100" 1) (image-stroke! canvas) ; Strokes the new selection in a very thin white line |
![]() |
Here's a slightly more complex example that builds a list of drawings
using a technique you've seen before and then uses them to create a
more complex image. (Note that for-each
is much like
map
, except that you use it with side-effecting procedures
to just do a series of operations, rather than to compute a new list.)
(define canvas (image-show (image-new 400 300))) (define BLACK (irgb 0 0 0)) (define WHITE (irgb 255 255 255)) (define STEPS 30) (define things (map (lambda (i) (hshift-drawing (* i (/ (image-width canvas) STEPS)) (vshift-drawing (* i i (/ (image-height canvas) (square STEPS))) (recolor-drawing (if (even? i) BLACK WHITE) (scale-drawing (+ 20 (/ i 2)) drawing-unit-circle))))) (iota STEPS))) (for-each (l-s image-select-drawing! canvas) things) (context-set-fgcolor! "red") (image-fill! canvas) (context-set-fgcolor! "black") (context-set-brush! "2. Hardness 100" 2) (image-stroke! canvas) (image-select-nothing! canvas) (context-update-displays!)
And here's the image that results.
Here we will post answers to questions of general interest. Please check here before emailing your questions!
define
.
list-ref
to extract the various
attributes of a drawing. Is that okay?
list-ref
in problem
7: I've been using the drawing-whatever
procedures.
Is that okay?
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.)
rgb-blue
should have been used in Problem 3. [ST, 1 point]length
to color-cycle
aliased Scheme's built-in procedure name. [ZS, 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.