Exam 1: Scheme and Image Basics

Assigned: Wednesday, 18 September 2013

Due: 10:30 p.m., Tuesday, 24 September 2013

Preliminaries

Exam format

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.

There are 10 problems on this examination. Each problem is worth 10 points, for a total of 100 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 two to three hours, depending on how well you've learned the topics and how fast you work. You should not work more than four hours on this exam. Stop at four hours and write “There's more to life than CS” and you will earn at least 70 on this exam, provided you give evidence of a serious attempt on at least 6 of the problems or come talk to me about the exam no later than one week after it is returned. With such evidence of serious intent, your score will be the maximum of 1) your actual score out of 100, 2) your best 7 questions scaled to a maximum of 90, or 3) 70.

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. 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 three hours or less or have spent at least three hours on the exam. In the latter case, they should also report on what work they've completed in the three hours. After receiving such notices, we may change the exam.

Academic honesty

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

I have neither received nor given inappropriate assistance on this examination.
I am not aware of any other students who have given or received inappropriate assistance on this 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.

Presenting Your Work

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, and hand me the printed copy. You must also email me a copy of your exam. 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 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 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.

Getting Help

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.

Problems

Part A: Preconditions and Postconditions

As you've learned, the preconditions and postconditions of a procedure are a contract between the people who implement the procedure (the “implementers”) and the people who use the procedure (the “clients”). If inputs meet the preconditions, the output is expected to meet the postconditions.

There's a tension in this duality - the clients want preconditions as broad as possible while the implementers want them as narrow as possible. (After all, if no inputs meet your preconditions, your procedure can do anything you want.) Similarly, implementers want as few restrictions as possible on postconditions while clients often want many guarantees. Good procedure design involves balancing the two desires. But we don't always get that balance right.

Problem A.1. Checking Preconditions

Consider the following procedure.

;;; Procedure:
;;;   colored-square
;;; Parameters:
;;;   size, a real number
;;;   color, a string   
;;; Purpose:
;;;   Create an image that is size by size, colored color.
;;; Produces:
;;;   img, an image id
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (image-width img) = size
;;;   (image-height img) = size
;;;   The color of the image is color
(define colored-square
  (lambda (size color)
    (image-show 
     (drawing->image
      (drawing-scale
       (drawing-hshift
        (drawing-vshift
         (drawing-recolor drawing-unit-square color)
         0.5)
        0.5)
       size)
      size
      size))))

There are a number of inputs that meet the preconditions, but that lead to an output that does not meet the postconditions (or, better yet, that cause the procedure to crash).

a. Identify a few such inputs.

b. Rewrite the preconditions so that they guarantee (to the best of your ability) that the procedure will succeed. You must choose reasonably broad preconditions. (E.g., you can't say “color must be "red" and size must be 10”, although those preconditions will certainly guarantee success.)

Problem A.2. Incomplete Postconditions

Consider this documentation for the procedure gcd.

;;; Procedure:
;;;   gcd
;;; Parameters:
;;;   x, a positive integer
;;;   y, a positive integer
;;; Purpose:
;;;   Compute the gcd of x and y (whatever that is)
;;; Produces:
;;;   divisor, a positive integer
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   divisor divides x.  That is, (remainder x divisor) is 0
;;;   divisor divides y.  That is, (remainder y divisor) is 0

The postconditions are somewhat vague, which means that a lazy implementer need not achieve the likely goals of the client.

Write a procedure that meets the postconditions for all preconditions, but does not achieve the goal of computing a greatest common divisor.

Part B: Numeric Values

Problem B.1. Fairer Ratings

In many situations where judges are asked to rate performers, some worry that judges may be biased. You can't really adjust for a large number of biased ratings, but you can try to eliminate some of the outliers.

Write a procedure, fair-rating, that takes as input seven values, throws out the lowest and highest value, and then averages the remaining values.

Problem B.2. Documenting Your Code

Write the six-P style documentation for fair-rating.

Problem B.3. Computing with the Calendar

Write the months-from-start procedure, which we've documented as follows:

;;; Procedure:
;;;   months-from-start
;;; Parameters:
;;;   start-month, an exact integer
;;;   number-of-months, an exact integer
;;; Purpose:
;;;   To compute what month it will be number-of-months from the
;;;   start-month.  January is represented by 1, February by 2, and so on.
;;; Produces:
;;;   end-month, an exact integer
;;; Preconditions:
;;;   1 <= start-month <= 12
;;; Postconditions:
;;;   1 <= end-month <= 12
;;;   (end-month - start-month) modulo 12 = number-of-months modulo 12

For example, we might see the following when interacting with this procedure.

> (months-from-start 5 2)
7
> (months-from-start 5 -3)
2
> (months-from-start 5 12)
5
> (months-from-start 5 9)
2
> (months-from-start 3 9)
12

Part C: Drawings as Values

Problem C.1. Smaller Neighbors

The laboratory on writing your own procedures asks you to write a procedure, add-smaller-neighbor, that adds a slightly smaller neighbor to an image.

Most students wrote something like the following.

(define add-smaller-neighbor
  (lambda (drawing)
    (drawing-group drawing
                   (drawing-hshift (drawing-scale drawing .75)
                                   (drawing-width drawing)))))

This procedure works fine if the input drawing is on the left margin of the screen. Unfortunately, if the input drawing is not on the left margin of the screen, the smaller neighbor overlaps the input drawing, rather than being on the side.

(define thingy
 (drawing-hshift 
  (drawing-vshift
   (drawing-scale
    (drawing-group
     (drawing-recolor drawing-unit-square "black")
     (drawing-recolor drawing-unit-circle "red"))
    80)
   60)
  100))

(image-show (drawing->image thingy 200 100))

(image-show (drawing->image (add-smaller-neighbor thingy) 200 100))

Why do we have this problem? Because drawing-scale scales everything - not just the shape (or shapes), but also the left and top offset.

How do we solve the problem? There are a variety of options. Here are two. You might choose to temporarily shift the drawing back to the left margin and then shift the pair back after making the neighbor. If that's too much effort, you can come up with a better formula for how much to shift the right neighbor. (The math isn't too hard.)

It will be easiest if we break the problem down into two parts: Making the right neighbor and adding it to the original drawing.

Once we know how to make a right neighbor, adding it is easy.

(define add-smaller-right-neighbor
  (lambda (drawing)
    (drawing-group drawing (smaller-right-neighbor drawing))))

Your goal is therefore to write smaller-right-neighbor. To help you in this endeavor, here's some documentation.

;;; Procedure:
;;;   smaller-right-neighbor
;;; Parameters:
;;;   drawing, a drawing
;;; Purpose:
;;;   Create a smaller version of drawing, situated immediately to the
;;;   right of drawing.
;;; Produces:
;;;   neighbor, a drawing
;;; Preconditions:
;;;   (drawing-width drawing) > 0
;;;   (drawing-height drawing) > 0
;;; Postconditions:
;;;   (drawing-width neighbor) = (* 0.75 (drawing-width drawing))
;;;   (drawing-height neighbor) = (* 0.75 (drawing-height drawing))
;;;   (drawing-top neighbor) = (drawing-top drawing)
;;;   (drawing-left neighbor) = (drawing-right drawing)
;;;   The colors and shapes of neighbor are essentially the same as
;;;     those of drawing.

Implement (that is, define the procedure) smaller-right-neighbor.

Make sure that you test your procedure on a variety of drawings, including some drawings that have their left edge to the left of the image (that is, less than zero).

Problem C.2. Frames

The basic drawings are relatively simple - just solid circles and squares. We've seen ways to expand these into ovals and rectangles. However, sometimes it's nice to be able to draw a “frame” -- effectively a hollow rectangle, one that just has the border, but nothing in the middle. One mechanism for making frames is to overlay a white rectangle over a larger colored rectangle. One might represent this approach in code as follows:

;;; Value:
;;;   alt-unit-square
;;; Type:
;;;   drawing
;;; Contents:
;;;   a unit square with the top-left corner at (0,0)
(define alt-unit-square
  (drawing-hshift (drawing-vshift drawing-unit-square 0.5) 0.5))

;;; Procedure:
;;;   frame
;;; Parameters:
;;;   width, a positive integer
;;;   height, a positive integer
;;;   border-size, an integer
;;;   color, a color
;;; Purpose:
;;;   Create a drawing of a frame - a rectangular shape in which
;;;   the color only appears on the outer border.
;;; Produces:
;;;   rect, a drawing
;;; Preconditions:
;;;   No additional
;;; Postconditions:
;;;   (drawing-width rect) = width
;;;   (drawing-height rect) = height
;;;   (drawing-left rect) = 0
;;;   (drawing-top rect) = 0
;;;   When rendered, the outside edge of the shape is color, that
;;;     edge is border-size thick, and the center is uncolored.
(define frame
  (lambda (width height border-size color)
    (drawing-group
     ; The colored rectangle
     (drawing-hscale 
      (drawing-vscale 
       (drawing-recolor alt-unit-square color)
       height) 
      width)
     ; An inner white rectangle
     (drawing-hshift
      (drawing-vshift
       (drawing-hscale
        (drawing-vscale
         (drawing-recolor alt-unit-square "white")
         (- height (* 2 border-size)))
        (- width (* 2 border-size)))
       border-size)
      border-size))))

A disadvantage of this approach is that the frame isn't really hollow. If we put it on top of another drawing, it obscures the drawing. For example, suppose we want to overlay a thin black frame over a thick blue frame, with a goal of the following image:

But if we put the thin black frame on top, we get the following:

(drawing-group (frame 50 50 10 "blue") (frame 100 100 5 "black"))

And if we put the blue frame on top, we get the following:

(drawing-group (frame 100 100 5 "black") (frame 50 50 10 "blue"))

Rewrite frame so that it generates a frame that does not obscure any drawings that appear in the middle. (You'll need to come up with an approach other than putting white in the middle.)

Problem C.3. Frames, Revisited

Another issue with the frame procedure from the previous problem is that all the frames have their top-left corner at (0,0). What if we want the frame elsewhere?

Implement (define) the following procedure.

;;; Procedure:
;;;   centered-frame
;;; Parameters:
;;;   width, an integer
;;;   height, an integer
;;;   border-size, an integer
;;;   x, an integer
;;;   y, an integer
;;; Purpose:
;;;   Create a frame of the given width and height centered at (x,y)

You need not base your solution on your solution to the previous problem. In particular, if you find it easier, you can just use the technique of “overlay a white rectangle on a colored rectangle”.

Note that our documentation does not include a parameter for the color. You can feel free to add one or to leave the frame black.

Part D: GIMP Instructions

Problem D.1. Rethinking Frames

In Part C, you explored instructions using drawings as values to create frames. Let's revisit that problem using the GIMP Tools.

The following code draws a simple brown frame with a border of 5 around a 40x30 space on an image called canvas (image 11, in this session), with the top-left corner of the space at (100,80)

> (context-set-fgcolor! "brown")
()
> (image-select-rectangle! canvas REPLACE 95 75 50 40)
11
> (image-select-rectangle! canvas SUBTRACT 100 80 40 30)
11
> (image-fill! canvas)
> (image-select-nothing! canvas)
11

Define a procedure, (image-draw-frame! image left top width height frame-width), that generalizes this code.

Note that our description does not include a parameter for the color. You can feel free to add one or to make the frame brown.

Note that our description uses the top-left corner of the space as an input, rather than the top-left corner of the frame. You can feel free to implement the procedure either way, as long as you make it clear what you're trying to do.

Problem D.2. Four-Paned Window Frames

The brown frame above got us thinking about window frames. And while many window frames are just rectangles, others break their interior up into four panes.

Write a procedure, image-draw-four-paned-window! that draws a four-paned window. In addition to the parameters above, this procedure should take as a parameter the width/height of the crossbar that separates the four panes. (That is, it's the width of the vertical piece in the crossbar and the height of the horizontal piece in the crossbar.)

As in the code for the previous problem, you should ensure that anything that would appear behind the “panes” of the window is left unchanged.

Some questions and answers

Here we will post answers to questions of general interest. Please check here before emailing your questions!

General questions

Question: What is a general question?

Answer: A question that is about the exam in general, not a particular problem.

Question: Do we always have to write the six P's, or only when it's specified?

Answer: Only when it's specified.

Question: Why do you use quotation marks in the European style rather than the American style?

Answer: Because we find it more accurate. You'll notice that many programmers (or at least hackers) prefer European style.

Question: I note that you occasionally have lists that lack a terminal “and”. Isn't that a grammatical error?

Answer: No, it's an accepted style. (It's not a common style, but it's accepted.)

Question: How much code do we have to turn in for examples? For example, in Problem C.1, I've created some drawings for my experiments. Do I need to include the code for those drawings?

Answer: You need to include enough for me to replicate your example. So, in this case, you'll need to include the definitions of the drawings.

Question: At times, it's useful to write a few procedures to answer a question rather than a single procedure. Are you okay with multiple procedures or would you prefer that I combine everything into a single procedure?

Answer: If you find that multiple procedures are clearer, then it's fine to use multiple procedures. Make sure to choose clear names for the helper procedures and the parameters to those procedures.

Problem A.1

Question: What does it mean to “cause the procedure to crash”?

Answer: The procedure “crashes” if it results in an error or otherwise fails to evaluate completely.

Question: Do we need to rewrite the code for the procedure?

Answer: No, just the preconditions.

Problem A.2

Question: Can you help me to understand this problem better?

Answer: The name “gcd” may be vague. So, while a client may understand it to mean “greatest common divisor”, the implementer may understand it to mean “Grinnell College divisor”. Hence, the implementer will only try to meet the postconditions. And, in doing so, may not achieve some assumptions that the client has. Your goal is to identify a way to meet those postconditions while failing to meet the implicit client expectations.

Problem C.1

Question: Does smaller-right-neighbor just have to work with thingy or with any drawing?

Answer: It should work with any drawing.

Problem C.3

Question: What happened to the color parameter?

Answer: We forgot to include it. (See the errata.) You can choose to include it or to elide it.

Problem D.1

Question: Why isn't there a parameter for the color?

Answer: We forgot to include it. (See the errata.) You can choose to include it or to elide it.

Problem D.2

Question: Do you have any suggestions on this problem?

Answer: You should be able to do most of the work with context-set-fgcolor!, image-select-rectangle!, and image-fill!.

Errata

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

Update: There are now five points of extra credit for everyone. Thank your classmates!

The sentence that begins “we will limit” should begin “We will limit”. [TB & DMR, 1 point]
We don't have a faculty member named Samuel A. Rebelsky John David Stone. [WBC, 1 point]
“You might to” should be “You might choose to” or “You might”. [SZ, 1 point]
C.3 and D.1 imply a color as a parameter, but do not include that in the parameter list. [ELB & CAG, 1 point]
“Follows” was misspelled as “folows” in Problem C.2. [MDH, 1 point]

Citations

Many 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 group projects, or based upon prior examinations, so precise credit is 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.