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 seven problems on this examination. Each problem is worth the same number of points. Although each remaining problem is worth the same amount, problems are not necessarily of equal difficulty.

Please 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” on the cover sheet of the examination and you will earn at least the equivalent of 70% on this exam, provided you recorded the time spent on each problem, filled in the prologue by the specified deadline, filled in the epilogue, 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, but not the time you spend on the epilogue.. 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 and recording time are not usually applied in the second situation, but penalties (e.g., for failing to number pages) usually are.

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 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 (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, physically and electronically.

For the physical copy, you must write all of your answers using the computer, print them out, number the pages, staple them together (except for the cover sheet), and hand me the printed copy. For your benefit and for ours, we are doing blind grading on this examination, so you have been assigned a number to use on your exam. Please make sure that your number appears at the top of every page. You should turn in a separate cover sheet along with your stapled and printed answers. The cover sheet should 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, and (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.

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.

You must also submit the code for your examination at http://bit.ly/151-2015S-exam3. Ideally, you would put all of the code for the exam in a single Racket file. However, if you have created separate files for the separate parts of the exam, you can just paste them one after another when you submit, provided you put a clear separator, such as ; PROBLEM 2, between sections.

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 provide 6P-style documentation for each primary procedure you write. Most helper procedures should be local, in which case you need only document them with a sentence or so. If you write any non-local helper procedures, you must document them with 6P-style documetation using at least the first four P's (Procedure, Purpose, Parameters, Produces).

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.

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

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

Topics: Named let, precondition testing

Consider the following procedure which intentionally lacks explicit preconditions and postconditions.

;;; Procedure:
;;;   pos-to-neg
;;; Parameters:
;;;   lst, a list
;;; Purpose:
;;;   To compute the ratio of positive to negative values in lst
;;; Produces:
;;;   ratio, a rational number
(define pos-to-neg
  (lambda (lst)
    (let kernel ([pos 0]
                 [neg 0]
                 [remaining lst])
      (cond
        [(null? remaining)
         (/ pos neg)]
        [(positive? (car remaining))
         (kernel (+ 1 pos) neg (cdr remaining))]
        [(negative? (car remaining))
         (kernel pos (+ 1 neg) (cdr remaining))]
        [else
         (kernel pos neg (cdr remaining))]))))

Here are a few simple examples of the procedure in action.

> (pos-to-neg (list 1 2 3 -1))
3
> (pos-to-neg (list 5 0 -1))
1
> (pos-to-neg (list -1 -2 3 -4 5))
2/3
> (pos-to-neg (list 0 -7 0))
0

Determine a comprehensive set of preconditions for pos-to-neg and add a husk to pos-to-neg to check all of these preconditions. Any error messages generated by a call to pos-to-neg should come from your husk, and not from an inappropriate call to some other procedure. That is, I should not see errors generated by addition, subtraction, division, car, cdr, cons, positive?, null? and other similar functions.

Topics: Direct recursion over lists

As you may recall from the previous exam, the rac procedure is intended to find the last element in a list and the rdc procedure is intended to extract all but the last element of a list.

It is possible to implement both rac and rdc with a call to reverse. But that's inefficient as it requires us to build a list that we will then modify. It is also possible to implement rac using list-ref with an index of one less than the length of the list. But that's also inefficient, since we have to traverse the list twice, once to find its length, and once to extract the element.

So, what should we do? Not so surprisingly, we can implement both rac and rdc recursively.

Write recursive versions of rac and rdc. You should use direct recursion and should not use any helper procedures. (Note: “direct recursion” is what we have also called “basic recursion”.)

You need not document either procedure.

Topics: Numeric recursion, Gimp tools

Some forms of line art play with the ways in which our brains interpret the world. One popular approach is to trick our brains into seeing curves when all we have is a bunch of straight lines. We've explored that approach a bit in making spirals and circles using turtle graphics. Here's a variant. Draw lines between (0,y) and (x,height-1) in which y ranges from 0 to (height-1) and x ranges from 0 to (width-1). In each case, you should space the values consistently (either along the left edge or the top edge).

Write, but do not document, a procedure, (mesh image n), that draws those lines using the current brush and color.

Here are some examples that assume we've set the brush to radius 10 and the color to blue.

> (context-set-brush! "2. Hardness 050" 10)
> (context-set-fgcolor! "blue")

	(mesh (image-show (image-new 200 200)) 5)
	(mesh (image-show (image-new 200 100)) 5)
	(mesh (image-show (image-new 100 150)) 10)

Topics: Turtle graphics, using actions, for-each

Sometimes it's useful to make lists of actions for a turtle to complete. For example, to make a triangle, we can have "forward 10, turn 120, forward 10, turn 120, forward 10". In Scheme, we might represent each action as a one-parameter procedure. For example, (r-s turtle-forward! 10) or (lambda (t) (turtle-teleport! t 100 100)).

Write, but do not document, a procedure, (turtle-script! turtle script!) that has the turtle follow a script, where the script is a list of one-parameter procedures.

Make your definition concise and clear. You may not use explicit recursion.

Here's the documentation for turtle-script!.

;;; Procedure:
;;;   turtle-script!
;;; Parameters:
;;;   turtle, a turtle
;;;   script, a list of one-parameter functions
;;; Purpose:
;;;   Have turtle execute the actions in script one by one
;;; Produces:
;;;   turtle, the same turtle
;;; Preconditions:
;;;   script has the form '(action1! ... actionn!)
;;;   Each action is a procedure of one parameter that takes a turtle
;;;     as input.
;;; Postconditions:
;;;   The following actions have been executed in turn
;;;     (action1! turtle)
;;;     (action2! turtle)
;;;     ...
;;;     (actionn! turtle)

Here are a few examples.

	(turtle-script! (turtle-new (image-show (image-new 200 200))) (list (lambda (t) (turtle-teleport! t 100 50)) (r-s turtle-face! 90) (r-s turtle-forward! 80) (r-s turtle-set-color! "red") (r-s turtle-turn! -45) (r-s turtle-forward! 30) (r-s turtle-set-color! "grey") (r-s turtle-turn! -90) (r-s turtle-forward! 60) (r-s turtle-set-color! "blue") (r-s turtle-face! 180) (r-s turtle-forward! 100)))
	(define side-script (list (r-s turtle-forward! 100) (r-s turtle-turn! 90))) (define square-script (append (list (lambda (t) (turtle-teleport! t 50 50)) (r-s turtle-set-color! "green")) side-script side-script side-script side-script)) (turtle-script! (turtle-new (image-show (image-new 200 200))) square-script)

Topics: Turtle-graphics, repeat

A “sparkle” is a set of evenly spaced radial lines, with a long line and a short line opposite each other.

Using turtles, write and document a procedure, (turtle-sparkle! turtle spokes long short).

You may find the following procedures helpful for design or testing.

;;; Procedure:
;;;   sample-turtle
;;; Parameters:
;;;   [None]
;;; Purpose:
;;;   Create a new turtle at the center of a new 200x200 world
;;; Produces:
;;;   turtle, a turtle
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (turtle-angle turtle) = 0
;;;   (turtle-x turtle) = 100
;;;   (turtle-y turtle) = 100
;;;   (image-width (turtle-world turtle)) = 200
;;;   (image-height (turtle-world turtle)) = 200
(define sample-turtle
  (lambda ()
    (turtle-teleport! (turtle-new (image-show (image-new 200 200)))
                      100 100)))

;;; Procedure:
;;;   turtle-line!
;;; Parameters:
;;;   turtle, a turtle
;;;   length, a real number
;;; Purpose:
;;;   Draw a line of the given length, using the turtle's current
;;;   direction, brush, and color.
;;; Produces:
;;;   t, the same turtle 
;;; Preconditions:
;;;   turtle is in a valid state (e.g., on an existing image)
;;; Postconditions:
;;;   The image now contains a line, drawn using the turtle's direction,
;;;     brush, and color.
;;;   The turtle is back in its original position, facing in the same way, 
;;;     with the same brush and color.
;;;       (turtle-world t) = (turtle-world turtle)
;;;       (turtle-angle t) = (turtle-angle turtle)
;;;       (turtle-x t) = (turtle-x turtle)
;;;       (turtle-y t) = (turtle-y turtle)
;;;       (turtle-brush t) = (turtle-brush turtle)
;;;       (turtle-brush-size t) = (turtle-brush-size turtle)
;;;       (turtle-color t) = (turtle-color turtle)
;;;   The turtle's brush is down.
(define turtle-line!
  (lambda (turtle length)
    (turtle-script! turtle
                    (list (r-s turtle-forward! length)
                          turtle-up!
                          (r-s turtle-turn! 180)
                          (r-s turtle-forward! length)
                          (r-s turtle-turn! 180)
                          turtle-down!))))

; An alternate version of turtle-line! for those who don't
; implement turtle-script!
(define turtle-line-alt!
  (lambda (turtle length)
    (turtle-forward! turtle length)
    (turtle-up! turtle)
    (turtle-turn! turtle 180)
    (turtle-forward! turtle length)
    (turtle-turn! turtle 180)
    (turtle-down! turtle)))

Here are some examples.

	(turtle-sparkle! (sample-turtle) 3 75 50)
	(turtle-sparkle! (sample-turtle) 5 45 70)
	(turtle-sparkle! (sample-turtle) 7 75 30)

Topics: Pairs and pair structures, code reading, deep recursion, predicates, documentation

The following higher-order procedure does something with trees.

(define tt
  (lambda (t p?)
    (cond
       [(pair? t)
        (+ (tt (car t) p?)
           (tt (cdr t) p?))]
       [(p? t)
        1]
       [else
        0])))

Document this procedure. Pay particular attention to the purpose of the procedure, which explains what the procedure computes, not how it does that computation.

Topics: Numeric recursion, list recursion, local recursive procedures.

Implement a procedure, (list-indices lst val), which returns a list of all of the indices of val in lst. Documentation for list-indices follows.

;;; Procedure:
;;;   list-indices
;;; Parameters:
;;;   lst, a list
;;;   val, a value
;;; Purpose:
;;;   Find all of the indices of val in lst.
;;; Produces:
;;;   indices, a list of non-negative integers
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   Every i in indices is a valid index into lst.  That is,
;;;     if (member? i indices), then (< 0 i (- (length lst) 1))
;;;   Every i in indices is an index of val in lst. That is,
;;;     if (member? i indices), then (equal? val (list-ref lst i))
;;;   Every appearance of val in lst has a corresponding index
;;;   in indices.  That is,
;;;     if (equal? val (list-ref lst j)), then (member? j indices)
;;;   indices is in order from smallest to largest.  That is
;;;     (< (list-ref indices k) (list-ref indices (+ k 1))) for
;;;     all reasonable k.

Here are some examples.

> (list-indices (list "a" "b" "c" "d") "a")
'(0)
> (list-indices (list "a" "b" "c" "d") "d")
'(3)
> (list-indices (list "a" "b" "a" "c" "a" "b") "a")
'(0 2 4)
> (list-indices (list 3 1 4 1 5 9 2 6) 1)
'(1 3)
> (list-indices (list "a" 1 "and" 'a 2 "and" 'a 3) "and")
'(2 5)
> (list-indices (list "a" 1 "and" 'a 2 "and" 'a 3) "a")
'(0)
> (list-indices (list "a" 1 "and" 'a 2 "and" 'a 3) 'a)
'(3 6)
> (list-indices (list "a" "b" "c" "d") "not present")
'()

Here's a test suite.

;;; Name:
;;;   list-indices-tests
;;; Type:
;;;   Test suite
;;; Value:
;;;   Tests for the list-indices procedure.
;;; Usage:
;;;   (run-tests list-indices-tests)
(define list-indices-tests
  (test-suite
   "Tests of list-indices"

   (test-case
    "empty lists"
    (check-equal? (list-indices null "a") null "a")
    (check-equal? (list-indices null 'a) null "'a")
    (check-equal? (list-indices null 123) null "123")
    (check-equal? (list-indices null null) null "null"))

   (test-case
    "singleton lists"
    (check-equal? (list-indices (list "a") "a") '(0) "a in (a)")
    (check-equal? (list-indices (list "a") "b") null "b in (a)")
    (check-equal? (list-indices (list "a") 1) null "1 in (a)")
    (check-equal? (list-indices (list 1) 1) '(0) "1 in (1)")
    (check-equal? (list-indices (list 1) "a") null "a in (1)")
    (check-equal? (list-indices (list 1) 2) null "2 in (1)"))

   (test-case 
    "Each position in a list of strings"
    (check-equal? (list-indices (list "a" "b" "c" "d") "a")
                  '(0)
                  "element 0")
    (check-equal? (list-indices (list "a" "b" "c" "d") "b")
                  '(1)
                  "element 1")
    (check-equal? (list-indices (list "a" "b" "c" "d") "c")
                  '(2)
                  "element 2")
    (check-equal? (list-indices (list "a" "b" "c" "d") "d")
                  '(3)
                  "last element")
    (check-equal? (list-indices (list "a" "b" "c" "d") "e")
                  '()
                  "not present"))

   (test-case
    "Homogeneous lists, various types"
    (check-equal? (list-indices (list "a" "b" "a" "c" "a" "b") "a")
                  '(0 2 4)
                  "multiple appearances, string")
    (check-equal? (list-indices (list 3 1 4 1 5 9 2 6) 1)
                  '(1 3)
                  "multiple appearances, integer, neither first nor last")
    (check-equal? (list-indices (list 1/2 1/3 1/2 1/4 1/5 1/2) 1/2)
                  '(0 2 5)
                  "multiple appearances, fraction, first and last")
    (check-equal? (list-indices (list 'a 'b 'c 'd) 'b)
                  '(1)
                  "one appearance, symbol, middle")
    (check-equal? (list-indices (list null (list 1) null null (list 2) null) 
                                null)
                  '(0 2 3 5)
                  "first, last, neighbor, lists of lists"))

   (test-case
    "Lists of lists of integers"
    (let ([loloi (list null       ; 0
                       (list 1)   ; 1
                       null       ; 2
                       (list 1 2) ; 3 
                       (list 1 2) ; 4
                       (list 12)  ; 5 
                       null       ; 6
                       (list 1 2) ; 7
                       (list 1)   ; 8
                       (list 2))]); 9
      (check-equal? (list-indices loloi null) 
                    '(0 2 6)
                    "null")
      (check-equal? (list-indices loloi (list 1)) 
                    '(1 8)
                    "(1)")
      (check-equal? (list-indices loloi (list 2)) 
                    '(9)
                    "(2)")
      (check-equal? (list-indices loloi (list 1 2)) 
                    '(3 4 7)
                    "(1 2)")
      (check-equal? (list-indices loloi (list 12)) 
                    '(5)
                    "(12)")
      (check-equal? (list-indices loloi (list 1 2 3))
                    '()
                    "(1 2 3)")))

   (test-case
    "heterogeneous lists"
    (let ([het (list "a" 1 "and" 'a 2 "and" 'a 3 "make" 'a "six")])
      (check-equal? (list-indices het "a")
                    '(0)
                    "a")
      (check-equal? (list-indices het 1)
                    '(1)
                    "1")
      (check-equal? (list-indices het "and")
                    '(2 5)
                    "and")
      (check-equal? (list-indices het 'a)
                    '(3 6 9)
                    "'a")
      (check-equal? (list-indices het "six")
                    '(10)
                    "six")))

   (test-case
    "all elements"
    (check-equal? (list-indices (make-list 10 2) 2) (iota 10) "ten 2's")
    (check-equal? (list-indices (make-list 30 "a") "a") (iota 30) "thirty a's")
    (check-equal? (list-indices (make-list 5 (list 1 2 3)) (list 1 2 3)) 
                  (iota 5) 
                  "five lists"))

   (test-case
    "no appearances"
    (check-equal? (list-indices (iota 100) "a") null "a in (iota 100)")
    (check-equal? (list-indices (iota 1000) 1000) null "1000 in (iota 1000)")
    (check-equal? (list-indices (iota 500) -1) null "-1 in (iota 1000)"))))