Exam 2: Color and Control

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 Sunday evening before the exam is due. The prologue is intended to help you get started thinking about the examination. The prologue is required. Failure to fill in the prologue by the designated time will incur a penalty of five points on the examination.

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 eight problems on this examination. Each problem is worth the same number of points, except for problem 1, which is worth 0 points. Although each remaining 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 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” on the cover sheet of the examination and you will earn at least the equivalent of 70% on this exam, provided you recorded the time spent on each problem, filled in the prologue by the specified deadline, filled in the epilogue, and arranged for a meeting with me within one week of receiving your graded exam. You may count the time you spend on the prologue toward those five hours, but not the time you spend on the epilogue.. 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 and recording time are not usually applied in the second situation, but penalties (e.g., for failing to number pages) usually are.

You should not count time reviewing readings, laboratories, or assignments 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 write, 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, physically and electronically.

For the physical copy, you must write all of your answers using the computer, print them out, number the pages, staple them together (except for the cover sheet), and hand me the printed copy. For your benefit and for ours, we are doing blind grading on this examination, so you have been assigned a number to use on your exam. Please make sure that your number appears at the top of every page. You should turn in a separate cover sheet along with your stapled and printed answers. The cover sheet should include (1) the two hand-written academic honesty statements (individually signed and dated, if it is appropriate for you to sign each), (2) your name, and (3) your assigned number. If you choose to invoke the “there's more to life than computer science” option, then you must indicate that option on the cover sheet, and you should indicate it only on the cover sheet.

The code and comments in your printed copy must use a fixed-width (a.k.a., monospaced or fixed-pitch) font; depending on what platform you use, viable candidates include Monospace, Courier, Courier New, Monaco, DejaVu Sans Mono, Free Mono, Liberation Mono, and Lucida Sans Typewriter. Failure to format your code with a monospace font will result in a penalty. You may read the instructions on printing for more details on how to create readable output.

You must also submit the code for your examination at http://bit.ly/151-2015S-exam2. Ideally, you would put all of the code for the exam in a single Racket file. However, if you have created separate files for the separate parts of the exam, you can just paste them one after another when you submit, provided you put a clear separator, such as ; PROBLEM 2, between sections.

In both cases (physical and electronic), you should put your answers in the same order as the problems. Failure to 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. Thursday, your physical copy will be submitted in class on Friday. 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 informally (by looking at what value you get for various inputs) or formally (by using the Rackunit testing framework). In addition to the examples provided in the exam, you should also provide additional examples. 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 Ps. If you write helper procedures (and it's often a good idea to write helper procedures), you need only document those with a sentence or two that gives their purpose. (We would prefer that you use the 6P style, but won't require it.)

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 in the preliminaries and problems 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 classes the week the exam is due to discuss any general questions you have on the exam.

THIS PROBLEM IS NO LONGER REQUIRED!

Topics: Integer-encoded RGB colors, predicates

As Matt Kluber, our colleague in studio art, notes, there are a lot of different colors available in the RGB spectrum (2^24, or about 16 million). It turns out that many of us lack the visual acuity to distinguish colors with similar red, green, and blue components.

Let's define a metric for similarity of RGB colors. In order to say whether or not two colors are similar, we should know the “distance” between those colors. You may know that for two points on the plane, the distance between those two points is the plane (x1,y1) and (x2,y2) is the square root of the sum of the squares of the differences between those points. In Scheme, we'd write that as follows:

(define plane-distance
  (lambda (x1 y1 x2 y2)
    (sqrt (+ (square (- x1 x2)) (square (- y1 y2))))))

Write, but do not document, a procedure, (irgb-close? irgb1 irgb2 closeness-metric) that takes two colors and a real number as parameters and returns true (#t) if the two colors have a distance less than the number, and returns false (#f) otherwise.

> (irgb-close? (irgb 0 0 0) (irgb 0 0 0) 10)
#t
> (irgb-close? (irgb 10 10 10) (irgb 25 25 25) 16)
#f
> (irgb-close? (irgb 10 25 10) (irgb 25 10 25) 32)
#t
> (irgb-close? (irgb 100 100 100) (irgb 100 100 115) 16)
#t
> (irgb-close? (irgb 100 100 100) (irgb 100 100 115) 14)
#f

Topics: Integer-encoded RGB colors, code reading, conditionals, local bindings

In printing, and in some forms of op-art from the 1960's, one takes an image developed in a much larger color space and represents it using a much smaller color space, perhaps with as few as two colors. The following procedure takes an image and three colors, and makes a new version of the image by replacing each color in the image by the closest of those three colors.

(define tricolor
  (lambda (image color1 color2 color3)
    (image-variant 
     image
     (lambda (color)
        (let ([distance1 
               (sqrt (+ (square (- (irgb-red color) 
                                   (irgb-red (color->irgb color1))))
                        (square (- (irgb-green color) 
                                   (irgb-green (color->irgb color1))))
                        (square (- (irgb-blue color) 
                                   (irgb-blue (color->irgb color1))))))]
              [distance2
               (sqrt (+ (square (- (irgb-red color) 
                                   (irgb-red (color->irgb color2))))
                        (square (- (irgb-green color) 
                                   (irgb-green (color->irgb color2))))
                        (square (- (irgb-blue color) 
                                   (irgb-blue (color->irgb color2))))))]
              [distance3
               (sqrt (+ (square (- (irgb-red color) 
                                   (irgb-red (color->irgb color3))))
                        (square (- (irgb-green color) 
                                   (irgb-green (color->irgb color3))))
                        (square (- (irgb-blue color) 
                                   (irgb-blue (color->irgb color3))))))])
          (cond 
            [(= distance1 (min distance1 distance2 distance3))
             (color->irgb color1)]
            [(= distance2 (min distance1 distance2 distance3))
             (color->irgb color2)]
            [else
             (color->irgb color3)]))))))

As you may have noted, there are many problems with the definition of tricolor. It is repetitious in that we see similar code written again and again and again. It is also inefficient in that we recompute values again and again and again.

You can see the effects of these redundancies when we try to run it even on a small image.

> (time (tricolor (image-new 10 10) "red" "orange" "blue"))
cpu time: 312 real time: 6217 gc time: 0
1
> (define sample 
    (image-show (image-compute 
                 (lambda (col row)
                   (irgb (mod (* col 29) 255)
                         (mod (* (+ col row) 17) 255)
                         (mod (* row 31) 255)))
                 10 10)))
2
> (time (tricolor sample "black" "blue" "red"))
cpu time: 320 real time: 6255 gc time: 0
3
> (time (tricolor (image-new 20 20) "black" "white" "grey"))
cpu time: 1248 real time: 23280 gc time: 0
4

If even a 20x20 image takes us about 24 seconds, it will take an interminable amount of time on our kitten, which is 200x300.

Rewrite tricolor to eliminate redundancies. Your first priority should be to eliminate repeated computation; once the code computes a value once, it should not have to compute it again. Your second priority should be to eliminate repeated code; if there are two pieces of code that look similar, find a way to make them a single piece of code. You will find that local bindings with let and let* will help with both activities. Your third priority will be to make it concise and clear.

The most important set of changes will make a huge improvement in the running time. The remainder will primarily affect concision, elegance, and readability. Here's an example showing the running time after making one important change. (We include the example to show just how significant the change is.)

> (time (tricolor (image-new 20 20) "black" "white" "grey"))
cpu time: 8 real time: 46 gc time: 0
5
> (time (tricolor kitten "red" "black" "yellow"))
cpu time: 548 real time: 960 gc time: 0
7

In this problem, you are updating an existing procedure. Hence, you do not need to write the 6P-style documentation.

Topics: Computing images, color blends, computing circles, conditionals

In the reading on building images from functions, you learned how to compute an image of circles using the distance of each image pixel from a center point. We can use that idea for not only circles, but also rings. For a ring, rather than using a color for all points within a given radius, we use a color for all points between two given radii.

In the lab on computing images, you figured out how to generalize a linear blend from one color component to another. In particular, you saw how to make a horizontal blue blend from any amount of blue to any other amount of blue.

In this problem, we will combine those two ideas.

Write, but do not document, a procedure, (radial-red-blended-ring inner-radius outer-radius initial-red final-red), that draws a 200x200 image with a ring of the specified inner radius and outer radius, centered at (100,100). The color at the inner radius should be (irgb initial-red 0 0). The color at the outer radius should be (irgb final-red 0 0). There should be a smooth blend within the ring. Pixels inside the ring should be colored white. Pixels outside the ring should be colored grey.

(radial-red-blended-ring 50 100 0 255)	(radial-red-blended-ring 25 90 192 64)	(radial-red-blended-ring 105 120 128 255)

Hint: Your computation of the red 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 inner-radius to outer-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 red component.

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

Topics: Core list operations, documentation.

You know that car and cdr are two basic operations for extracting the first element of a list and all but the first element of a list. Surprisingly, Scheme doesn't have procedures for getting the last and all but the last element from a list. (Okay, it's not so surprising: The underlying implementation of lists makes implementing car and cdr quick and straightforward. But the implementation makes getting the last element much less efficient.) But that's okay, we can implement them. Let's say we want to write two procedures, rac, which extracts the last element of a list, and rdc, which extracts a list containing all but the last element of the list.

For example,

> (rac (list 3 1 4))
4
> (rac (iota 20))
19
> (rdc (list 3 1 4))
'(3 1)
> (rdc (iota 20))
'(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18)

Write 6P-style documentation for rdc. Make sure that you specify the preconditions as carefully as possible. What does the input have to look like? Will the procedures accept empty lists? Singleton lists? Long lists?

Make equally sure that you specify the postconditions carefully. You want to make sure that someone who is unclear on the purpose does not accidentally write a procedure that sometimes returns the wrong value (e.g., the empty list or the cdr).

Topics: Core list operations, concision, higher-order procedures (e.g., composition, sectioning)

Implement rac and rdc as concisely as you can. You should be able to implement rac with five words, including define and rac, plus a few parentheses. You should be able to implement rdc almost as concisely.

You do not need to document rac. You should have already documented rdc in the previous problem.

Note: You may not use the alternate mechanism of define procedures of the form (define (rac lst) ...), but you may find other ways to avoid writing lambda.

Note: You will receive most of the credit for a correct solution, even if it is not as concise as it is possible.

Topics: Colors, unit testing

Consider the procedure (irgb-classify icolor), that takes integer-encoded RGB color as input and returns the symbol 'reddish when the red component is larger than both the green and blue components, 'greenish when the green component is larger than both the red and blue components, 'blueish when the blue component is larger than both the red and green components, and 'otherish when none of those conditions holds.

> (irgb-classify (irgb 255 0 0))
'reddish
> (irgb-classify (irgb 0 32 0))
'greenish
> (irgb-classify (irgb 10 15 30))
'blueish
> (irgb-classify (irgb 128 128 128))
'otherish

Write a comprehensive test suite for irgb-classify.

Since you'll need something to test, here's an incorrect implementation. Amazingly, it gives the right answers for all of the examples above.

(define irgb-classify
  (lambda (icolor)
    (if (= (irgb-red icolor) (irgb-blue icolor) (irgb-green icolor))
        'otherish
        (if (> (irgb-red icolor) 128)
            'reddish
            (if (> (irgb-green icolor) (irgb-blue icolor))
                'greenish
                'blueish)))))

Your tests should not just catch the many errors in this implementation, but should be designed to catch errors in any implementation.

Note: As is usually the case in testing, you should think about a variety of cases. Consider different relationships between the red, green, and blue components and make sure you test them all. About a dozen should suffice, provided they are different.

Note: I am likely to run your tests on incorrect code that reflects some of the errors that novices are likely to make, and will expect you to catch errors in the incorrect code. I am unlikely to run your tests on maliciously designed code, but it would be nice if your tests also caught errors in such code if I did.

Note: For testing, you need to pick concrete values to test. For example, here's one of the checks I might do for a color in which blue dominates.

(check-equal? (irgb-classify (irgb 190 190 200)) 
              'blueish
              "blue dominates, red and green are equal and large")

Topics: Colors, conditionals

Correctly implement the irgb-classify procedure described in the prior problem. You need not document irgb-classify.

Topics: Lists, concision, higher-order procedures (map).

In a recent assignment, you wrote a procedure, (image-sample image x-coords y-coords), that gets the color at each (x,y) pair, makes a shape in that color, and then renders the shape at the same location in a new image.

As we saw in class, we can achieve interesting effects by automatically generating long lists of x and y coordinates. There are a variety of lists that are possible to generate. Solve one of the following two problems in generating coordinates.

> (zigzag-y-coords 20 20)
'(19 16 13 10 7 4 1 2 5 8 11 14 17 18 15 12 9 6 3 0)

>  (image-sample kitten 
                 (iota (image-width kitten)) 
                 (zigzag-y-coords (image-width kitten) 
                                  (image-height kitten)))

> (sinusoidal-y-coords 20 5)
'(2
  1.381966011250105
  0.8244294954150537
  0.3819660112501051
  0.09788696740969294
  0.0
  0.09788696740969272
  0.3819660112501051
  0.8244294954150535
  1.381966011250105
  1.9999999999999998
  2.6180339887498953
  3.175570504584946
  3.618033988749895
  3.9021130325903073
  4.0
  3.9021130325903073
  3.618033988749895
  3.1755705045849467
  2.6180339887498953)
> (map (o inexact->exact round) (sinusoidal-y-coords 20 100))
'(50 34 20 9 2 0 2 9 20 34 49 65 79 90 97 99 97 90 79 65)

>  (image-sample kitten 
                 (iota (image-width kitten)) 
                 (sinusoidal-y-coords (image-width kitten) 
                                      (image-height kitten)))