Exam 2: Control


Assigned: Wednesday, October 31

Due: Tuesday, November 6, 10:30 p.m.

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 ten 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 be able to complete the exam in a reasonable amount of time. In particular, this exam is likely to take you about three to four 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.

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.

  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.

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 Tuesday night, 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 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. 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 (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: Exploring and Computing with Drawings

Topics: Drawings as values, Predicates, Lists, Conditionals, Recursion

As you may recall, in MediaScheme, the basic values of the “drawing” data type are represented as lists of eight elements.

> drawing-unit-circle
(drawing ellipse 0 "" -0.5 -0.5 1 1)
> drawing-unit-square
(drawing rectangle 0 "" -0.5 -0.5 1 1)
> (drawing-hshift drawing-unit-circle 2)
(drawing ellipse 0 "" 1.5 -0.5 1 1)
> (drawing-hscale drawing-unit-circle 5)
(drawing ellipse 0 "" -2.5 -0.5 5 1)

For the basic drawing values, the eight elements are straightforward. Element 0 is the symbol drawing. Element 1 is the symbol ellipse or the symbol rectangle. Element 2 is the color of the drawing, represented as an RGB number. Element 3 is a string (currently unused). Element 4 is the left edge of the drawing. Element 5 is the top edge of the drawing. Element 6 is the width of the drawing. Element 7 is the height of the drawing.

There are also compound drawings, created by drawing-group and similar procedures. We will not consider them at this time, except to note that they exist.

Problem 1: Predicates for Simple Drawings

a. Write, but do not document, a predicate, (simple-drawing? value), that checks whether value meets the form of a simple drawing. That is, your predicate should check whether value has the form described above.

Note: You may not use the procedure drawing? in solving this problem.

> (simple-drawing? drawing-unit-circle)
#t
> (simple-drawing? 4)
#f
> (simple-drawing? (drawing-hshift drawing-unit-square 5))
#t
> (simple-drawing? (drawing-group drawing-unit-circle drawing-unit-square))
#f
> (simple-drawing? (iota 8))
#f
> (simple-drawing? (list 'drawing 'ellipse RGB-BLACK "" 2 3 4 5))
#t
> (simple-drawing? (list 'drawing 'ellipse "black" "" 2 3 4 5))
#f
> (simple-drawing? (list 'drawing 'ellipse RGB-BLACK))
#f

b. Write, but do not document, a predicate, (drawing-rectangle? val), that determines whether val is a drawing and is a rectangle. You can use the simple-drawing? predicate to first check whether a value is a drawing.

> (drawing-rectangle? drawing-unit-square)
#t
> (drawing-rectangle? (drawing-scale drawing-unit-square 23))
#t
> (drawing-rectangle? (drawing-hshift drawing-unit-square -5))
#t
> (drawing-rectangle? drawing-unit-circle)
#f
> (drawing-rectangle? "This is a drawing of a rectangle")
#f

Problem 2: The Perimeter of Drawings

Write a procedure, (drawing-perimeter val), that finds the perimeter of a drawing that is a rectangle. (You need not find the perimeter of any other drawing such as an ellipse.)

Be sure to check preconditions and print appropriate error messages if those preconditions are not met.

> (drawing-perimeter drawing-unit-square)
4
> (drawing-perimeter (drawing-scale drawing-unit-square 20))
80
> (drawing-perimeter drawing-unit-circle)
drawing-perimeter: Don't know how to find the perimeter of that drawing.
> (drawing-perimeter (drawing-hscale drawing-unit-square 20))
42
> (drawing-perimeter (drawing-vscale (drawing-hscale drawing-unit-square 20) 15))
70
> (drawing-perimeter (drawing-group drawing-unit-circle drawing-unit-square))
drawing-perimeter: Don't know how to find the perimeter of that drawing.
> (drawing-perimeter 5)
drawing-perimeter: Expected a drawing, given 5

Problem 3: The Largest Drawing

Write a procedure, (drawings-largest drawings), that takes a list of rectangle drawings and returns the drawing in the list having the largest perimeter.

Part B: Image Computing

Problem 4: Hidden Images

Topics: Image transformations, Numeric values, Anonymous procedures, RGB colors

In this problem, we consider an approach to keeping messages secret. Steganography is the process of hiding a message in an image such that no one, other than the sender and receiver, even knows there is any hidden information. One approach to hiding an image inside a full-color image is to use the "least significant bits" to store the secret image. In the same way you're not likely to notice if two numbers far after the decimal point have changed, no one is likely to notice if the colors in a photo have been changed by only 1/8 from the original brightness values. How do we do that?

Just like the decimal numbers you're probably used to have "places" for the ones digit, tens digit, thousands digit, etc., the numbers storing the colors have eight "places" for binary bits that are either zero or one. We can shift and manipulate these binary bits by dividing and multiplying the number by powers of two (rather than powers of ten as for decimal numbers), as we do in the following.

Here is the algorithm we used to create a steganographic image.

  • The original or cover image and a secret image are both inputs to the algorithm, and they have the same width and height.
  • For each row and column,
    • For each color channel (R, G, and B)
      • Divide the channel value in the cover image by 8 (23) to shift off the last three bits, take the floor, and multiply the result again by 8 to put these bits back where they belong. This has the effect of setting the last three places in the binary representation of the number to zero.
      • Divide the channel value in the secret image by 32 (25) to shift off the last five bits, leaving only the first three (which are the most significant places).
      • Add the two results together to form the value of the color channel for the pixel in the steganographic image.
    • Combine the three color channels into a single RGB for the pixel at this row and column of the steganographic image.
  • Return the steganographic image.

Decoding the image is much simpler. At each pixel, for each color channel you can get the last three bits (which contain our hidden image) by taking its modulus with respect to 8 and rescaling the result to the range 0-255.

(a) Write, but do not document, a procedure, (image-steg-decode steg-image), that takes a steganographic image produced using this algorithm and produces the secret image.

Note: Use image-variant in your procedure. You should write your procedure with as little repeated code as possible. However, the fewer lambdas you use to write your solution the more points you will receive. Bonus points will be given for a completely lambda-free solution.

(b) Download this image of the kitten and test your procedure on it. Describe the secret image hidden inside it.

Problem 5: Computing Multiple Circles

Suppose we want to draw a background and three circles on canvas.

  • The background has sporadically placed white dots.
  • The first circle has radius 40, is centered at (30,40), and is colored with a function that uses sine and cosine to produce horizontal bands.
  • The second has radius 30, is centered at (50,50), and is colored with shades of purple based on their distance from (60,60).
  • The third has radius 5, is centered at (20,50), and is black.

We might write

(define canvas (image-new 100 100))
(image-show canvas)
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (and (zero? (mod col 7)) (zero? (mod row 5)))
       RGB-WHITE
       RGB-BLACK)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 1600 (+ (square (- col 30)) (square (- row 40))))
       (rgb-new (+ 128 (* 255 (sin (* (/ pi 60) row)))) 
                0 
                (+ 128 (* -255 (cos (* (/ pi 60) row)))))
       rgb-transparent)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 900 (+ (square (- col 50)) (square (- row 50))))
       (let ((c (* 4 (sqrt (+ (square (- col 60))
                              (square (- row 60)))))))
         (rgb-new c 0 c))
       rgb-transparent)))
(region-compute-pixels!
 canvas 0 0 (- (image-width canvas) 1) (- (image-height canvas) 1)
 (lambda (col row)
   (if (>= 25 (+ (square (- col 20)) (square (- row 50))))
       RGB-BLACK
       rgb-transparent)))

Rewrite this code so that there is only one call to image-compute. That is, you should use a single expression of the following form.

(define canvas (image-compute ...))

Hint: Use a cond to decide which, if any, of the circles each position belongs in.

Hint: Which circle appears in front, and which appears behind? Your code should produce the same image as the code above.

Part C: Repeating Turtles

Topics: Turtles, Iteration, Anonymous procedures

Problem 6: Square Spiraling Turtles

Write, but do not document, a procedure (turtle-square-spiral! turtle initial-side segments scale-factor) that draws a spiral of the given number of segments, with each segment's length scale-factor times the the previous segment's length.

For example:

(define world (image-new 200 200))
(define tommy (turtle-new world))
(turtle-teleport! tommy 100 100)
(image-show world)
(turtle-square-spiral! tommy 75 20 0.9)

Problem 7: Flowery SpiralingTurtles

Most of the turtle procedures you have been writing so far use the same turtle to iterate a process. For instance, the procedure turtle-spiral! from the reading on iteration iterates the process of moving one turtle forward and turning by an increasing angle.

  (define turtle-action-02!
  (lambda (turtle angle)
    (turtle-forward! turtle 5)
    (turtle-turn! turtle angle)))

  (define turtle-spiral!
  (lambda (turtle steps)
    (for-each (l-s turtle-action-02! turtle)
              (list-drop (iota (+ 1 steps)) 1))))

While repeatedly drawing polygons is interesting and useful because the turtle always returns to its original position, there are situations in which we may not want to rely on this postcondition. Those situations will often call for using multiple turtles.

Using turtle-spiral! as a helper, write, but do not document, a procedure, (turtles-spin-longer-spirals! turtles initial-steps scale-factor angle), that uses turtle-spiral! with each turtle in the list turtles. Before drawing its spiral, each turtle should be turned by angle degrees more than its previous turtle.

For example, if angle were 30, the first turtle would turn by zero, the second by 30, the third by 60, and so on.

In addition, each turtle's spiral should have a number of steps that is approximately scale-factor times the previous turtle's number of steps. (Because the number of steps needs to be an integer, you may need to round.)

Here is an example of turtle-spin-longer-spirals! in action:

(define forest (image-new 200 200))
(define tiffany (turtle-new forest))
(turtle-teleport! tiffany 100 100)
(define clones (map turtle-clone (make-list 8 tiffany)))
(turtles-spin-longer-spirals! clones 4 1.5 45)

Part D: Recursion

Topics: Lists, Recursion, Anonymous procedures

Problem 8: Reading code

An important Scheme primitive function is car that returns the first item in a list. What if you want the last item instead? Scheme does not provide last-item as a primitive, you have to make your own, perhaps like this:

;;; Procedure: 
;;;   last-element
;;; Parameters: 
;;;   lst, a list
;;; Purpose: 
;;;   Find and return the last element of a list
;;; Process
;;;   Repeatedly take cdr until we reach the list's end
;;; Produces:
;;;   last, a value
;;; Preconditions: 
;;;   lst must be non-empty
;;; Postconditions: 
;;;   last is the last element of lst
(define last-element
  (lambda (lst)
    (cond
      ((not (list? lst)) 
       (error "last-element expects a list, given: " lst))
      ((null? lst) 
        (error "last-element expects a non-empty list, given: " lst))
      (else
       (let kernel ((remaining lst))
         (if (null? (cdr remaining)) 
             (car remaining)
             (kernel (cdr remaining))))))))

There is a shorter way to write last-element that does not require you to (explicitly) write a recursive procedure. Write a shorter version of last-element. Explain in your 6-P documentation how your shorter version achieves its goal with a seventh P (process).

Problem 9: Fixing Unreadable Code

As you've probably noted, we like to write long procedure names that make it perfectly clear what procedures are supposed to do. These procedures have names like image-compute-pixels! or rgb-complement. We also try to choose good names for the variables and parameters in our code.

However, some programmers prefer to give their procedures and variables short names, such as f and x. Some pay little attention to formatting.

Unfortunately, such short names can obfuscate code, particularly when combined with a lack of care in formatting. For example, consider the following useful procedure.

(define m (lambda (v) (let k ((r v)) (if (null? (cdr r)) null (cons (car r) (k (cdr r)))))))

(a) Make this procedure definition easier to read as follows.

  • First, reformat the procedure so that the indentation properly demonstrates nesting. That is, you should choose appropriate points to put in carriage returns. Remember that MediaScheme will re-indent for you after you put in those returns, as long as you select the text and type Control-Tab.
  • Then, figure out what the procedure does. After doing so, change the names in the procedure to clarify the roles of various things. You should certainly rename m, k, r, and v. (As a hint, start by figuring out what types the parameters should be.)
  • Write introductory comments (the six Ps) to explain the purpose (and the other Ps) of the procedure formerly named m. Pay particular attention to the preconditions.
  • Finally, modify your code so that it verifies the preconditions.

When you format your exam, please put the introductory comments before the revised procedure definition.

(b) Perhaps you'll notice that there is a shorter way (in terms of code) to implementing the same procedure. Write a second version that is shorter, much like Problem 8.

(c) Which version of last-element do you like better? What about m (or rather whatever you renamed it)? Do you like the original recursive version, or do you prefer the shorter version? Why? Write a sentence or two explaining your choice.

Problem 10: Palindromes

(I am Sam I am) is not a list palindrome; but (I am Sam am I) is a list palindrome. (a man a plan a canal panama) is not a list palindrome; but (a m a n a p l a n a c a n a l p a n a m a) is a list palindrome. Here is a definition of what it means to be a list palindrome:

  1. The empty list is a palindrome.
  2. A single element list is a palindrome.
  3. If the first element is equal to the last element and if the list without its first and without its last elements is a palindrome, then the list is a palindrome.
  4. Nothing else is a palindrome.

(a) If lst is (i am sam am i), what is (m (cdr lst)) where m is as defined in Problem 9?

(b) Complete the definition and documentation of the procedure palindrome? that returns #t for a list palindrome and #f for anything else.

Hint: You should use the procedures from Problems 8 and 9.

;;; Procedure: 
;;;   palindrome?
;;; Parameters: 
;;;   lst, a list
;;; Purpose: 
;;;   Determine whether a list is a palindrome
;;; Process:
;;;   If lst is short enough we can return #t.
;;;   If the first and the last items of lst match, 
;;;     we check the inner portion of lst for "palindromicity"
;;; Produces: 
;;;   is-palindrome, a boolean
;;; Preconditions:
;;;   lst is a list [Unverified]
;;; Postconditions:
;;;   ___
;;;   ...
(define palindrome?
  (lambda (lst)
    (cond
      ((null? lst) ______)
      ((null? (cdr lst)) ______)
      ((equal? (car lst) (last-element lst)) 
       (palindrome? ______))
      (else #f))))
> (palindrome? '(I am Sam I am))
#f
> (palindrome? '(I am Sam am I))
#t
> (palindrome? '(able was I ere I saw elba))
#f
> (palindrome? '(able was I ere I was able))
#t
> (palindrome? (append (iota 20) (reverse (iota 20))))
#t

(c) Did you notice that the reverse of a palindrome is the same as the original list? Write a shorter version of palindrome? that makes use of this observation.

(d) Do you prefer the version of palindrome? from (b) or from (c)? Write a few sentences about why, commenting on how elegant or intuitive you find them and possibly their relative efficiency.

Some questions and answers

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

Problem 1

Question: For part b, are we allowed to use Scheme's built-in drawing-rectangle? procedure as part of our solution?
Answer: No, you will be overriding that definition with your own implementation.

Problem 4

Question: If we create a helper procedure in order to define image-steg-decode, do the lambdas we use with image-steg-decode also count toward our total?
Answer: Yes, they count anonymous or otherwise.

Problem 5

Question: You said we should use image-compute!, but image-compute! creates an entirely new image, and we're starting with canvas, which has already been defined. Should we use image-compute-pixels! instead?
Answer: You could/should use a single expression of the following form.
(define canvas (image-compute ...))

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.

  • Procedure image-compute had an errant exclamation in Problem 5 [BW, FB; 1 point].
  • Procedure palindrome? was missing a parenthesis. [BW; 1 point].

Jerod Weinman

Copyright 2007-2012 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 2.5 License .