Exam 2: Control and Collections


Assigned: Wednesday, 5 March 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 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 2. 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 tell you not to document your procedures, you must write 6P-style documentation for every globally accessible procedure. (Thus, anonymous and local helper procedures are exempted.)

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.

I 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: Simple Transformations

Topics: Integer-encoded RGB colors, testing, conditionals, numeric computation.

A simple, but common, color transformation is to flatten a color by converting each component to one of a few selected values. (e.g., 0, 63, 127, 191, 255).

;;; Procedure:
;;;   irgb-flatten-5
;;; Parameters:
;;;   color, an irgb color
;;; Purpose:
;;;   "flatten" the color, making it one of a small group of similar colors.
;;; Produces:
;;;   flattened, an irgb color
;;; Preconditions:
;;;   [No additional.]
;;; Postconditions:
;;;   All of the components are one of 0, 63, 127, 191, or 255.  
;;;     That is,
;;;       (member? (irgb-red flattened) '(0 63 127 191 255))
;;;       (member? (irgb-green flattened) '(0 63 127 191 255))
;;;       (member? (irgb-blue flattened) '(0 63 127 191 255))
;;;   Each of the components of flattened is near the corresponding
;;;     component in color.  That is.
;;;       (<= (abs (- (irb-red flattened) (irgb-red color))) 32)
;;;       (<= (abs (- (irb-green flattened) (irgb-green color))) 32)
;;;       (<= (abs (- (irb-blue flattened) (irgb-blue color))) 32)

Because we want to do the same thing to each of the three components, it makes sense to write a helper, flatten-component.

;;; Procedure:
;;;   flatten-component-5
;;; Parameters:
;;;   component, an integer
;;; Purpose:
;;;   "flatten" the component to make it one of 0 63 127 191 255
;;; Produces:
;;;   fc, an integer
;;; Preconditions:
;;;   0 <= component < 256
;;; Postconditions:
;;;   fc is one of 0, 63, 127, 191, 255.  That is,
;;;     (member? fc '(0 63 127 191 255))
;;;   fc is close to component.  That is,
;;;     (<= (abs (- fc component)) 32)

Once we've written flatten-component-5, it is relatively easy to write irgb-flatten-5.

(define irgb-flatten-5
  (lambda (color)
    (irgb (flatten-component-5 (irgb-red color))
          (flatten-component-5 (irgb-green color))
          (flatten-component-5 (irgb-blue color)))))

Here is an incorrect implementation of flatten-component-5.

(define flatten-component-5
  (lambda (component)
    (if (< component 128) 0 255)))

You might want to explore what it does with a simple image.

Problem 1: Testing Flatten

Write a test suite for flatten-component-5. You should make sure to test a variety of categories of “normal” cases as well as appropriate “edge” cases.

You'll note that the postconditions of flatten-component-5 are potentially a bit vague. Suppose we had a component with a value of 95. If flatten-component-5 transforms it to 63, we've met both postconditions, because 63 is a member of that list and 95-63 is 32, which is less than or equal to 32. However, if flatten-component-5 transforms 95 to 127, we've also met both postconditions. 127 is an element of the list, and 127-95 is 32. How do we handle the possibility that either value is correct? We focus on the postconditions as described, rather than looking for particular values.

(define valid-components (list 0 63 127 191 255))
(test-case "(fc5 95) is a valid component"
           (check-true (member? (flatten-component-5  95) valid-components)))
(test-case "(fc5 95) is close to 95"
           (check-true (<= (abs (- (flatten-component-5 95) 95)) 32)))

You will likely find it much easier to write your overall test suite if you write one or more helper procedures.

Problem 2: A First Approach to Flattening

An obvious way to implement flatten-component-5 is to write a conditional for each of the natural cases. For example, if the input value is less than 32, we return 0. Use that approach to implement flatten-component-5.

Problem 3: Another Approach to Flattening

As you may recall from the time before we learned conditionals, many of the things that we are first inclined to write with conditionals we can write equally well without conditionals. Implement flatten-component-5 with an appropriate arithmetic expression that does not involve conditionals.

Note: You may call this version flatten-component-5-alt or something similar, so that DrRacket does not complain about you trying to have duplicate names in your file.

Hint: You probably want to use a combination of addition, subtraction, multiplication, division, rounding, floor, and ceiling. (You probably won't use all of those operations.)

Note: You are permitted to use the values 0, 64, 128, 192, and 256 if you find that approach easier.

Part B: Nearby Values

Topics: Documentation, recursion, transforming images.

While the conditional and arithmetic approaches above are useful, they are not particularly general. There are a number of ways to generalize the “nearest value” algorithm. If the values are equally divided (as they are in the example above), we can write a somewhat more complex formula. But what if we want a nonlinear division, say the values 0, 32, 64, 128, and 255? In that case, it might make sense to make a list of possible values, and ask for the “nearest” of those values. (As we noted in the previous problem, there can be two nearest values. In that case, either should be acceptable.)

In Scheme, we might describe the procedure as (nearest val values), and it's supposed to return a value in values that is closest to val.

Problem 4: Documenting nearest

Write the six-P style documentation for nearest. Pay particular attention to the preconditions and postconditions. Although we first came up with nearest because we wanted to find a nearest component, note that you should generalize the function so that it works for any reasonable number and list.

Problem 5: Implementing nearest

Implement nearest. Given that you need to identify an element of a list, you will likely need recursion. You will likely find the procedure easier to write if you use helper recursion.

Problem 6: Flattening Images, Revisited

We can use the nearest procedure as part of a broader attempt to flatten images. For example, we might write a procedure that takes an image and a list of integers to use as valid components.

;;; Procedure:
;;;   image-flatten
;;; Parameters:
;;;   image, an image id
;;;   valid-components, a list of integers
;;; Purpose:
;;;   "flatten" image by converting each component to a nearby value
;;; Produces:
;;;   flattened, an image id
;;; Preconditions:
;;;   Each element of valid-components is between 0 and 255, inclusive. That is,
;;;     0 <= (list-ref valid-components i) <= 255 
;;;        for any 0 <= i < (length valid-components).
;;; Postconditions:
;;;   flattened is similar to image.
;;;   Each component of each color in flattened is an element of
;;;     valid-components. That is,
;;;     (member? (irgb-component (image-get-pixel flattened col row))
;;;              valid-components) for any valid
;;;      column 0 <= col < (image-width image), 
;;;      row    0 <= row < (image-height image), and 
;;;      component extraction function irgb-red, irgb-green, or irgb-blue.

Implement this procedure.

Note: If you can't get nearest to work correctly, you may use the following incorrect version. Your images will look awful, but you can at least assure us that you understand how you would use the function if you'd implemented it correctly.

(define nearest
  (lambda (val values)
    (if (and (> val 127) (not (null? (cdr values))))
        (cadr values)
        (car values))))

Part C: Miscellaneous

Problem 7: A decreasing? Predicate

Topics: Predicates, documentation, numeric values.

At times, we want to know something about the relative ordering of values in a list. For example, if we have a list of numbers (say, representing rankings in figure skating), we might want to determine whether the numbers are ordered in decreasing order, from largest to smallest.

Let's start by specifying the procedure carefully. Document a procedure, (decreasing? numbers), that returns #f only when any number in the list is less than the number following it, and returns #t otherwise. In documenting this procedure, pay particular attention to the preconditions and postconditions.

> (decreasing? (iota 10))
#f
> (decreasing? (reverse (iota 10)))
#t
> (decreasing? (list 1/10 1/2 1/3 5/6))
#f
> (decreasing? (list 10 3 3 2 1 1 0))
#t
> (decreasing? (list 1/2 1/3 1/4 1/5 1/6))
#t
> (decreasing? (list 10))
#t
> (decreasing? null)
#t

Problem 8: Implement decreasing?

Topics: Recursion, predicates, and, or.

Implement the decreasing? procedure that we described and you documented in the previous problem.

While your inclination may be to write this procedure using if (or when, or cond), for full credit you should avoid using if (or when or cond). Focus instead on logical ways to combine the ways in which you know that the predicate holds or fails to hold.

Problem 9: Transforming Color Names

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 a procedure, (cnames-much-darker color-names), that, given a list of color names, returns a new list of color names, with each color name in the result list an approximation of the color that results from applying rgb-darker twice to the corresponding color in the original list. For example,

> (cnames-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 cnames-much-darker
  (lambda (cnames)
    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). You may receive a bit of extra credit if you can achieve such a solution.

Problem 10: Mystery Procedure

Topics: Code reading, procedures as parameters.

(define mystery (o rgb-list->irgb (l-s map (l-s + 32)) irgb->rgb-list))

a. Figure out what mystery does, then rename it and write 6P documentation for it.

b. Write a seventh P, Process, that explains the details of the underlying algorithm and how the code above manifests an implementation of that algorithm.

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

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

  • Because we assume a true/false value, we should be using member? rather than member. [TK, 1 point]
  • Sam misspelled “appropriate”. [OQ, 1 point]
  • Sam misspelled “multiplication”, but caught the error. [SR, 0 point]
  • The doubly-darker version of pink seems to be tan rather than plum. [AM, 1 point]
  • The example flatten-component-5 used color instead of component. [CF, 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 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.


Jerod Weinman

Copyright 2007-2014 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 3.0 Unported License .