Exam 1: Scheme and Image Basics


Assigned: Wednesday, 5 February 2014

Due: The due dates for various tasks are as follows.

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.

This examination has an optional prologue due by the Friday before the exam is due. It is intended to help you get started thinking about the examination. While the prologue is optional, if you intend to invoke the “there's more to life” option (see below), you must submit the prologue by the specified deadline.

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 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 a 70 on this exam, provided you (1) submitted the prologue by the specified deadline, and (2a) show evidence of serious effort on at least six of the problems or (2b) come to talk to me within a week of submitting the exam about the difficulties you had. 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 out of 100 or (2) 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. 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.

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.

  1. I have neither received nor given inappropriate assistance on this examination.
  2. 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 Weinman.

Exams can be stressful. Don't let the stress of the exam lead you to make decisions that you will later regret.

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 with the subject CSC 151-01 Exam 1. 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.

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 (7 a.m. - 6 p.m.), feel free to try to call me (269-9812).

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: Thinking About Time

Topics: Documentation, unit testing, writing procedures, numeric values

Two ways of representing the time are the familiar twelve hour format (e.g., 11:23 a.m., 1:23 p.m.) or the less common twenty-four hour format (e.g. 1123h, 1323h) commonly used in the military (which is why this latter format is sometimes referred to as "military time").

In this section, we will think about how to convert the hour portion of such twenty-four hour military time into its corresponding "civilian" hour. You will document, test, and finally write the procedure (military->civilian hours). For example:

  > (military->civilian 10)
  10
  > (military->civilian 12)
  12
  > (military->civilian 13)
  1
  > (military->civilian 20)
  8
  > (military->civilian 23)
  11
  > (military->civilian 0)
  12

Problem 1: Document military->civilian

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 military->civilian as described above.

Problem 2: Test military->civilian

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.

Write a test suite for the procedure military->civilian.

Problem 3: Implement military->civilian

Write the procedure (military->civilian hours) as described above.

Part B: Moving Drawings

Topics: Drawings as values, documentation, unit testing, writing procedures

It is often useful to have drawings whose top is at 0 and whose left is at 0. Why? Such drawings will be rendered in a way we would expect. As we've seen in some code explorations, it is also easier to make neighbors or scaled versions of drawings with those characteristics.

In this part of the examination, you will explore a procedure, (top-left drawing), that makes a copy of the given drawing at the top-left corner, with left at 0 and top at 0.

Problem 4: Document top-left

Document the procedure top-left using the 6Ps.

Problem 5: Test top-left

a. Write a test suite for the procedure top-left.

b. Which postconditions are you able to test? Which (if any) do you find difficult to test directly? Why?

Problem 6: Implement top-left

Implement the procedure (top-left drawing).

Part C: Miscellaneous

Problem 7: Cleaning Code

Topics: Numeric values, code reading, documentation

Consider the following procedure.

(define f (lambda (a b c) (min (max (min a b) c) (max (min b c) a))))

Reformat the procedure (i.e., by adding new lines) so that its operations are easier to understand. Next, try calling it with a variety of parameters. Your goal is to discover what parameters f accepts and what it does with those parameters.

Then rewrite the procedure definition as follows:

  • Format the code more clearly (i.e., according to our Scheme conventions).
  • Give each parameter a meaningful name that (at least) reflects its type.
  • Give the procedure a meaningful name.
  • Document the procedure using the 6Ps.
  • Add a seventh P, Process, to describe briefly the method (algorithm) used to calculate the result.

Problem 8: A Smaller Checkerboard

Topics: Drawings as values, writing procedures

On a recent assignment, you made a traditional eight-by-eight checkerboard. Let's explore a simpler variant of that problem.

Write a procedure, (grid drawing), that takes as input an N-by-M drawing whose top-left corner is at (0,0) and that produces as output a 2N-by-2M drawing with four copies of the original drawing in two rows of two, with the top-left and bottom-right copies recolored to black and the top-right and bottom-left copies recolored to red.

oval
(grid oval)

Problem 9: Adding Circles to Images

Topics: Drawings as values, images, side effects, code design

Many image-manipulation programs provide a simple effect in which we put “tabs” (usually quarter-circles) at the four corners of an image in order to simulate what the picture might look like in a photo album.

For example, assume we start with the following image.

(define kitten (image-load "/home/rebelsky/glimmer/samples/kitten.jpg"))

Adding tabs might give us the following image.

(add-corner-tabs! kitten "black" 50)

Here's a starting set of documentation for the add-corner-tabs! procedure.

;;; Procedure:
;;;   add-corner-tabs!
;;; Parameters:
;;;   image, an image id
;;;   color, a color
;;;   radius, a positive real number
;;; Purpose:
;;;   Add four "tabs" (quarter circles) to each of the four corners
;;;   of the given image.
;;; Produces:
;;;   image, the same image id
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   The image contains four quarter circles centered at the four corners.
;;;   Each quarter circle is in the given color and has the given radius.

How would we go about writing the add-corner-tabs! procedure? We might start by writing a procedure that allows us to put a circle anywhere in the image. We could then use that procedure to put circles at the four corners.

a. Write a procedure, (add-colored-circle! image color radius x y), that adds a colored circle to the given image, centered at the given location, as shown in the following example.

(add-colored-circle! kitten "red" 100 200 300)
(add-colored-circle! kitten "yellow" 20 190 155)

Here's some preliminary 6P-style documentation for that procedure.

;;; Procedure:
;;;   add-colored-circle!
;;; Parameters:
;;;   image, an image id
;;;   color, a color
;;;   radius, a positive real number
;;;   x, a real number
;;;   y, a real number
;;; Purpose:
;;;   Add a colored circle to the given image.
;;; Produces:
;;;   image, same image id
;;; Preconditions:
;;;   The circle fits within the image.  That is,
;;;     (+ x radius) > 0
;;;     (+ y radius) > 0
;;;     (- x radius) < (image-width image)
;;;     (- y radius) < (image-height image)
;;; Postconditions:
;;;   The corresponding image now contains a colored circle at the
;;;     specified location.
;;;   The image is not otherwise modified.

b. Once we've written that procedure, the next step should be easy. Using add-colored-circle!, write a procedure, (add-corner-tabs! image color radius), that adds quarter circles to each of the four corners of the image.

You've seen one example above. Here's a slightly more complex example.

(add-corner-tabs! kitten "black" 50)
(add-corner-tabs! kitten "white" 45)

Problem 10: Annotating Complex Code

Topics: Drawings as values, textual output, code reading, code tracing

As you've started to see, we sometimes achieve complex results by having procedures call other procedures multiple times. Consider the following procedures.

;;; Procedure:
;;;   outlined-circle
;;; Parameters:
;;;   diameter, a real number
;;; Purpose:
;;;   Create an outline of a circle of the given diameter
;;; Produces:
;;;   circle, a drawing
;;; Preconditions:
;;;   diameter > 4
;;; Postconditions:
;;;   When rendered, circle appears as an outline of a circle.
;;;   (drawing-width circle) = diameter
;;;   (drawing-height circle) = diameter
;;;   (drawing-left circle) = 0
;;;   (drawing-top circle) = 0
(define outlined-circle
  (lambda (diameter)
    (hshift-drawing
     (/ diameter 2)
     (vshift-drawing
      (/ diameter 2)
      (drawing-group
       (scale-drawing diameter drawing-unit-circle)
       (scale-drawing (- diameter 2) 
                      (recolor-drawing "white" drawing-unit-circle)))))))

;;; Procedure:
;;;   nest
;;; Parameters:
;;;   egg, a drawing
;;; Purpose:
;;;   Make a new drawing by surrounding four copies of egg
;;;   with a circle.
;;; Produces:
;;;   nested, a drawing
;;; Preconditions:
;;;   (drawing-left egg) = 0
;;;   (drawing-top egg) = 0
;;;   (drawing-width egg) = (drawing-height egg)
;;; Postconditions:
;;;   When rendered, nested has four copies of egg, surrounded by a circle.
;;;   (drawing-width nested) = (* 2 (drawing-width egg))
;;;   (drawing-height nested) = (* 2 (drawing-height egg))
;;;   (drawing-left nested) = 0
;;;   (drawing-top nested) = 0
(define nest
  (lambda (egg)
    (drawing-group
     ; Surrounding circle
     (outlined-circle (* 5/2 (drawing-width egg)))
     ; top
     (hshift-drawing (* 3/4 (drawing-width egg))
                     egg)
     ; left
     (vshift-drawing (* 3/4 (drawing-height egg))
                     egg)
     ; right
     (hshift-drawing (* 3/2 (drawing-width egg))
                     (vshift-drawing (* 3/4 (drawing-height egg))
                                      egg))
     ; bottom
     (hshift-drawing (* 3/4 (drawing-width egg))
                     (vshift-drawing (* 3/2 (drawing-height egg))
                                     egg)))))

We can achieve a fairly interesting image with the following call.

(nest (nest (nest (outlined-circle 15))))

But how do we get so many circles with such little code?

a. Annotate both procedures so that we can better understand what's happening in the construction of the image. That is, add appropriate calls to display so that we can get output like one of the following two examples.

Creating an outlined circle of diameter 15.
Nesting four eggs of width 15.0

b. Having explored the behavior of this code, explain how you might change or improve your solution to the checkerboard problem from assignment 3.

Some Questions and Answers

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

General Questions

What is a general question?
A question that is about the exam in general, not a particular problem.
Do the two classes have the same exam?
Yes, although we format it differently.
Does our exam need to be in the body of the email, or will you accept attachments?
Rebelsky will accept attachments. Weinman does not.
Can we still invoke the “There's more to life” clause if we spend more than five hours on the exam?
Yes. However, we really do recommend that you stop at five hours unless you are very close to finishing. It's not worth your time or stress to spend more effort on the exam. It is, however, worth your time to come talk to us, and perhaps to get a mentor or more help. There's likely some concept you're missing, and we can help figure that out.
What do you mean by “implement”?
Write a procedure or procedures that accomplish the given task.
Do we have to make our code concise?
You should strive for readable and correct code. If you can make it concise, that's a plus, but concision is secondary to readability and correctness. Long or muddled code is likely to lose points, even if it is correct.

Part A

Should I write my procedure to generate an error if a precondition is not met?
While that is nice behavior (something we call a "verified" precondition), we do not yet know generally how to generate errors, so it is acceptable to leave preconditions as specified but "unverified" (meaning they might generate a meaningless result rather than an error message).
I noticed how the military to civilian time clock converter would be so much easier if we knew conditionals, such as an if expression. Is it alright if I use them for my answer even if we haven't done conditionals yet?
No. The problem is intended for a solution without conditionals.
Does this only have to work with whole numbers, or should I make it work for real numbers?
You only have to deal with whole numbers.

Part B

Do we group the new drawing with the original, or just return the new drawing?
The goal is to return only the new drawing.

Problem 8

The result seems to be on a white rectangle. Do we have to include that white rectangle in our result?
No. It's just an artifact of how the drawings are rendered.

Problem 10

What do you mean by “annotate”?
Insert calls to display and newline to show when the procedures are called.
When we write about the effects on our checkerboard code, can we write our answer in Emglish or should we write code?
English is fine.

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

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 written collaboratively, or were themselves 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.

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.


Jerod Weinman

Copyright 2007-2012 Janet Davis, Matthew Kluber, Samuel A. Rebelsky, and Jerod Weinman. (Selected materials copyright by John David Stone and Henry Walker and used by permission.)

This material is based upon work partially supported by the National Science Foundation under Grant No. CCLI-0633090. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial 2.5 License .