Exam 1: Scheme and Color Basics
Due at 10:30pm on Tuesday, September 22, 2015

Assigned

Wednesday, September 16th, 2015

Due

10:30pm, Tuesday, September 22nd, 2015 (electronic)
1:00pm, Wednesday, September 23rd (printed)

About this Exam

This is a take-home examination. You may work on the exam any time you deem appropriate, provided you return it to me by the due date. There are seven problems on this examination. Each problem is worth the same number of points. Although each problem is worth the same amount, problems are not necessarily of equal difficulty.

Please read the entire exam before you begin.

We expect that this exam will take about four hours, provided you have mastered the material in course so far. Write down the amount of time each problem takes on your exam. Each person who does so will earn two points of extra credit on the exam. We use this information to make sure our exams take a reasonable amount of time.

Sanity Clause

You should not work more than five hours on this exam. Stop at five hours and write “There’s more to life than computer science” on the cover sheet of the examination and you will earn at least 70% on this exam, provided you record the time spent on each problem and get at least two problems mostly correct. You will receive either 70% or the percentage earned based on the work you have completed, whichever is largest. Bonus points for errors and recording time do not increase your grade above 70%, are not applied in the first case (70%), but penalties (e.g., for failing to number pages) usually are.

Important: You may not count time reviewing readings, laboratories, or assignments toward the amount of time you spend on the exam or on individual problems.

Partial Credit

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.

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, including class mentors and tutors. 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 we 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 or how long you have 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 write, sign, and date each statement separately. 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 anyone other than Professor Curtsinger.

Exams can be stressful. Don’t let the stress of the exam lead you to make decisions that you will later regret. Violations of academic honesty and exam policies will be handled through the Committee on Academic Standing, the College Hearing Board, or the Computer Science Department’s Academic Honesty Policy, as appropriate.

Code, Documentation, and Prose

Code

You will need to write code for many problems on the exam. Unless the exam says otherwise, 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 by running your code.

Documentation

You must provide 6P-style documentation for each primary procedure you write, unless the exam says otherwise.

Prose

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.

Turning in Your Exam

You must present your exam in two forms, physically and electronically. I will be grading exams blindly, meaning I will not know whose exam I am grading to avoid any possible bias. You have been assigned a random secret number, which you will use to identify yourself on the exam.

Write all of your answers using the computer, print them out, number the pages, staple them together, and hand me the printed copy. Please make sure that your randomly assigned secret number appears at the top of every page.

Cover Sheet

You should turn in a separate cover sheet along with your stapled and printed answers. Do not staple your cover sheet to the rest of your exam. Your cover sheet must 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
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.

Give your printed exams to me in class on Wednesday, September 23rd. Submit the electronic copy of your exam by emailing it to grader-151-02@cs.grinnell.edu by 10:30pm on Tuesday, September 22nd. It is presumed the physical copy matches the electronic copy. Any discrepancies (other than formatting) will likely be considered a misrepresentation of your work and referred appropriately. 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 larger penalty.

Font Requirements

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.

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 you need help outside of office hours, please send me email. I will do my best to respond promptly.

I will reserve time at the start of each class to discuss any general questions you have on the exam.

Checklists

Since many students regularly seem to miss different elements of the exam, these checklists serve as a way to help you remember everything that you have to do.

Big Picture

• Have you picked up a random number?
• Have you done your requisite work on the exam? (Due: Tuesday)
• Have you gone over the contents of your exam using the checklist below? (Due: Tuesday)
• Have you submitted the code online? (Due: Tuesday)
• Have you written a cover sheet and gone over the cover sheet checklist? (Due: Tuesday)
• Have you printed your examination and gone over the printed exam checklist? (Due: Tuesday)

Exam Contents

• Have you reviewed the question and answer section of the exam?
• Have you removed all identifying materials from your code, other than your assigned id number?
• If you’ve copied any code, have you also copied the accompanying documentation?
• Have you cited all the code that you’ve relied upon?
• Have you recorded how long each problem took?
• Have you included examples for each procedure you’ve written?
• Have you documented each procedure you’ve written?
• Have you checked your spelling?

Printed Version

• Did you use a fixed-width font?
• Have you written or printed your secret number on every page?
• Have you written or printed the page number on every page?
• Have you looked at the output to make sure that there are no instances in which the code wraps badly?

Cover Sheet

• Have you written your id on the cover sheet?
• Have you written your name on the cover sheet?
• Have you written, signed, and dated the first academic honesty statement? (This item assumes you consider it appropriate to sign the first academic honesty statement.)
• Have you written, signed, and dated the second academic honesty statement? (This item assumes you consider it appropriate to sign the second academic honesty statement.)

Problems

Problem 1: Bounded Ratings

Topics: Numeric values, writing procedures, section, composition

Without using lambda or if, write a procedure, (bound-rating rating), that takes one input, a real number, and returns:

• 0 if rating < 0
• 10 if rating > 10
• rating if neither of the two previous conditions holds.

Note that to define this procedure, you will find it necessary to use o, section or both. You will also find it useful to go back and think about how we’ve bounded values in past exercises.

You do not need to document this procedure.

Problem 2: Identifying the Largest Value

Topics: Procedures, numeric computation

Write a procedure, (index-of-largest val1 val2 val3) that returns

• 1 if val1 is larger than the other two values,
• 2 if val2 is larger than the other two values,
• 3 if val3 is larger than the other two values, and
• whatever you’d like, if no one value is largest.

> (index-of-largest 100 50 0)
1
> (index-of-largest 100 0 50)
1
> (index-of-largest 50 100 0)
2
> (index-of-largest 0 100 50)
2
> (index-of-largest 0 50 100)
3
> (index-of-largest 50 0 100)
3

You may not use conditionals (e.g., if) in writing index-of-largest.

You do not need to document this procedure.

Problem 3: Adding Times

Topics: Code reading, times, complex numbers, numeric computation, abusing Scheme

Suppose we want to do math with times, and we limit ourselves to times that involve minutes and seconds. How do we represent both minutes and seconds? Here’s a not-necessarily-clever trick: We could use complex numbers. The real part of the imaginary number represents the minutes and the imaginary part represents the seconds.

Here are some procedures that allow us to work with that representation.

;;; Procedure:
;;;   time
;;; Parameters:
;;;   min, a non-negative integer
;;;   sec, a non-negative integer
;;; Purpose:
;;;   Generate a representation of min minutes and sec seconds
;;; Produces:
;;;   tm, a complex number representing a time
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (minutes tm) = min
;;;   (seconds tm) = sec
(define time
  (lambda (min sec)
    (+ min (* 0+i sec))))

;;; Procedure:
;;;   minutes
;;; Parameters:
;;;   tm, a complex number representing a time
;;; Purpose:
;;;   Extract the minutes from tm
;;; Produces:
;;;   min, an integer
(define minutes real-part)

;;; Procedure:
;;;   seconds
;;; Parameters:
;;;   tm, a complex number representing a time
;;; Purpose:
;;;   Extract the seconds from tm
;;; Produces:
;;;   sec, an integer
(define seconds imag-part)
 
;;; Procedure:
;;;   display-time
;;; Parameters:
;;;   tm, a complex number representing a time
;;; Purpose:
;;;   Display the time.
;;; Produces:
;;;   [Nothing; called for the side effect]
(define display-time
  (lambda (tm)
    (display (minutes tm))
    (display " minutes and ")
    (display (seconds tm))
    (display " seconds.")
    (newline)))

Write and document a procedure, (add-times time1 time2), that adds the two times appropriately. For example:

> (define t1 (time 5 35))
> (minutes t1)
5
> (seconds t1)
35
> (display-time t1)
5 minutes and 35 seconds.
> (define t2 (add-times t1 t1))
> (minutes t2)
11
> (display-time t2)
11 minutes and 10 seconds.
> (display-time (add-times t1 t2))
16 minutes and 45 seconds.

Your procedure should correctly limit the number of seconds to between 0 and 59, even if the input time is not in that form.

> (define t3 (time 0 97))
> (display-time t3)
0 minutes and 97 seconds.
> (define t4 (add-times t3 t3))
> (display-time t4)
3 minutes and 14 seconds.
> (display-time (add-times (time 0 0) t3))
1 minutes and 37 seconds

Problem 4: Timely Testing

Write a test suite for add-times.

We will likely run your test suite on a variety of implementations of add-times, including some that are mostly, but not completely, correct.

Note: Your tests should only involve correct calls to add-times. If, for example, the times are negative, there are no restrictions on what the procedure should do.

Problem 5: Whatzitdo?

Topics: Numeric functions, reading code, procedures, documentation

Consider the following procedure.

(define fun
  (lambda (n i)
    (quotient (remainder n (expt 10 (+ i 1))) (expt 10 i))))

Your job is to be a code detective. Read the procedure definition carefully and call the procedure with many different parameters to learn what the procedure does and how it works.

Hint: Try using large values of n and small values of i. You can discover the purpose of the procedure either by trying many examples or by working through an example by hand.

a. In your own words, describe what fun computes. That is, explain the purpose of the procedure.

b. In your own words, explain how fun works. That is, explain the algorithm that is used.

c. What limitations are there on n and i in order for this procedure to work sensibly?

Problem 6: A Strange Transformation

Topics: Integer-encoded RGB colors, code reading, documentation

Consider the following definitions.

;;; Procedure:
;;;   irgb-component-add
;;; Parameters:
;;;   color, an integer-encoded RGB color
;;    offset, an integer
;;; Purpose:
;;;   Add offset to each of the components of color.
;;; Produces:
;;;   new-color, an integer-encoded RGB color
;;; Preconditions:
;;;   offset >= 0
;;; Postconditions:
;;;   (irgb-red new-color) = (min 255 (+ offset (irgb-red color)))
;;;   (irgb-green new-color) = (min 255 (+ offset (irgb-green color)))
;;;   (irgb-blue new-color) = (min 255 (+ offset (irgb-blue color)))
(define irgb-component-add
  (lambda (color offset)
    (irgb (+ offset (irgb-red color))
          (+ offset (irgb-green color))
          (+ offset (irgb-blue color)))))

;;; Procedure:
;;;   irgb-component-sub
;;; Parameters:
;;;   color, an integer-encoded RGB color
;;    offset, an integer
;;; Purpose:
;;;   Subtract offset from each of the components of color.
;;; Produces:
;;;   new-color, an integer-encoded RGB color
;;; Preconditions:
;;;   offset >= 0
;;; Postconditions:
;;;   (irgb-red new-color) = (max 0 (- (irgb-red color) offset))
;;;   (irgb-green new-color) = (max 0 (- (irgb-green color) offset))
;;;   (irgb-blue new-color) = (max 0 (- irgb-blue color) offset))
(define irgb-component-sub
  (lambda (color offset)
    (irgb (- (irgb-red color) offset)
          (- (irgb-green color) offset)
          (- (irgb-blue color) offset))))

(define irgb-strange 
  (lambda (x y)
    (irgb-component-add (irgb-component-sub x y) y)))

Write the six-P style documentation for irgb-strange. You may find it useful to rename the parameters.

Problem 7: Bounding Colors and Images

Topics: Integer-encoded RGB colors, color transformations, image transformations, procedures, bounded values, sectioning.

Consider the following procedure documentation.

;;; Procedure:
;;;   irgb-bound-components
;;; Parameters:
;;;   color, an integer-encoded RGB color
;;;   lower, an integer
;;;   upper, an integer
;;; Purpose:
;;;   Bound the components to be in the range [lower .. upper]
;;; Produces:
;;;   bound, an integer-encoded RGB color
;;; Preconditions:
;;;   0 <= lower <= upper <= 255
;;; Postconditions:
;;;   If (irgb-red color) < lower, then (irgb-red bound) = lower
;;;   If (irgb-red color) > upper, then (irgb-red bound) = upper
;;;   If neither of the preceding two cases holds, then
;;;     (irgb-red bound) = (irgb-red color)
;;;   If (irgb-green color) < lower, then (irgb-green bound) = lower
;;;   If (irgb-green color) > upper, then (irgb-green bound) = upper
;;;   If neither of the preceding two cases holds, then
;;;     (irgb-green bound) = (irgb-green color)
;;;   If (irgb-blue color) < lower, then (irgb-blue bound) = lower
;;;   If (irgb-blue color) > upper, then (irgb-blue bound) = upper
;;;   If neither of the preceding two cases holds, then
;;;     (irgb-blue bound) = (irgb-blue color)

a. Implement the irgb-bound-components procedure.

b. Using your implementation, write a procedure (image-mid image) that creates a variant of image in which every color component is bounded below by 64 and above by 196.

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 sections have the same exam?

More or less.

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 (not on this exam, but on the class). 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.

Much of your sample 6P-style documentation has incomplete sentences. Can we follow that model? That is, can we use incomplete sentences in our 6P-style documentation?

Yes, you can use incomplete sentences in 6P-style documentation.

You tell us to start the exam early, but then you add corrections and questions and answers. Isn’t that contradictory? Aren’t we better off waiting until you’ve answered the questions and corrected any errors?

That’s one of the reasons we give extra credit to those who work on the exam early. But you’re also better able to get your questions answered early if you start early (or at least we think you are). Later questions will generally be told “See the notes on the exam.”

How do we know what our random number is?

You should have received one in class. If you need a new one, there’s a stack in the back of our classroom.

When we print the exam, do you prefer one problem per page (one on the front of the page, one on the back, unless more is needed)? If not, is it okay to have a blank line between each problem?

Either is fine. If you do go the less paper route, make sure to insert a few blank lines between problems, as well as a comment like ; --------- PROBLEM 2 -------------.

To show we’ve tested the code informally, would you just like us to just post the inputs we used to test the procedure? If so, how should we list those?

Copy and paste the interactions pane into the appropriate place in the definitions pane. Select the text. Under the Racket menu, use “Comment out with semicolons.”

Should we include examples and, if so, how do we include them?

You should certainly include examples. We would recommend that you copy and paste them from the interactions pane to right below the problem in the definitions pane, and then comment them out with semicolons. (Select and then choose “Comment out with semicolons” from the “Racket” menu. Do not use “Comment out with a box”!

Should we cite our partner from a past lab or assignment if we use code from a past lab or assignment?

You should cite both yourself and your partner, although you should do so as anonymously as possible. For example: “Ideas taken from the solution to problem 7 on assignment 3 written by student 641321 and partner”.

Problem 1

Can I use more than one <> in section?

Certainly. Each <> refers to a separate input. However, it’s unlikely to be helpful for this problem, since you only have one input. You will certainly find section useful. You will also find composition (o) useful.

Problem 2

I have a feeling that I’ve seen this problem before. Where might that have been?

You may have seen something similar on hw 3.

Can I assume that all the parameters are positive for this problem?

Yes. However, you may earn extra credit if you get it to work with negative numbers, too.

I’ve found that if the second and third values are equal and larger than the first value, my procedure gives a value of 5. That seems weird. Is it okay?

Yes, that’s okay. You can return anything you want if no single value is the largest.

Problem 4

Can you give a sample test?

(check-equal? (minutes (add-times (time 1 40) (time 2 40))) 4)

What should our documentation look like?

;;; Name:
;;;   ...
;;; Type:
;;;   test suite
;;; Value:
;;;   ...

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

• There was a misplaced paren in problem 5’s definition of irgb-component-sub. [GN, BD, and SJ, +1 point]
• There should be no restrictions on invalid inputs in problem 4. [EN, +1 point]

Citations

Some 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 difficult, if not impossible.

Some problems on this exam were inspired by conversations with our students and by correct and incorrect student solutions on a variety of problems. 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.