Exam 3: Recursion and Repetition

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 Friday 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. 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 three to 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 the equivalent of 70% on this exam, provided you filled in the prologue by the specified deadline 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. 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 are not usually applied in the second situation.

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 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: both physically and electronically. That is, you must write all of your answers using the computer, print them out, number the pages, staple them together, and hand me the printed copy. (In the past, we have asked students to put their name on the top of every page. To enhance our ability to do blind grading, please do not put your name on the top of pages.) The code and comments in your printed copy should use a fixed-width (a.k.a., monospaced or fixed-pitch) font; viable candidates (depending on your platform) include Monospace, Courier, DejaVu Sans Mono, Free Mono, Liberation Mono, Lucida Sans Typewriter. Failure to format your code with a monospace font will result in a penalty.

You must also email me a copy of your exam with the subject CSC 151.01 Exam 3 (Your Name). You should create the emailed version by copying the various parts of your exam and pasting them into an email message. 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. 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 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 your helper procedures as separate procedures, you must use the six P's for those helpers, even if you don't have to do so for the primary procedure. If you make your helper procedures local to the primary procedure, you only need give a short comment that describes the purpose of the helper.

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.

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 each class before the exam is due to discuss any general questions you have on the exam.

Topics: Lists, predicates, recursion, husk/kernel, precondition checking

Write, but do not document, a procedure, (double val lst), that takes a value and a list as parameters and adds an extra occurrence of val everywhere it occurs in the list.

> (double 3 (iota 5))
'(0 1 2 3 3 4)
> (double "mint" (list "red" "green" "blue"))
'("red" "green" "blue")
> (double "the" (list "the" "word" "the"))
'("the" "the" "word" "the" "the")
> (double "red" "r")
double expects a list for the second parameter, received "r"

As the last example suggests, your procedure should check its preconditions.

Topics: Unit testing, lists, types

Write a Rackunit test suite for the double procedure. (Yes, we know that we told you that you should write the test suite before writing the code. And you should. But many of you have found it hard to write a test suite without something that sort of works, so you can start there. A good test suite might find some errors in your original code.)

Topics: Characters, numeric operations, composition, concision

A substitution cipher is a code that simply replaces one character with another in a one-to-one fashion. This is the kind of code that must be broken when solving the typical newspaper puzzle called a “cryptogram”. A special case of this code is called a Caesar cipher, named for the Roman emperor Julius Caesar, who used it to communicate with his generals. A Caesar cipher simply shifts each character to another a certain number of places down the alphabet. In a Caesar cipher with a shift of 3, the letter A (character 0) would become D (character 3), P (character 15) would become S (character 18), and Y (character 24) would wrap-around to the front of the alphabet to become B (character 27, or, actually character 1).

With 26 characters in the Roman alphabet we use, there is a special Caesar cipher whose encryption algorithm is the same as the decryption algorithm. Since the Caesar cipher shifts things down the alphabet with wrap-around, if the shift is by 13 places, then it will also take another 13 place shift to “undo” the encryption. This form of the Caesar cipher is called a “ROT13” encryption, which is short for a “rotation” (or shift) by 13 places.

In our implementation, we will keep to capital letters A-Z only. We should first realize that characters in Scheme have a collating-sequence number. Fortunately, the collating-sequence numbers of A-Z are consecutive. However, they do not start at 0, which we will probably desire.

(a) Write, but do not document, a procedure, (shift-down x), that takes as its parameter the collating-sequence number of a capital Roman letter in U.S. English (A-Z), and returns an integer in the canonical range 0-25. You should make your definition as concise as possible.

> (shift-down (char->integer #\A))
0
> (shift-down (char->integer #\P))
15
> (shift-down (char->integer #\Z))
25

For the standard ASCII/Unicode collating sequence, you will see the following behavior.

> (shift-down 65)
0
> (shift-down 80)
15
> (shift-down 90)
25

Note: Your goal is to write a procedure that is independent of the collating sequence. Hence, you should not rely on the fact that capital A seems to have value 65 in both ASCII and Unicode. However, you may assume that capital letters are numbered sequentially in the collating sequence.

(b) Write, but do not document, a procedure (add-13 x) that takes an integer as its argument and simply adds thirteen to it. You should make your definition as concise as possible.

(c) Write, but do not document, a procedure, (wrap-26 x), that takes as its argument a non-negative integer and produces a new number that results from "wrapping around" at 26. In other words, a number no larger than 25 should be produced (corresponding to the letter Z) . The idea is to produce the "rotation" effect of the 26 characters of the alphabet. You should make your definition as concise as possible.

> (wrap-26 0)
0
> (wrap-26 11)
11
> (wrap-26 25)
25
> (wrap-26 26)
0
> (wrap-26 27)
1
> (wrap-26 38)
12
> (wrap-26 (+ 25 13))
12

(d) Write, but do not document, a procedure (shift-up x) that takes as its parameter an integer in the canonical range 0-25 and returns the corresponding collating-sequence number of a capital letter (A-Z). You should make your definition as concise as possible.

> (integer->char (shift-up 0))
#\A
> (shift-up 0)
65
> (integer->char (shift-up 15))
#\P
> (shift-up 15)
80
> (integer->char (shift-up 25))
#\Z
> (shift-up 25)
90

(e) Using the procedures from parts (a)-(d), write, but do not document, another procedure called char-rot13 that takes a character, and produces the ROT13-encoded character. You should make your definition as concise as possible.

> (char-rot13 #\A)
#\N
> (char-rot13 #\T)
#\G
> (char-rot13 (char-rot13 #\A))
#\A

Topics: Characters, strings, map

Write, but do not document, a procedure, (str-rot13 str), that takes a string containing only capital letters as a parameter and returns the ROT13 version of the string. You should make your code as concise as possible.

> (str-rot13 "HELLO")
"URYYB"
> (str-rot13 (str-rot13 "HELLO"))
"HELLO"

If you were not able to write char-rot13, you may instead use the following alternate, which simply returns the previous letter in the collating sequence.

(define char-dryrot
  (lambda (char)
    (integer->char (+ -1 (char->integer char)))))

If you choose to use char-dryrot, you should name your function str-dryrot.

> (str-dryrot "HELLO")
"GDKKN"

Topics: Iteration with repeat, turtles

You may recall that in our initial exploration of turtles, we wrote a simple procedure to make squares.

;;; Procedure:
;;;   turtle-square!
;;; Parameters:
;;;   turtle, a turtle
;;;   side-length, a positive number
;;; Purpose:
;;;   Create a square with the given side length
;;; Produces:
;;;   turtle, the same turtle
;;; Preconditions:
;;;   The turtle is within the bounds of its underlying image.
;;;   No boundary is closer than side-length.
;;; Postconditions:
;;;   The turtle is again in the same position, facing the same
;;;     direction.
;;;   The turtle's pen is down.
;;;   The image now contains a picture of a square, drawn with the
;;;     turtle's current brush and color.
;;;   The edges of the square are side-length (or fairly close,
;;;     depending on rounding.
;;;   One corner of the square is at the turtle's original position.
;;;   The first edge of the square is at the angle in which the turtle
;;;     is facing.
(define turtle-square!
  (lambda (turtle side-length)
    (turtle-down! turtle)
    (turtle-forward! turtle side-length)
    (turtle-turn! turtle 90)
    (turtle-forward! turtle side-length)
    (turtle-turn! turtle 90)
    (turtle-forward! turtle side-length)
    (turtle-turn! turtle 90)
    (turtle-forward! turtle side-length)
    (turtle-turn! turtle 90)))

Of course, squares are just one of many regular polygons. It seems that rather than writing one procedure for each type of polygon, we can develop something a bit more general.

Write, but do not document, a procedure, (turtle-polygon! turtle side-length sides), that uses a turtle to draw a regular polygon with the specified number of sides, with each side of the specified length.

You must use repeat to achieve repetition. You may not use recursion, map, or for-each.

In keeping with the spirit of turtle graphics, you may not use turtle-teleport!, turtle-face!, turtle-set-brush!, or turtle-set-color!.

Important: Your procedure must return the turtle to its original position and angle.

Hint: The turtle must turn a total of 360 degrees to return to its original angle.

Here are some examples. Note that since you cannot change the brush or color, the particular polygon you get will depend on the current state of the turtle.

(turtle-polygon! t 100 3)

(turtle-polygon! t 100 4)

(turtle-polygon! t 60 5)

(turtle-polygon! t 40 6)

Topics: Iteration with for-each, turtles, higher-order procedures

Write, but do not document, a procedure, (turtle-scale-polygon! turtle initial-side-length sides scale-factor copies), that draws the given number of copies of the specified polygon, with each copy drawn with a side length scale-factor times the previous side length.

For example, if the initial side length is ten, and the scale factor is two, this procedure would draw polygons with side lengths 10, 20, 40, 80, 160, ....

Similarly, if the initial side length is 100, and the scale factor is 0.9, the procedure would draw polygons with side lengths 100, 90, 81, 72.9, ....

You must use for-each to repeat the drawing of polygons. You may not use recursion, map, or repeat for this repetition. (You will likely also need repetition to draw an individual polygon. You may certainly call the turtle-polygon! procedure from the previous problem, even though it uses repeat.)

Important: As in the previous problem, your procedure must return the turtle to its original position and orientation and you may not use turtle-face!, turtle-teleport!, turtle-set-brush!, or turtle-set-color!.

Note: If you were not able to write the turtle-polygon! procedure, you may scale squares created using the turtle-square! procedure.

Hint: The expt function will be useful for finding the ratio of each polygon's side length to the original side length. For example, for scale factor two, the ratios would be 1, 2, 4, 8, 16, 32, and so on.

Here are some examples. Once again, your images may differ somewhat depending on the brush, color, initial position, and initial angle.

(turtle-scale-polygon! t 1 5 2 8)

(turtle-scale-polygon! t 1 5 1.2 30)

(turtle-scale-polygon! t 100 5 0.9 20)

Topics: List recursion, code reading, named let

Consider the following procedure that reveals poor choices in naming and formatting.

(define f (lambda (lst num) (let g ([a num] [str null] [b null]
[chr null]) (if (null? a) (list (reverse str) b (reverse chr)) (let
([c (cdr a)] [newlst (car a)]) (cond [(< newlst lst) (g c (cons
newlst str) b chr)] [(> newlst lst) (g c str b (cons newlst chr))]
[else (g c str (cons newlst b) chr)]))))))

Improve this procedure definition with the following steps.

First, reformat the procedure so that the indentation properly demonstrates nesting. That is, you should choose appropriate points to put in spaces and carriage returns. Remember that DrRacket will re-indent for you after you put in those returns, as long as you either (1) select the text and type Tab or (2) hit <Ctrl>-I. You should also make sure that let and cond statements have the appropriate square brackets.

Then figure out what the procedure does. You might analyze the code to understand it. You might run it and look at the results. You might do a combination of the two. You should not rely on the names of the parameters, which rarely (if ever) match their type.

After you've figured out what the procedure does, change the names in the procedure to clarify the roles of various things. You should certainly rename the procedure f, the parameters, and the local variables; all of these should have clear names that the average reader would understand. (As a hint, start by figuring out what type each parameter should be.)

Once you understand the code and have cleaned up the code, you are ready to write introductory comments (the six Ps) to explain the purpose (and the other Ps) of the procedure formerly named f. Don't forget that 6P-style documentation belongs before the procedure it documents.

Writing the introductory comments lets you reflect on necessary preconditions for the procedure. Finish your work by adding code that checks preconditions.

Topics: Numeric recursion, preconditions

As you may recall, we use the following template as our model for recursive procedures.

(define FUNC
  (lambda (PARAM)
    (if (SIMPLE? PARAM)
        (BASIC-RESULT PARAM)
        (COMBINE (EXTRACT-VALUE PARAM)
                 (FUNC (SIMPLIFY PARAM))))))

In most of the examples of numeric recursion we've explored, we use one of two mechanisms for simplifying the numeric parameter: We either repeatedly subtract 1 until we reach 0 (or 1), or we repeatedly add 1 until we reach some value.

But there are certainly other ways to get closer to our target. For example, we might multiply the original number by a fraction between 0 (inclusive) and 1 (exclusive) until we get a number that is pretty small (say less than or equal to 1). It turns out that “simplify by multiplication” can lead to some fairly fast procedures. Let's explore why.

Suppose we start with a parameter of 100 and each time we simplify the parameter by multiplying by 1/2. Our recursion will look something like the following

(func 100)
=> (... (func 50) ...)
=> (... (... (func 25) ...) ...)
=> (... (... (... (func 25/2) ...) ...) ...)
=> (... (... (... (... (func 25/4) ...) ...) ...) ...)
=> (... (... (... (... (... (func 25/8) ...) ...) ...) ...) ...)
=> (... (... (... (... (... (... (func 25/16) ...) ...) ...) ...) ...) ...)
=> (... (... (... (... (... (... (... (func 25/32) ...) ...) ...) ...) ...) ...) ...)

25/32 is less than 1, so we're done. So, for an input of 100, we did 7 recursive calls.

Is there a general formula for how many recursive calls you do given a starting value (100, in the example above) and a multiplier (1/2 in the example above)? Possibly. Let's start exploring the question by writing a procedure to count for us.

Write, but do not document, a recursive procedure, (count-reductions starting-value multiplier), that counts how many times we have to multiply starting-value by multiplier in order to get a value less than or equal to 1.

For example,

> (count-reductions 100 1/2)
7 ; see the example above
> (count-reductions 180 1/3)
5 ; 180 -> 60 -> 20 -> 20/3 -> 20/9 -> 20/27
> (count-reductions 1000 1/2)
10
> (count-reductions 1000 2/3)
18
> (count-reductions 0 8/9)
0 ; 0 is already less than or equal to 1
> (count-reductions 1 9/10)
0; 1 is already less than or equal to 1
> (count-reductions 500 3/2)
count-reductions: expects a multiplier at least 0 and less than 1, received 3/2
> (count-reductions 500 0)
1; 500 -> 0
> (count-reductions 500 1)
count-reductions: expects a multiplier at least 0 and less than 1, received 1

As the example suggests, your procedure should verify that the multiplier must be between 0 (inclusive) and 1 (exclusive). You should only check that precondition once.

Note that we can use this procedure to get a simple picture of how quickly different values simplify to zero.

;;; Procedure:
;;;   illustrate-reduction
;;; Parameters:
;;;   maxval, a positive integer
;;;   multiplier, a real number
;;;   colors, a list of irgb-colors
;;; Purpose:
;;;   Create a simple image that shows how many times we have to
;;;   multiply maxval by multiplier in order to get a number less
;;;   than or equal to 1.
;;; Produces:
;;;   illustration, an image
;;; Preconditions:
;;;   0 <= multiplier < 1 [unverified]
;;;   (length colors) > 2 [unverified]
;;; Postconditions:
;;;   (image-width illustration) = maxval+1
;;;   (image-get-pixel illustration i 0) is
;;;     (list-ref colors (mod (count-reductions i multiplier)
;;;                           (length colors)))
;;;   That is, each color transition indicates that one more multiplication
;;;     is necessary to reach a small value.  From another perspective, if
;;;     two neighboring pixels have the same color, the underlying values
;;;     require the same number of multiplications to reach a small value.
(define illustrate-reduction
  (lambda (maxval multiplier colors)
    (let ([numcolors (length colors)])
      (image-compute
       (lambda (col row)
         (let ([count (count-reductions col multiplier)])
           (list-ref colors (mod count numcolors))))
       (+ maxval 1) 20))))

;;; Values:
;;;   default-colors
;;;   rainbowish-colors
;;; Type:
;;;   Lists of irgb colors
;;; Summary:
;;;   List of irgb colors suitable for use by illustrate-reduction.
(define default-colors
  (list (irgb 255 255 255) (irgb 128 128 128) (irgb 0 0 0)))

(define rainbowish-colors
  (map color->irgb
       (list "white" "red" "orange" "yellow" "green" 
             "blue" "indigo" "violet" "black")))

	(illustrate-reduction 250 0.4 default-colors)
	(illustrate-reduction 250 0.5 default-colors)
	(illustrate-reduction 250 0.6 default-colors)

As these images suggest, once the numbers get high enough, huge swaths of values all require the same number of reductions. For example, with a factor of 0.5, both 130 and 250 require the same number of reductions. If the range is that big, the implication is that there will be comparatively few reductions, since each reduction brings us to a new section.