Exam 4: Sophisticated Scheming

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 an optional prologue due by the Wednesday before the exam is due. It is intended to help you get started thinking about the examination. While the prologue is optional, if you intend to invoke the “there's more to life” option (see below), you must submit the prologue by the specified deadline.

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 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 (1) submitted the prologue by the specified deadline, and (2a) show evidence of serious effort on at least six of the problems or (2b) come to talk to me within a week of submitting the exam about the difficulties you had. 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 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. 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.

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.

For the physical copy, 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. For your benefit and for ours, we are doing blind grading on this exam, so please do not put your name on any page beside the cover sheet.

The code and comments in your printed copy must use a fixed-width (a.k.a., monospaced or fixed-pitch) font; viable candidates (depending on your platform) 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 email me a copy of your exam with the subject CSC 151-02 Exam 4. 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. 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 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. (We would prefer that you use the six P's, but won't require it.)

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

Topics: Sorting, vectors, numeric recursion, higher-order procedures

The famous selection sort algorithm for sorting vectors works by repeatedly stepping through the vector from back to front, swapping the largest remaining thing to the next place in the vector. We might express that algorithm for a vector of strings as

(define vector-selection-sort!
  (lambda (vec may-precede?)
    (let kernel [(pos (- (vector-length vec) 1))]
      (when (>= pos 0)
        (let* [(index (vector-index-of-extreme vec pos may-precede?))
               (largest (vector-ref vec index))]
          (vector-set! vec index (vector-ref vec pos))
          (vector-set! vec pos largest)
          (kernel (- pos 1)))))))

Of course, we will need the procedure vector-index-of-extreme, which we might document as follows.

;;; Procedure:
;;;   vector-index-of-extreme
;;; Parameters:
;;;   vec, a vector
;;;   pos, an integer
;;;   may-precede?, a procedure that compares two values for order
;;; Purpose:
;;;   Find the index of the extreme value in the subvector of 
;;;   vec at positions [0..pos].
;;; Produces:
;;;   index-of-extreme, an integer
;;; Preconditions:
;;;   pos >= 0.
;;;   (vector-length vec) > pos.
;;;   may-precede? can be applied to any two values in vector
;;;   may-precede? represents a transitive operation
;;; Postconditions:
;;;   For all i from 0 to pos, inclusive,
;;;     (may-precede? (vector-ref vec i) (vector-ref vec index-of-extreme))

For example,

> (define claim (vector "computers" "are" "sentient" "and" "malicious" "on" "tv"))
> (vector-index-of-extreme claim 6 string<=?)
6
> (vector-ref claim 6)
"tv"
> (vector-index-of-extreme claim 6 string>=?)
3
> (vector-ref claim 3)
"and"
> (vector-index-of-extreme claim 5 string<=?)
2
> (vector-ref claim 2)
"sentient"
> (vector-selection-sort! claim string<=?)
> claim
'#("and" "are" "computers" "malicious" "on" "sentient" "tv")
> (define shorter? (lambda (x y) (<= (string-length x) (string-length y))))
> (vector-selection-sort! claim shorter?)
> claim
'#("on" "tv" "and" "are" "sentient" "computers" "malicious")
> (define numbers (vector 301 151 161 207 321 211 213))
> numbers
'#(301 151 161 207 321 211 213)
> (vector-selection-sort! numbers <=)
> numbers
'#(151 161 207 211 213 301 321)
> (vector-selection-sort! numbers >=)
> numbers
'#(321 301 213 211 207 161 151)
> (define second-digit (lambda (val) (modulo (quotient val 10) 10)))
> (define smaller-second-digit?
    (lambda (x y)
          (<= (second-digit x) (second-digit y))))
> (vector-selection-sort! numbers smaller-second-digit?)
> numbers
'#(301 207 211 213 321 151 161)

Implement the vector-index-of-extreme procedure.

Hint: We've looked for extreme values before, such as the brightest color in a list.

Topics: Higher-order procedures, procedures as return values, comparison.

In the previous problem, we built two new procedures for comparing values: (shorter? x y) and (smaller-second-digit? x y).

The two procedures have very similar definitions.

(define smaller-second-digit?
  (lambda (x y)
    (<= (second-digit x) (second-digit y))))
(define shorter?
  (lambda (x y)
    (<= (string-length x) (string-length y))))

When we have similar definitions, we want to write a general form. Define a procedure, (make-comparison convert), that takes as input a function from some kind of values to numbers and returns a function of two values that applies convert to each of those values and then compares the results with <=.

;;; Procedure:
;;;   make-comparison
;;; Parameters:
;;;   convert, a function from values to numbers
;;; Purpose:
;;;   Build a mechanism for comparing values.
;;; Produces:
;;;   may-precede?, a binary predicate
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   (may-precede? x y) = (<= (convert x) (convert y))

Once we've defined make-comparison, it's much easier to write the two previous procedures.

(define smaller-second-digit? (make-comparison second-digit))
(define shorter? (make-comparison string-length))

In fact, we may not even need to define those two procedures. We can just use make-comparison in our calls to vector-selection-sort! and other procedures.

> (define lists (vector (list) (iota 5) (make-list 3 2) (make-list 2 3)))
> lists
'#(() (0 1 2 3 4) (2 2 2) (3 3))
> (vector-selection-sort! lists (make-comparison length))
> lists
'#(() (3 3) (2 2 2) (0 1 2 3 4))
> (define complex (vector 1+5i 2+4i 3+1i 7+3i 8+2i 4+0i))
> (imag-part 1+5i)
5
> (real-part 1+5i)
1
> (vector-selection-sort! complex (make-comparison real-part))
> complex
'#(1+5i 2+4i 3+1i 4 7+3i 8+2i)
> (vector-selection-sort! complex (make-comparison imag-part))
> complex
'#(4 3+1i 8+2i 7+3i 2+4i 1+5i)
> (imag-part 4)
0

Implement make-comparison.

Topics: Trees, randomness, deep recursion

At times, it can be useful to generate a tree with “unpredictable” structure, and with either predictable or known contents.

For example, given the four values 1, 2, 3, and 4, we can build four different trees that have those four values in order.

Write, but do not document, a procedure, (simple-random-tree size value) that makes a tree with size leaves, each of which has value value and whose shape is difficult to predict. You may assume that size is at least 1.

> (simple-random-tree 1 'a)
'a
> (simple-random-tree 2 'a)
'(a . a)
> (simple-random-tree 2 'a)
'(a . a)
> (simple-random-tree 4 'a)
'((a . a) a . a)
> (simple-random-tree 4 'a)
'(((a . a) . a) . a)
> (simple-random-tree 4 'a)
'((a . a) a . a)
> (simple-random-tree 4 'a)
'(a a a . a)

Hint: If size is greater than 1, you know that each subtree must have size at least 1. (That also tells you something about the maximum size of the other subtree.)

Hint: If you know the total size and you know the desired size of the left subtree, then you can figure out the desired size of the right subtree.

Hint: You can use random to randomly choose the size (number of leaves) in the left subtree. Of course, you should identify a reasonable range for that size.

Topics: Trees, deep recursion

You should be familiar with the reverse procedure, which, given a list, creates a new list of the same length and the same elements, but with the elements in the reverse order.

Write, but do not document, a procedure, (deep-reverse value), that “reverses” a list, tree, value, or tree-like structure by reversing the two subtrees and then cons-ing them together in reverse order.

> (deep-reverse null)
'()
> (deep-reverse 'a)
'a
> (deep-reverse (cons 'a 'b))
'(b . a)
> (deep-reverse (cons 'a (cons 'b 'c)))
'((c . b) . a)
> (deep-reverse (cons (cons 'a 'b) 'c))
'(c b . a)
> (deep-reverse (cons 'c (cons 'b 'a)))
'((a . b) . c)
> (deep-reverse (cons (cons 'a 'b) (cons 'c 'd)))
'((d . c) b . a)
> (deep-reverse (list 'a 'b 'c))
'(((() . c) . b) . a)
> (deep-reverse (list (list 'a 'b) (list 'c 'd)))
'((() (() . d) . c) (() . b) . a)

Topics: Trees, deep recursion, efficiency

As you know from experience with recursion, a bit of carelessness can make a recursive procedure run very slowly. We find that procedures that traverse trees and similar structures are particularly subject to such difficulties. Hence, we have a particular responsibility to carefully analyze such procedures.

a. Create a new version of deep-reverse that allows you to determine how many calls to cons might be made in reversing a tree of size n. (You should check direct calls as well as any implicit calls you make by, say, calling append or make-list.) You may certainly use the analysis tools that were included as part of the reading and lab on analysis, but you must be sure to cite those resources if you include the corresponding tools.

b. Determine the number of calls to cons involved in using deep-reverse to reverse lists of length 0, 1, 2, 4, 8, 16, and 32. (Make sure to show the code you used to answer this question.) For an input of size n, how many calls do you predict? What leads you to that conclusion?

c. As we saw in problem 3, given a size, we can build a wide variety of shapes of trees that have that size. Make four different trees of size 6 (that is, with six leaves) and see whether your deep-reverse makes the same number of calls to cons on each one. (Make sure to include the code that you wrote to answer this question.) If the number of calls your procedure makes depends on the shape of the tree, explain why. If the number of calls your procedure makes does not depend on the shape of the tree, explain why not.

Alternate: If you are not able to implement deep-reverse, you may instead analyze the following procedure.

(define deep-something
  (lambda (tree)
    (if (pair? tree)
        (cons (deep-something (car tree))
              (deep-something (cdr tree)))
        tree)))

Topics: Vector mutation, recursion in vectors

Document and write a procedure, (vector-reverse! vec), that reverses a vector in place, swapping the first and last elements, the second and penultimate elements, and so on and so forth.

> (define vec1 (vector 'a 'b 'c 'd 'e))
> (define vec2 (list->vector (iota 8)))
> (vector-reverse! vec1)
> vec1
#(e d c b a)
> (vector-reverse! vec2)
> vec2
#(7 6 5 4 3 2 1 0)
> (vector-reverse! vec2)
> vec2
#(0 1 2 3 4 5 6 7)

You may not use the list-based reverse procedure in solving this problem. You may not create additional vectors or lists in solving this problem.

Topics: Binary search, testing

Some people find the version of binary search that appears in the reading problematic for a variety of reasons.

Some find it to be a bit too complex, what with the get-key and may-precede? and everything. So, they might want a simple procedure that simply finds the index of a string in a sorted vector of strings.

Others are bothered by the fact that if a string appears multiple times, we aren't sure which one we will get. They'd like us to get the last one. If we put these two approaches together, we might end up with the following procedure.

;;; Procedure:
;;;   binary-search-strings
;;; Parameters:
;;;   strings, a sorted vector of strings
;;;   str, a string
;;; Purpose:
;;;   Finds the last index of str in strings
;;; Produces:
;;;   index, an integer
;;; Preconditions:
;;;   For all i, 0 < i < (vector-length strings)
;;;     (string-ci<=? (vector-ref strings (- i 1)) (vector-ref strings i))
;;; Postconditions:
;;;   -1 <= index < (vector-length strings)
;;;   If there is no string equal to str (ignoring case), then index is -1.
;;;   Otherwise, (vector-ref vec index) is equal to str (ignoring case) and
;;;    (vector-ref vec (+ index 1)) is not equal to string (or invalid).
(define binary-search-strings
  (lambda (strings str)
    (let search-portion ([lower-bound 0]
                         [upper-bound (- (vector-length strings) 1)])
      ; The following line is useful when we're experimenting
      ; (display (list 'search-portion lower-bound upper-bound)) (newline)
      
      ; If the portion is empty
      (cond
        ; If the two bounds are equal, we've found it.
        [(= lower-bound upper-bound)
         lower-bound]
        ; If the lower-bound is beyond the upper bound, it's
        ; not there
        [(> lower-bound upper-bound)
         -1]
        ; Otherwise, look at the middle element and decide what
        ; to do next.
        [else
         (let* ([midpoint (quotient (+ lower-bound upper-bound) 2)]
                [middle-string (vector-ref strings midpoint)])
           (if (string-ci<? str middle-string)
               ; If the goal is smaller, look to the left.
               (search-portion lower-bound (- midpoint 1))
               ; Otherwise, look to the right
               (search-portion midpoint upper-bound)))]))))

> (binary-search-strings (vector "a" "b" "c" "d") "b")
1
> (binary-search-strings (vector "a" "b" "c" "d" "e") "c")
2
> (binary-search-strings (vector) "a")
-1

Of course, we'd like to be sure that the procedure works correctly.

Write a test suite for binary-search-strings. You should make sure to try a variety of sizes of arrays, a variety of locations for the copies of the value, and so on and so forth. Note that because we also return -1 when the value does not appear in the vector, we should look for values that might be found near different locations (e.g., not just something smaller than everything in the vector or larger than everything in the vector).

Hint: You will find it useful to pre-build a few vectors and then use them for your tests.

Hint: For a three-element vector with no repeated elements, there are seven possible tests in which you know the output. Make sure that you do all of those seven tests.

Hint: There are three three-element vectors with repeated elements. Make sure you test each of those.

Note: If your test suite runs forever on some inputs, the binary search procedure probably has infinite recursion. The fault is likely the procedure's, and not the test suite's. In the next problem, you will address the problems in the procedure.

Topics: Binary search, code reading

This implementation of binary-search-strings has at least two bugs. Presumably, your test suite identified those bugs.

If you were not able to write a test suite, try a variety of examples by hand to see if you can see times in which the procedure fails to behave as expected.

Once you have identified potential errors, correct the code.

Hint: If you're not sure what's going wrong, you can uncomment the lines that display each call to kernel.