Exam 4: Higher, Deeper, and Faster

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

Since there is a lot of utility code in the examination (placed at the end in the template), make a copy of your exam and remove that utility code before printing.

You must also submit the code for your examination at http://bit.ly/151-2015S-exam4. 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. Monday, your physical copy will be submitted in class on Tuesday. 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 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 documentation 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: Testing, assoc

In writing tests, we are too often biased by the code we've written, that we see, or that we plan to write. But good tests can and should be written independent of the code being tested.

A few years ago, one of my colleagues wrote a new-and-improved, but not quite correct, version of assoc. More recently, I attempted to rewrite that version, relying on a variety of student implementations of assoc. My version was also not quite correct.

Your goal in this problem is to write a test suite for assoc that will find the errors in erroneous versions, but will not find errors in the standard version of assoc.

How can you access this new version? There are two steps.

First, in the terminal, type the following.

/opt/racket/bin/raco link /home/rebelsky/share/CSC151-2015S

Second, when you want to use the new (and perhaps not-so-improved) version of assoc, you will write the following in the definitions pane.

(require CSC151-2015S/a-sock)

We have manually tested this procedure using the following input, and it appears to work correctly:

> (assoc 5 (list (cons 1 2) (cons 3 4) (cons 5 6) (cons 7 8)))
'(5 . 6)
> (assoc 1 (list (cons 1 2) (cons 3 4) (cons 5 6) (cons 7 8)))
'(1 . 2)
> (define colors
    (list (list "red" (list 255 0 0))
          (list "purple" (list 255 0 255))
          (list "green" (list 0 128 0))
          (list "blue" (list 0 0 255))
          (list "black" (list 0 0 0))
          (list "white" (list 255 255 255))
          (list "grey" (list 128 128 128))))
> (assoc "blue" colors)
'("blue" (0 0 255))

Unfortunately, a few experiments are not enough. In fact, as noted above, the implementation has several bugs.

Using the RackUnit library, write a complete test suite for assoc, as documented in the reading on association lists. Call your test suite assoc-tests.

Your test suite should identify at least four different ways in which the buggy procedure produces an incorrect result. (It produces incorrect results in at least five ways, one of which is quite subtle. You may receive extra credit for finding the most subtle issue.)

Hint: Think about the many issues we explored in playing with assoc.

Topics: assoc, higher-order procedures

We've seen that it's possible to use assoc to search a table for a value. We've also seen that in some cases, we want to “hard-code” the table.

Write, but do not document, a procedure, table->lookup that takes as input a list of pairs of the form that assoc expects and returns a procedure of one parameter. The returned function should take a key as a value and either (a) return the cdr of the entry corresponding to that key, if such an entry exists or (b) issue an error message if the entry does not exist.

Here are a few examples.

> (define lookup-grinnell-CS100
    (table->lookup (list (cons "CSC105" "The Digital Age")
                         (cons "CSC151" "Functional Problem Solving")
                         (cons "CSC161" "Imperative Problem Solving")
                         (cons "CSC195" "Special Topics"))))
> (lookup-grinnell-CS100 "CSC161")
"Imperative Problem Solving"
> (lookup-grinnell-CS100 "CSC105")
"The Digital Age"
> (lookup-grinnell-CS100 "CSC100")
. . Could not find "CSC100"
> (define cname->rgb-list
    (table->lookup (list (list "black" 0 0 0)
                         (list "white" 255 255 255)
                         (list "grey" 128 128 128)
                         (list "blue" 0 0 255)
                         (list "red" 255 0 0)
                         (list "green" 0 128 0))))
> (cname->rgb-list "red")
'(255 0 0)
> (cname->rgb-list "puce")
. . Could not find "puce"
> (cname->rgb-list "white")
'(255 255 255)

Here's some 6P-style documentation for table->lookup for those of you who find it helpful to see such documentation.

;;; Procedure:
;;;   table->lookup
;;; Parameters:
;;;   table, a list of pairs
;;; Purpose:
;;;   Create a lookup function for the table
;;; Produces:
;;;   lookup, a unary function
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   If there is an entry of table whose car is key, (lookup key) is the
;;;     cdr of the first such entry.
;;;   If there is no such entry, (lookup key) issues an error of the form
;;;     "Could not find ..."

Hint: You should use assoc in your definition.

Topics: Higher-order procedures, repetition, numeric recursion

We frequently write the following pattern to do a series of actions with side effects.

(for-each (lambda (i)
            (_________ (* __ (+ __ i))))
          (iota __))

While this model is concise and readable, it also requires us to build a list that we don't really need, and perhaps even to do a bit of extra computation in turning the i values into the values we really want.

Write, but do not document, a procedure, (iterate proc! initial final offset), that calls proc! on initial, then calls proc! on initial+offset, then calls proc! on initial+offset+offset, and so on and so forth until we exceed final.

> (iterate (lambda (val) (display val) (display " "))
           7 11 1)
7 8 9 10 11 
> (iterate (lambda (val) (display val) (display " "))
           10 70 10)
10 20 30 40 50 60 70 
> (iterate (lambda (val) (display val) (display " "))
           7 70 10)
7 17 27 37 47 57 67 
> (iterate (lambda (val) (display val) (display " "))
           11 7 1)
; No output, because 7 is less than 11
> (iterate (lambda (val) (display val) (display " "))
           -20 -10 2)
-20 -18 -16 -14 -12 -10 

Although the examples all use a procedure that displays the values, any procedure is possible. We will more frequently use this procedure with turtles and other commonly-used operations with side effects.

Here's the for-each version of turtle-spiral!.

(define turtle-spiral!
  (lambda (turtle amt length)
    (for-each (lambda (angle)
                (turtle-forward! turtle amt)
                (turtle-turn! turtle angle))
              (cdr (iota (+ length 1))))))

In contrast, here's the improved version using iterate.

(define turtle-spiral!
  (lambda (turtle amt length)
    (iterate (lambda (angle)
               (turtle-forward! turtle amt)
               (turtle-turn! turtle angle))
             1 length 1)))

Hint: Use a local kernel that keeps track of the current parameter to proc!.

Topics: Deep recursion, predicates, documentation

In the material above, we introduced a new model of trees, one in which the empty tree is called nil and we make new trees with node. Using this new model, we might write the following definition of trees.

We've found it useful to use the list? predicate. Unfortunately, there is no such predicate for this new form of trees.

Document and write a predicate, (tree? val), that holds when val meets the preceding definition of trees. You will be judged not only on the correctness of the solution, but also its concision and elegance of expression.

Here are some examples of that procedure in use.

> (tree? nil)
#t
> (tree? (node 0 nil nil))
#t
> (tree? (node 0 1 nil))
#f
> (tree? (node 0 nil 1))
#f
> (tree? (node 0 (node 1 nil nil) nil))
#t
> (tree? (node 0 (node 1 nil nil) (node 2 nil nil)))
#t
> (tree? (node 0 (node 1 nil (node 3 nil nil)) (node 2 nil nil)))
#t
> (tree? (node 0 (node 1 nil (node 3 nil 5)) (node 2 nil nil)))
#f
> (tree? (cons 1 2))
#f
> (tree? null)
#f

Hint: We've written concise and elegant predicates to test if a pair structure is a list and if a pair structure is a number tree. Refer back to those predicates.

Topics: Vectors, divide-and-conquer, numeric recursion

You've discovered how to determine if a value is a tree. But how do we build trees in the first place? One option is to start with a vector and build a tree by repeatedly dividing the vector in half. For example, given the vector #("this" "sample" "vector" "contains" "seven" "string" "values"), we'd note that "contains" is in the middle position, so it will be the top value in the tree. We'll then turn "this", "sample", and "vector" into the left subtree and "seven", "string", and "values" into the right subtree. For the left subtree, "sample" will be at the top, with "this" as its left subtree and "vector" as its right subtree.

Write, but do not document, a procedure, (vector->tree vec) that turns a vector into a tree using that strategy.

> (vector->tree (vector "this" "sample" "vector" "contains" "seven" "string" "values"))
'#(node
   "contains"
   #(node "sample" #(node "this" nil nil) #(node "vector" nil nil))
   #(node "string" #(node "seven" nil nil) #(node "values" nil nil)))
> (vector->tree (vector "this" "sample" "vector" "contains" "six" "values"))
'#(node
   "vector"
   #(node "this" nil #(node "sample" nil nil))
   #(node "six" #(node "contains" nil nil) #(node "values" nil nil)))
> (vector->tree (vector))
'nil
> (vector->tree (vector "aardvark"))
'#(node "aardvark" nil nil)
> (vector->tree (vector "aardvark" "baboon"))
'#(node "aardvark" nil #(node "baboon" nil nil))
> (vector->tree (vector "aardvark" "baboon" "chinchilla"))
'#(node "baboon" #(node "aardvark" nil nil) #(node "chinchilla" nil nil))
> (vector->tree (vector "aardvark" "baboon" "chinchilla" "dingo"))
'#(node
   "baboon"
   #(node "aardvark" nil nil)
   #(node "chinchilla" nil #(node "dingo" nil nil)))
> (vector->tree (vector "aardvark" "baboon" "chinchilla" "dingo" "emu"))
'#(node
   "chinchilla"
   #(node "aardvark" nil #(node "baboon" nil nil))
   #(node "dingo" nil #(node "emu" nil nil)))
> (vector->tree 
   (vector "aardvark" "baboon" "chinchilla" "dingo" "emu" "fox"))
'#(node
   "chinchilla"
   #(node "aardvark" nil #(node "baboon" nil nil))
   #(node "emu" #(node "dingo" nil nil) #(node "fox" nil nil)))

Hint: You may want to write a kernel that keeps track of the boundaries of the portion of the vector you are currently converting.

Topics: Trees, binary search

What happens if we use vector->tree on a sorted vector, such as the kind we used for binary-search? We get a tree with two interesting characteristics. First, the keys of the entries in the left subtree all may precede the key of the root value, and the key of the root value may precede the keys of all the entries in the right subtree. Second, each subtree has the same characteristic. Basically “smaller things are in the left subtree, larger things are in the right subtree”. Trees with these characteristics are called binary search trees

Write, but do not document, a procedure, (bst-find key bst), that looks for the entry with the given key in the binary search tree bst. You can assume that each entry in the tree has the form (key . value), that the key is a string, and that the key/value pairs are organized as described, with smaller keys in the left subtree and larger keys in the right subtree.

The provided code in the examination includes a variety of sample binary search trees, including animals (animal names, indexed by letter of the alphabet), cs-faculty-first (CS faculty names, indexed by first name), cs-faculty-last (CS faculty names, indexed by last name), and some-grinnell-courses (some Grinnell courses, indexed by course id, such as "CSC151").

As the images suggest, not all binary search trees are perfectly balanced, but all binary search trees follow the organizational principal. As long as they follow that principal, we can search.

> (bst-find "P" animals)
"Polar Bear"
> (bst-find "Z" animals)
"Zorilla"
> (bst-find "J" animals)
"Jackalope"
> (bst-find "a" animals)
. . Could not find "a"
> (bst-find "Sam" cs-faculty-first)
"Rebelsky"
> (bst-find "Samuel" cs-faculty-first)
. . Could not find "Samuel"
> (bst-find "Weinman" cs-faculty-last)
"Jerod"
> (bst-find "Sam" cs-faculty-last)
. . Could not find "Sam"
> (bst-find "SST295" some-grinnell-courses) ; Duplicate keys
"Real Life Entrepreneurship"
> (bst-find "POL295" some-grinnell-courses)
"Intro to Network Analysis"
> (bst-find "CSC299" some-grinnell-courses)
. . Could not find "CSC299"

Hint: When you encounter a tree node, check its key and then recurse on either the left or right subtree.

Topics: Trees, deep recursion, program analysis, code reading

In an earlier problem, we turned a vector into a tree. But sometimes we want to “flatten” trees back into linear structures, such as lists. Here's a procedure that does just that.

;;; Procedure:
;;;   tree-flatten
;;; Parameters:
;;;   tree, a tree
;;; Purpose:
;;;   "Flatten" the tree into the corresponding list.
;;; Produces:
;;;   lst, a list
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   Every value in the tree appears in the list.
;;;   No additional values appear in the list.
;;;   The values are in the same order in the list as they are
;;;     in the tree.  (Things in the left subtree appear before
;;;     the value in a node, which appears before things in the
;;;     right subtree.
(define tree-flatten
  (lambda (tree)
    (if (nil? tree)
        null
        (list-append (tree-flatten (left-subtree tree))
                     (cons (root-value tree)
                           (tree-flatten (right-subtree tree)))))))

And here's the procedure in action.

> (tree-flatten (node
                 "chinchilla"
                 (node "aardvark" 
                       nil 
                       (node "baboon" nil nil))
                 (node "emu" 
                       (node "dingo" nil nil) 
                       (node "fox" nil nil))))
'("aardvark" "baboon" "chinchilla" "dingo" "emu" "fox")

You may be worried that the procedure is potentially inefficient because it uses list-append, and you'd be right to be worried.

a. Update list-append and tree-flatten so that you can count the calls to cons.

b. Find the number of calls to cons for each of the following trees. You may also find it useful to visualize each of the trees with a command like (visualize-tree t3 200 200).

(define t1
  (node 4 (node 3 (node 2 (node 1 nil nil) nil) nil) nil))

(define t2
  (node 3 (node 2 (node 1 nil nil) nil) (node 4 nil nil)))

(define t3
  (node 3 (node 1 nil (node 2 nil nil)) (node 4 nil nil)))

(define t4
  (node 2 (node 1 nil nil) (node 4 (node 3 nil nil) nil)))

(define t5
  (node 2 (node 1 nil nil) (node 3 nil (node 4 nil nil))))

(define t6
  (node 1 nil (node 2 nil (node 3 nil (node 4 nil nil)))))

(define t7
  (node 1 nil (node 3 (node 2 nil nil) (node 4 nil nil))))

c. Which tree seems to require the most calls to cons? Why does it require so many calls?

d. Which tree seems to require the fewest call to cons? Why does it require so few calls?

e. Write a new version of tree-flatten (which you should call tree-flatten-new) in which the number of calls to cons is the same as the number of values in the list.

> (counter-reset! cons-counter) (tree-flatten-new t1) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t2) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t3) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t4) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t5) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t6) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t7) (counter-print! cons-counter)
'#("cons" 0)
'(1 2 3 4)
cons: 4

Hint: You will find that you will require fewer calls to cons if you (a) write a helper that permits you to pass around a partially flattened tree and (b) flatten the right half of the tree before the left half.