Exam 2: Repetition, Conditionals, and Careful, Concise Coding

Assigned: Wednesday, 26 October 2011

Due: 11:59 p.m., Tuesday, 1 November 2011

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 a 70 on this exam if you give evidence of a serious attempt on at least 6 of the problems or come talk to me about the exam no later than one week after it is returned.

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. Because 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 Weinman (that's me) or Professor Davis.

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.

While your electronic version is due at 11:59 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, 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. You should use examples other than those that may be provided with the exam. Do not include images; I should be able to regenerate those.

Unless I state otherwise, you should document any top-level procedures you write using the six-P documentation style.

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 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 (7 a.m. - 6 p.m.), feel free to try to call me in the office (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: Images

Problem 1: Lining up polygons

Topics: Turtles, repetition.

Write, but do not document, a procedure, (turtle-shift-polygon! turtle side-length sides shift-angle shift-distance copies), that draws the given number of copies of the specified polygon. Each copy should be offset by the specified shift-angle and shift-distance.

The turtle need not be returned to its original position and orientation.

Here is an example of turtle-shift-polygon! in action:

(define world (image-new 200 200))
(define tia (turtle-new world))
(image-show world)
(turtle-shift-polygon! tia 10 5 45 15 8)
(turtle-shift-polygon! tia 10 3 90 7 13)
(turtle-shift-polygon! tia 10 6 0 20 11)

You may certainly use your turtle-polygon! procedure from homework 5, but remember to cite it appropriately.

Problem 2: Varying the space between polygons

Topics: Turtles, repetition.

Write, but do not document, a procedure, (turtle-increasing-shift-polygon! turtle side-length sides shift-angle initial-shift-distance shift-increase copies), that draws the given number of copies of the specified polygon. Each copy should be offset by the specified shift-angle. The distance by which each copy is shifted should start at initial-shift-distance and increase by shift-increase for each copy.

The turtle need not be returned to its original position and orientation.

Here is an example of turtle-increasing-shift-polygon! in action:

(define world (image-new 200 200))
(define tia (turtle-new world))
(image-show world)
(turtle-increasing-shift-polygon! tia 10 5 45 5 5 6)
(turtle-increasing-shift-polygon! tia 10 3 90 8 3 6)
(turtle-increasing-shift-polygon! tia 10 6 0 10 5 6)

You may certainly use your turtle-polygon! procedure from homework 5, but remember to cite it appropriately.

Problem 3: Applying a color palette to an image

Topics: Image transformations, anonymous procedures, concision.

Recall that although the GIMP can represent 16,777,216 different colors, only some of those colors have names in MediaScheme. If you have an RGB color, you can find the name of the most similar color using rgb->color-name.

Write a procedure, (image-palettize image), that takes an image and produces a new image using only colors that have names in MediaScheme. Each color from the original image should be converted to the most similar named color.

For full credit, strive to write your code as concisely as possible.

Here is an example using image-palettize:


kitten	(image-palettize kitten)

Problem 4: Revising monochrome code

Topics: Code reading, local bindings, concision.

There are many ways to make code better, including avoiding unnecessary repeated code and computation. The procedure below applies a color transform that makes an image appear as though it consisted only of a single color, the second parameter. Rewrite this procedure to eliminate as much of the repeated code and computation as you can.

In addition, you could strive to make the code even more elegant by making it as concise as possible. (Hint: The most concise version may require you to rethink the method used to compute the three color channels.)

(define monochrome
  (lambda (image lens-color)
    (image-variant image
                   (lambda (rgb)
                     (rgb-new (* 0.5 (+ (* 0.30 (rgb-red rgb))
                                        (* 0.59 (rgb-green rgb))
                                        (* 0.11 (rgb-blue rgb))
                                        (rgb-red lens-color)))
                              (* 0.5 (+ (* 0.30 (rgb-red rgb))
                                        (* 0.59 (rgb-green rgb))
                                        (* 0.11 (rgb-blue rgb))
                                        (rgb-green lens-color)))
                              (* 0.5 (+ (* 0.30 (rgb-red rgb))
                                        (* 0.59 (rgb-green rgb))
                                        (* 0.11 (rgb-blue rgb))
                                        (rgb-blue lens-color))))))))

Part B: Implementing patterns of list recursion

Topics: List recursion, generalization.

Problem 5: Any and all

You may recall that in the reading on list recursion, revisited, we developed templates for testing whether a predicate holds for any value in a list or for all values in a list. We can implement these templates as new, more general procedures.

a. Write, but do not document, a recursive predicate, (all predicate? lst), that produces #t if predicate? is true for all values in lst, and #f otherwise.

b. Write, but do not document, a recursive predicate, (any predicate? lst), that produces #t if predicate? is true for some value in lst, and #f otherwise.

c. Using the rgb? predicate write, but do not document, a new function (all-rgb? lst). Make your implementation as concise as possible.

Problem 6: Folding

In the lab on list recursion, revisited, you developed a pattern for folding: the process of repeatedly applying a two-parameter procedure so as to process a list.

Implement your pattern as a procedure, (fold combine lst), where combine is a two-parameter procedure and lst is a list. You do not need to write 6-P documentation.

Using fold, many recursive procedures can be implemented much more concisely:

(define sum (l-s fold +))
(define product (l-s fold *))
(define largest (l-s fold max))
(define smallest (l-s fold min))
(define rgb-darkest (l-s fold 
                         (lambda (c1 c2) (if (< (rgb-brightness c1) (rgb-brightness c2))
                                             c1
                                             c2))))

(Note that fold will not work for combining values from left to right. We'll revisit this in the future.)

Part C: Writing procedures carefully

Problem 7: A mystery procedure

Topics: Code reading, style, documentation.

We encourage you to choose meaningful variable and procedure names in your code. Here is another example of why. Consider the following procedure.

(define m (lambda (l v) (if (null? l) null (cons ((car l) v) (m (cdr l) v)))))

Read and reformat the code. Try calling it with a variety of parameters. Your goal is to discover what parameters m accepts and what it does with those parameters. (Hint: Pay attention to error messages!)

Then, rewrite the procedure definition as follows:

The code should be formatted according to Scheme conventions.
Each parameter should have a meaningful name that (at least) reflects its type.
The procedure should have a meaningful name.
The procedure should be documented using the 6-Ps.

If you are not able to discover the purpose of the procedure, please do as much as you can for partial credit.

Problem 8: Testing a generalized tally procedure

Topics: Unit testing, documentation, list recursion.

Consider the following documentation for a common and useful procedure.

;;; Procedure:
;;;   list-tally
;;; Purpose:
;;;    Counts the number of items in a list for which some predicate is true.
;;; Parameters:
;;;   lst, a list
;;;   pred?, a predicate procedure
;;; Produces:
;;;   tally, a non-negative integer
;;; Preconditions:
;;;   pred? can be applied without error to each item in lst. [unverified.]
;;; Postconditions:
;;;   tally is equal to the number of distinct indices i for which
;;;      (pred? (list-ref lst i)) is not #f.

a. Write a complete suite of unit tests for the procedure list-tally that, when passed, would give you a high degree of confidence that the procedure was completely correct. In writing your test suite, use begin-tests!, end-tests!, test!, and test-error!. Next to each test, include a comment that indicates the purpose of the test in clear English.

b. The command below loads an implementation of list-tally that contains several bugs. Using your unit test suite, identify and describe as many bugs as you can find as an aid to the original developers. (Note that this implementation has at least two bugs.)

(require (file "/home/weinman/courses/CSC151/list-tally.scm"))

Problem 9: Documenting `find-first`

Topics: Documentation.

Whereas the any procedure above determines whether some item in a list satisfies a predicate, and the procedure index-of from the lab on verifying preconditions finds the (first) index of a particular item in a list, we often want a hybrid of these two procedures that gives us the first item in a list that satisfies a particular predicate. Write the complete 6-P documentation for such a procedure, examples of which are shown below.

> (find-first string? (list 'fork pi "yummy" "tummy"))
"yummy"
> (find-first odd? (iota 4))
1
> (find-first even? (list pi 4 'me))
even?: expects argument of type <integer>; given 3.141592653589793
> (find-first drawing? (list RGB-RED 'circle ""))
find-first: requires at least one element to satisfy the predicate, given (16711680 circle "")

Problem 10: Implementing `find-first`

Topics: Verifying preconditions, list recursion.

Implement the procedure find-first. Your implementation should verify as many preconditions as possible.

Some questions and answers

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

Problem 5

Question: Did you mean

(all-predicate?
lst)

instead of

(all predicate? 
lst)

Answer: No. The name of the function should be all. The function should have two parameters, predicate? and lst.

Question: May we assume that lst contains only elements that can be evaluated by predicate?

Answer: Yes, that is an appropriate precondition.

Problem 7

Question: Is ((car l) v) a typo?

Answer: No. Think about what type this indicates for l.

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 problems 1 and 2, “repetition” was misspelled as “repetion”. [PV, 1 point]