Exam 1: Scheme and Image Basics

Assigned: Wednesday, 16 September 2009

Due: Beginning of class, Wednesday, 23 September 2009

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 80 points on this exam.

I 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. Since I worry about the amount of time my exams take, I 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, I 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 the other members of your group. 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, 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 the exam.” 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 (that's me) or Professor Weinman.

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.

In many problems, I ask you to write code. Unless I specify otherwise in a problem, you should write working code and include examples that show that you've tested the code. Do not include images; I should be able to regenerate those.

Unless I 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. Since I 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. I will limit that form of extra credit to five points.

I will give partial credit for partially correct answers. I am 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 (before 10 p.m. and after 8 a.m.), feel free to try to call me in the office (269-4410) or at home (236-7445).

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: Bounding and Averaging Measurements

Topics: Numbers, Numeric Operations, Procedures

Problem 1: Bounding Values

As you may recall from the lab on numeric values, the following expression had an “interesting” effect on val, provided lower and upper were already defined.

> (define bounded-val (min (max val lower) upper))

A typical description of this code is that “bounded-val is a ‘bounded’ version of val. That is, if val is larger than upper, bounded-val is capped at the value of upper and if val is smaller than lower, bounded-val is capped at lower.”

Turn this expression into a procedure, (bound val lower upper). This procedure should have the effect described above. That is, if val is greater than upper, bound should return upper and if val is less than lower, bound should return lower.

You may assume that upper is at least as large as lower.

Problem 2: Bounding Particular Measurements

A typical use of bounding is to keep measurements in a particular range. Suppose we are measuring the blue component of a color. As you know, the blue component of a color cannot be less than 0 or more than 255.

Write a procedure, (bound-blue bc) that takes a potential blue component value as input, and returns that value as bounded below by 0 and above by 255. In writing this procedure, you must call the bound procedure you wrote earlier.

How does one measure the blue component of a color? Ideally, by using some cool optical sensors. Of course, optical sensors are expensive, and may be affected by ambient light. Hence, we more frequently just “eyeball it”, as in “Hey, Emerson, how much blue do you think is in this color?”

Problem 3: Improving Inaccurate Measurements

Many of the ways we estimate blue components (certainly “eyeballing it”, but even using some optical instruments) are, unfortunately, not very accurate. We might get a better estimate by taking multiple measurements (e.g., by asking seven people to estimate the blue component), throw out the lowest estimate and the highest estimate, and then average the remaining estimates.

Write a procedure, (estimate-blue m1 m2 m3 m4 m5 m6 m7), that implements this technique.

Do not call bound-blue in writing estimate-blue.

Problem 4: Combining Our Techniques

4. The Morgan & Parker consulting company has suggested combining bound-blue and estimate-blue to get a better estimate. However, each suggests a different combination.

(define morgan-estimate
  (lambda (m1 m2 m3 m4 m5 m6 m7)
    (estimate-blue (bound-blue m1)
                   (bound-blue m2)
                   (bound-blue m3)
                   (bound-blue m4)
                   (bound-blue m5)
                   (bound-blue m6)
                   (bound-blue m7))))

(define parker-estimate
  (lambda (m1 m2 m3 m4 m5 m6 m7)
    (bound-blue (estimate-blue m1 m2 m3 m4 m5 m6 m7))))

a. Are there any values of m1 .. m7 for which these two procedures return different values? If so, give one such set of values. If not, explain why not.

b. Are there any values of m1 .. m7 for which these two procedures return the same value? If so, give one such set of values. If not, explain why not.

c. Which of the two procedures do you prefer, and why?

Part B: Scripting the GIMP Tools

Problem 5: Drawing Simple Windows

Topics: Procedures, GIMP tools, generalization.

The following code draws a simple window of size 40x30 with a brown outer frame of width 5 on an image called canvas (image 11, in this session), with the top-left corner of the window 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 called (image-draw-window! image left top width height frame-width), that generalizes the code above.

Problem 6: Drawing More Complex Windows

The windows that we drew in the previous problem are relatively simple. More often, in representational drawings, we like four-paned windows.

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.

Part C: Drawings as Values

Problem 7: Drawing a Flag, Take One

Topics: Drawings as values, Code reading, Debugging, Paradigms

The following code is intended to draw the flag of Sweden, a yellow cross on a blue field. (See Flags of the World - Sweden.)

This is not actually what it does. Fix it.

(define field 
  (drawing-vscale 
   (drawing-hscale drawing-unit-square 32)
   20))

(drawing-recolor field "blue")

(define vcross (drawing-hshift 
                (drawing-hscale 
                 (drawing-vscale drawing-unit-square 20) 
                 4) 
                -4))
(define hcross (drawing-hscale 
                (drawing-vscale drawing-unit-square 4) 
                32))

(drawing-recolor (drawing-group vcross hcross) "yellow")

(define se-flag (drawing-group field vcross hcross))

(drawing-hshift se-flag 16)
(drawing-vshift se-flag 10)

(image-show (drawing->image se-flag 32 20))

Note: You should strive to make your corrections as concise as possible, doing your best to avoid introducing any additional variables.

Problem 8: Drawing a Flag, Take Two

Topics: Drawings as values, Conciseness.

Now that you've drawn the flag of Sweden, consider the flag of Colombia: two horizontal stripes of equal size, colored red and blue, below one horizontal stripe twice as tall, colored gold. (See Flags of the World - Colombia.) Write a program (that is, a sequence of expressions) that (a) uses drawings-as-values to define co-flag as a drawing of the flag of Colombia and (b) renders that flag in a new image. Make your code as concise as you can.

Problem 9: Drawing Diagonals

Topics: Drawings as values, procedures.

a. Write a procedure, (diagonal drawing) that creates a compound drawing with four copies of drawing (one unshifted, one shifted right and down once, one shifted right and down twice, and one shifted right and down thrice). This new, compound drawing should be scaled by 25%, so that it is the same width and height as the original.

b. Using diagonal, build a "sawtooth" (a series of two diagonals) of some interesting drawing, such as the Swedish flag from Problem 7.

For example:

(image-show (drawing->image flag 32 20))
(image-show (drawing->image (diagonal flag) 32 20))
(image-show (drawing->image sawtooth 64 20))

Part D: RGB Colors

Problem 10: Combining Colors

Topics: RGB colors, Procedures, Numbers

Sometimes we want to take two RGB colors and blend them in some way. For example, we might blend colors “smoothly” by taking an average over their components. At other times we may want more drastic combinations. For example, we might want to use only the more intense or the less intense of each color component.

Write a procedure, (rgb-min-blend color1 color2), that takes two RGB colors, and creates a new RGB color where each component (red, green, and blue) is the smaller of the corresponding component of the two colors.

> (rgb->rgb-list (rgb-min-blend (color-name->rgb "white") (color-name->rgb "black")))
(0 0 0)
> (color->rgb-list "mistyrose")
(255 228 225)
> (color->rgb-list "lemonchiffon")
(255 250 205)
> (rgb->rgb-list (rgb-min-blend (color-name->rgb "mistyrose") (color-name->rgb "lemonchiffon")))
(255 228 205)
> (color->rgb-list "springgreen")
(0 255 127)
> (color->rgb-list "bisque")
(255 228 196)
> (rgb->rgb-list (rgb-min-blend (color-name->rgb "springgreen") (color-name->rgb "bisque")))
(0 228 127)

Some questions and answers

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

Miscellaneous

Question: Suppose we find an error of spelling, grammar, or logic in the question and answer section or the errata. Does that count for points in the errata section?

Answer: Past history suggests that when Sam Rebelsky is involved in writing answers or errata, giving you credit for mistakes there leads to a spiraling increase in errata. So, no credit for mistakes found in these sections. (We still appreciate corrections to mistakes in these sections, but we won't give you credit for them.)

Question: For the printed version, do you want each problem on a separate page?

Answer: No. That would be a waste of paper. Just put them in sequence with a bit of whitespace between them.

Question: What do you want on the cover page?

Answer: Your name. The statements (signed). The date. Preferably the course name and exam number. Anything else you deem pertinent.

Part A

Question: You keep talking about eyeballing how much blue is in an image. What exactly are you talking about doing in terms of the program?

Answer: All this text is doing is setting up a little motivation for the problem. In general, we have measurements of a quantity (in this case, "blueness"), and we want to cap these measurements (problem 2), compute a single, summary estimate value of multiple measurements (problem 3), or combine these techniques (problem 4).

Question: Can we assume that people guessing the blue component will guess between 0 and 255?

Answer: Evidence suggests that people rarely follow instructions. Hence, although the blue component should be between 0 and 255, you will find that some folks pick a number higher than 255 and others pick a number lower than 0. (Even if you use an instrument to get the component, there is a chance it will give a number outside the expected range unless it has a procedure like rgb-bound built into the circuitry.)

Problem 1

Question: The first question looks to me like it requires if statements or at least some sort of indefinite loop, and I at least haven't noticed anything like that in the readings. Am I wrong about this?

Answer: The given define statement accomplishes the task for particular values of val, lower, and upper. You are to transform this into a procedure, no tests, conditionals, or loops are required.

Problem 3

Question: I've found some numbers for which I get an answer that is rational, but not an integer. Since RGB colors are supposed to be integers, what should I do?

Answer: You know a variety of procedures for converting rational numbers to nearby integers. Choose one.

Question: Does it matter whether estimate-blue provides an exact integer?

Answer: Given the context of the problem, it would be better to have an extact integer. However, it is acceptable if your result is inexact.

Part B

Problem 5

Question: Shouldn't color should be one of the parameters in order to do set the foreground color for the window?

Answer: Color is one of the possible things we could have generalized, but, as with all procedures, there are some things you get to control and some you don't. Thus, we have asserted that the position/size gets to be general, but the color is not. (It is always brown).

Question: When you say “top-left corner of the window”, do you mean the inside corner or the outside corner? I ask because in your example the inside corner is at (100,80), but the outside is at (95,75). I assume this would indicate that you do mean the inside corner.

Answer: “[T]op-left corner of the window” means the top left corner of the glass, rather than the actual frame. So this is the inside corner of the frame, but the top left corner of the window pane.

Problem 6

Question: Does the pane-dividing-thing have to be in one piece?

Answer: I'm not sure exactly what you mean by “one piece”. It would be way cool if you could simply select one region that corresponds to the window frame, and then fill it. However, if you find it easier to do multiple selections, that's fine, provided that drawing the window does not affect the parts of the image that appear behind the panes.

Question: What is the relationship of the size of the crossbar in the four-pane window to the size of the outer frame?

Answer: The size of the crossbar pieces (width of vertical piece, height of horizontal piece) should be specified as a parameter to the procedure.

Question: Can I use two extra parameters, one for the width of the vertical piece in the crossbar and one for the height of the horizontal piece in the crossbar?

Answer: Yes.

Question: Do the four panes have to be the same size?

Answer: Yes.

Question: Are we allowed to call the image-draw-window! procedure that we wrote in problem 5?

Answer: Yes.

Question: Do I have to use crossbar-width and crossbar-height as parameters? If I can make a procedure that draws four paned window without using both parameters, can I not use them?

Answer: You may take only one parameter to specify both, but your procedure should allow the caller to specify a crossbar "thickness" separately from the frame width.

Part C

Problem 7

Question: Are we allowed to change the numbers?

Answer: Yes, if you consider it appropriate to do so.

Problem 8

Question: What do you mean by “[render] that flag in a new image”?

Answer: Something like (image-show (drawing->image ...)).

Question: What do you mean when you say we should use “drawings-as-values”?

Answer: We mean that you should use the procedures of the form drawing-... and not the GIMP tools procedures, such as image-select-rectangle!.

Problem 9

Question: Shouldn't we need a canvas width and canvas height as parameters to diagonal?

Answer: No. The diagonal procedure is intended to create a drawing, not an image. The resulting drawing should be the same width and height as the original drawing. You can determine those with drawing-width and drawing-height, but scaling by 25% should suffice.

Question: I'm sure that my flags are done correctly. However, when I make the diagonals and end up with very small flags, they don't always look quite right. Why?

Answer: When the flags are small, you're likely to end up with components of the drawing that are real but not integral. (E.g., you might have a shift of 2.5 or a width of 17.2.) When rendered, such components are approximated. The approximation may therefore affect the quality of the flag. It is okay if the flags don't look quite right when scaled.

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.

In problem 1, “These procedure” should be “This procedure”. [DMN & JD, 1 point]
In problem 4, my appears instead of m7. [JD, 1 point]
In problem 9, there should be an unshifted version of the drawing rather than one shift right and down four times. [WM, 1 point]
It's “Colombia” not “Columbia”. [MSH, 1 point]
Extra comma in “Some of the ways we estimate blue components ([...]), are, unfortunately, not very accurate”. [ER, 1 point]