Exam 4: Higher, deeper, faster

Note: This examination is still in draft format. Expect a few changes or additions before its release on Wednesday. Corrections will not be accepted until Thursday.

Assigned: Wednesday, 29 November 2017

Prologue Due: Friday, 1 December 2017 by 10:30 p.m.

Exam Due: Thursday, 7 December 2017 by 10:30 p.m.

Cover Sheet Due: Friday, 8 December 2017 by the start of class

Epilogue Due: Friday, 8 December 2017 by 10:30 p.m.

Please read the exam procedures page for policies, turn-in procedures, and grading details. If you have any questions about the exam, check the Q&A at the bottom of this page. We will generally spend some time in class every day on questions and answers while the exam is in progress.

While the exam is out, please check back periodically to see if we have reported any new errata.

Complete the exam using the exam04.rkt starter source code. Please rename this file to 000000.rkt, but replace 000000 with your generated random number.

Prologue

The prologue for this examination will be via email, which you should send to your instructor. Your message should be titled CSC 151.03: Exam 4 Prologue (your name).

1. For each problem, please include a short note about something that will help you solve the problem. Mostly, we want to see some evidence that you’ve thought about the problem. You might note some similar procedures you’ve written or problems you’ve solved in the past (e.g., in a lab or on a homework assignment). You might note procedures that you expect to use. You might sketch an algorithm. You might pose a question to yourself. (We won’t necessarily read this in a timely fashion, so if you have questions for your instructor, you should ask by email or in person.)

   If, when looking at a problem, you think you already know the answer, you can feel free to write something short like “solved” or “trivial”.

2. Which of those six problems do you expect to be the most difficult for you to solve? Why?

3. You should only do one of problem 5 and problem 6. Which do you plan to attempt on the exam? Why did you choose that one?

4. Conclude by answering the question What is an approach that you expect will help you be successful on this exam? For example, you might suggest that you will work thirty minutes on the exam each day, or work on the exam at 7pm each day, when your brain is most able to process information. (Note that it is perfectly fine to just repeat what you wrote in the epilogue for the prior exam.)

Epilogue

The epilogue for this examination will also be via email, which you should send to your instructor. Your message should be titled CSC 151.03: Exam 4 Epilogue (your name). Include answers to the following questions.

1. What was the most difficult part of the exam?

2. What made that part difficult?

3. What are two things you would recommend to next semester’s CSC 151 students as they undertake these exams?

Some important notes

There are six problems on this examination. You should do problems 1–4 and then either problem 5 or problem 6. If you submit both problems 5 and 6, we will score both and you will receive the lower of the two scores you get on those two problems.

You will note that the exam code template has the line (require csc151/trees) and (require csc/counters). You will likely need to update your csc151 package for those lines to work.

Problem 1: Fixing list-set

Topics: analysis and efficiency, list recursion

In a recent examination, we asked students to write a procedure to set the kth element of a list. Since not all students had reflected on the costs of various operations, some turned in some fairly inefficient solutions. Here are versions of two of them.

(define list-set-one
  (lambda (lst pos val)
    (letrec ([kernel
              (lambda (index lst1 pos1 val1)
                (cond
                  [(= index (length lst))
                   null]
                  [(= index pos)
                   (cons val (kernel (increment index) lst pos val))]
                  [else
                   (cons (list-ref lst index)
                         (kernel (increment index) lst pos val))]))])
      (kernel 0 lst pos val))))

(define list-set-two
  (lambda (lst pos val)
    (let kernel ([so-far null]
                 [remaining lst])
      (cond
        [(null? remaining)
         so-far]
        [(equal? (length so-far) pos)
         (kernel (append so-far (list val))
                 (cdr remaining))]
        [else
         (kernel (append so-far (list (car remaining)))
                 (cdr remaining))]))))

a. Describe, in your own words, any potential inefficiencies in each of these two procedures.

b. Rewrite the two procedures to be more efficient. You may not significantly change the logic of the procedures. However, you may add extra parameters (or remove unused parameters). In the case of list-set-two, you may also find it useful to use reverse once or twice.

Problem 2: Tallying nested lists

Topics: Deep recursion, Higher-order programming, Tallying

We have written a large number of procedures that tally values. At this point, you should be ready to generalize those procedures. Write, but do not document, a recursive procedure, (nested-list-tally lst pred?) that counts the number of elements in lst (or sublists of lst, or sublists of sublists of lst, or …) for which pred? holds. You may assume that your procedure only receives correctly formed nested lists. You may also assume that the predicate is not list?, pair?, null? or anything similar.

> (nested-list-tally null odd?)
0
> (nested-list-tally (list (list 1 2) 3 4 (list (list 5) 6)) odd?)
3
> (nested-list-tally (list "a" (list 2 "b" 3) "c" (list 4 "d") "e") string?)
5

You may not use filter or length, even if you implement them yourself.

Problem 3: Filtering vectors

Topics: vectors, vector recursion, higher-order procedures, filtering

Document and write a procedure, (vector-filter vec pred?), that creates a new vector which contains only the elements of vec for which pred? holds. The elements should appear in the same order that they do in vec.

In writing this procedure, you may create exactly one new vector. Hence, you will not find it productive to use vector-append. In addition, you may not create any lists. Hence, you will not find it productive to use list->vector or vector->list.

Hint: You may have to iterate the vector twice, once to determine the size of the result vector and once to fill it in.

Problem 4: Finding the next larger value

Topics: vectors, binary search

Write, but do not document, a procedure (next-larger val vec) that uses binary search to find the smallest value in the sorted vector vec that is larger than val (we call that the “next larger” value). Documentation for this procedure is included below:

;;; Procedure:
;;;   next-larger
;;; Parameters:
;;;   val, a real number
;;;   vec, a vector of real numbers
;;; Purpose:
;;;   Find the smallest value in vec that is greater than val
;;; Produces:
;;;   result, a real number or #f.
;;; Preconditions:
;;;   vec is a vector of real numbers sorted from smallest to largest
;;; Postconditions:
;;;   If vec contains a number greater than val, then result is the
;;;     smallest such number.
;;;   If vec does not contain a number greater than val, then result is #f.

Here are a few examples.

> (next-larger 4 '#(2 4 6 8 10 12))
6

> (next-larger 100 '#(1 3 10 29))
#f

> (next-larger 10 '#(7 8 9 10))
#f

> (next-larger 0 '#(100 200 300 400))
100

> (next-larger 225 '#(100 200 300 400))
300

> (next-larger 5 '#(3 4 5 5 5 7))
7

> (next-larger 1.5 '#(1.5 2 3.5 4 9/2 5 6.0))
2

> (next-larger -1 '#(0 1 2 3))
0

> (next-larger -1 '#(-5 -3 -1 2 3 17.2 18.5 21 22))
2

You may find the following variant of binary search useful as a starting point.

;;; Procedure:
;;;   binary-search-reals
;;; Parameters:
;;;   vec, a vector of real numbers
;;;   num, a real number
;;; Purpose:
;;;   Search vec for num.
;;; Produces:
;;;   pos, an integer
;;; Preconditions:
;;;   * The vector is "sorted".  That is, for all reasonable i,
;;;     (<= (vector-ref vec i) (vector-ref vec (+ i 1)))
;;;     holds for all reasonable i.
;;; Postconditions:
;;;   * If vector does not contain num, pos is -1.
;;;   * If vec contains an element equal to num, pos is the
;;;     index of one such value.  That is,
;;;     num = (vector-ref vec pos)
;;;   * Does not modify vec.
(define binary-search-reals
  (lambda (vec num)
    ; Search a portion of the vector from lower-bound to upper-bound
    (let search-portion ([lower-bound 0]
                         [upper-bound (- (vector-length vec) 1)])
      ; If the portion is empty
      (if (> lower-bound upper-bound)
          ; Indicate the value cannot be found
          -1
          ; Otherwise, identify the middle point, the element at that
          ; point and the key of that element.
          (let* ([point-of-division (quotient (+ lower-bound upper-bound) 2)]
                 [separating-element (vector-ref vec point-of-division)])
            (cond
              ; If the middle value equals the value, we use the position
              ; of the middle value.
              [(= num separating-element)
               point-of-division]
              ; If the middle value is too large, look in the left half
              ; of the region.
              [(< num separating-element)
               (search-portion lower-bound (- point-of-division 1))]
              ; Otherwise, the middle element must be too small, so look
              ; in the right half of the region.
              [else
               (search-portion (+ point-of-division 1) upper-bound)]))))))

Problem 5: Flattening trees

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

We’ve seen how to turn vectors into trees. But what if we want to do the reverse? In particular, what if we want to “flatten” a tree back into a linear structure, such as a list? 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 (empty? tree)
        null
        (list-append (tree-flatten (left tree))
                     (cons (contents tree)
                           (tree-flatten (right tree)))))))

And here’s the procedure in action.

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

You may be worried that the procedure is potentially inefficient because it uses list-append. 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.

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

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

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

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

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

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

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

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-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t2) (counter-print cons-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t3) (counter-print cons-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t4) (counter-print cons-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t5) (counter-print cons-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t6) (counter-print cons-count
er)
'#("cons" 0)
'(1 2 3 4)
cons: 4
> (counter-reset! cons-counter) (tree-flatten-new t7) (counter-print cons-count
er)
'#("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. Your helper might look something like the following (although you may decide to make it local).

;;; Procedure:
;;;   partial-flatten
;;; Parameters:
;;;   tree, a tree
;;;   partial, a list
;;; Purpose:
;;;   Flatten tree and add it to the front of partial.  Assume that 
;;;   partial represents everything that should appear after tree in
;;    the flattened original tree.
;;; Produces:
;;;    more-flattened, a list.

Problem 6: Whatzitdo?

Topics: code reading, documentation, sorting

Consider the following poorly designed (but correctly indented) procedures.

(define ioe
  (lambda (a / b)
    (let * ([c (decrement b)]
            [d b])
      (if (and (< c (increment c))
               (<= c (square c))
               (or (negative? c)
                   (negative? (increment c))
                   (negative? (square c))))
          d
          (let ([new-c (vector-ref a d)]
                [new-d (vector-ref a c)]
                [new-a (vector-ref a (quotient (+ d c) 2))]
                [new-b (+ c (- c (increment c)))])        
            (if (and (<= c d)
                     (/ new-d new-c))
                (* new-b c)
                (* new-b d)))))))

(define vss! 
  (lambda (? +)
    (let kernel [(/ (- (vector-length ?) 1))]
      (when (>= / 0)
        (let* ([a (ioe ? + /)]
               [b (vector-ref ? a)])
          (vector-set! ? a (vector-ref ? /))
          (vector-set! ? / b)
          (kernel (- / 1)))))))

Figure out what the procedures do and then.

a. Rename the procedures, parameters, and local variables to use meaningful names. You should use the DrRacket rename feature or you will likely get lost.

b. Remove useless code. (There’s a lot of it in the first procedure.)

c. Document the revisited procedures.

Hint: Read the topics. They should help you figure out one of the parameters to the vss! procedure.

Questions and answers

We will post answers to questions of general interest here while the exam is in progress. Please check here before emailing questions!

Initial questions and answers

These questions and answers were provided in the initial release of the examination.

What is a general question?

A question that is about the exam in general, not a particular problem.

Do all the sections have the same exam?

Yes.

Can we still invoke the “There’s more to life” clause if we spend more than five hours on the exam?

Yes. However, we really do recommend that you stop at five hours unless you are very close to finishing. It’s not worth your time or stress to spend more effort on the exam. It is, however, worth your time to come talk to us, and perhaps to get a mentor or more help (not on this exam, but on the class). There’s likely some concept you’re missing, and we can help figure that out.

How do we know what our random number is?

You should have received instructions on how to generate your random number on the day the exam was distributed. If you don’t have a number, ask your professor for one before submitting your exam.

To show we’ve tested the code informally, would you just like us to just post the inputs we used to test the procedure? If so, how should we list those?

Copy and paste the interactions pane into the appropriate place in the definitions pane. Select the text. Under the Racket menu, use “Comment out with semicolons.” You should have at least three examples or tests per procedure you write.

Should we cite our partner from a past lab or assignment if we use code from a past lab or assignment?

You should cite both yourself and your partner, although you should do so as anonymously as possible. For example “Ideas taken from the solution to problem 7 on assignment 2 written by student 641321 and partner.”

If we write a broken procedure and replace it later, should we keep the previous one?

Yes! This will help us give you partial credit if your final procedure isn’t quite right. But make sure to comment out the old one with semicolons and perhaps add a note or two as to what you were trying.

Do I need to document helper procedures?

You must document helpers using the 4Ps.

If I write a helper procedure for one of the problems that does not require me to document the primary procedure, do I need to document the helper?

Yes. All non-local helpers should be documented with the 4P’s.

Do I have to document local helper procedures?

It’s nice if you write a one-line comment that explains what they do, but you certainly don’t need 4P’s.

What’s a local helper procedure?

One defined within the procedure, most typically with a letrec or a named let.

Can I use procedures that we have not covered in class?

Probably not. Ask about individual procedures if you’re not sure.

DrRacket crashed and ate my exam. What do I do?

Send your instructor the exam file and any backups that DrRacket seems to have made. (Those tend to have a similar file name, but with pound signs or tildes added at the front or back.)

How do I know when you’ve added a new question or answer?

We try to add a date stamp to the questions and answers.

Should we cite readings from the CSC 151 Web site? If so, how much information should we give.

Yes. The title and URL should suffice.

Can I use some other websites (different from our class websites) to solve problems in the exam?

As the exam policies page states, “This examination is open book, open notes, open mind, open computer, open Web.” Note that it also states “ If you find ideas in a book or on the Web, be sure to cite them appropriately.”

But be sure that the other Web sites rely on the procedures you’ve learned and follow the Scheme style we use.

Do we have to cite the exam itself?

No.

How do I generate a random six digit number?

(random 1000000)

How do I submit my exam?

Name it 012345.rkt (substituting your random number)

Send it to your instructor, not the grader, as an attachment in an email message entitled “CSC 151 Exam 2” (or something similar)

How many points will I lose if I don’t do the prologue?

Somewhere between 2 and 5, depending on the mood of the grader.

How many points will I lose if I do the prologue late?

Somewhere between 0 and 5, depending on the mood of the grader.

How many points will I lose if I don’t do the epilogue?

Somewhere between 2 and 5, depending on the mood of the grader.

How many points will I lose if I do the epilogue late?

Somewhere between 0 and 5, depending on the mood of the grader.

How many points will I lose if I don’t use the required template?

Somewhere between 0 and 50, depending on the mood of the grader.

Will I lose points if I fail to indent my code correctly with ctrl-i?

Almost certainly.

How many points will I lose if I fail to indent my code correctly?

It depends on how hard your code is to read.

Can you provide a sample time log?

Sure.

; Time Log:
;   Date        Start   Finish  Elapsed Activity
;   2017-09-15  18:00   18:20   20 min  Wrote four tests
;   2017-09-15  20:30   21:00   30 min  Three non-working versions
;                                       (marked as a, b, and c below).
;                                       Decided to sleep on it.
;   2017-09-16  08:00   08:10   10 min  Woke up with an idea.  Coded it.
;                                       it seems to work
;   2017-09-16  19:00   19:10   10 min  A few more tests just to make
;                                       sure.  Done!

Do I have to use YYYY-MM-DD format?

Certainly. Why would you use anything else?

Do I get the bonus points for errors if I successfully invoke “There’s more to life”?

Nope.

Do I lose points for missing prologue/epilogue and other similar issues if I successfully invoke “There’s more to life”?

Yes.

What do you consider the hardest problem or problems on the exam?

We’ll answer this question after all of the prologues are submitted.

New general questions

These questions and answers were added after the initial release of the examination.

Questions on problem 1

How much of the original should I preserve? [2017-12-04, ca. 8:00 a.m.]

As much as possible. For example, your solution to the first problem should continue to (a) use letrec, (b) have a tripartite cond, and (c) return the original list when given an index out of bounds.

Questions on problem 2

Any hints? [2017-12-04, ca. 8:00 a.m.]

“Trust the magic recursion fairy.” Use direct recursion. Assume that the tally procedure will succeed on the cdr. Assume that you can use it on any sublist. Work from there.

Questions on problem 3

Should this procedure return anything? [2017-12-04, ca. 8:00 a.m.]

Yes. The procedure builds a new vector. It should return that vector.

Can I modify the original vector? [2017-12-04, ca. 8:00 a.m.]

No.

Questions on problem 4

Does this have to work with negative numbers? [2017-12-04, ca. 8:00 a.m.]

Yes.

Any hints? [2017-12-04, ca. 8:00 a.m.]

Make a list of cases.

Make sure that you try all of the examples we’ve given you.

Questions on problem 5

Any hints on part e? [2017-12-04, ca. 8:00 a.m.]

The problem suggests writing a helper that keeps track of the flattened version of everthing that will appear to the right. That’s a good strategy. Start with the empty list.

Questions on problem 6

I keep getting the same result when I call ioe. Is that intentional? [2017-12-04, ca. 8:00 a.m.]

If you use the correct parameters, you should get a variety of results. Perhaps you should figure out vss! first and see how it calls ioe.

Errata

Please check back periodically in case we find any new issues.

• The procedure nested-list-tally was inconsistently named in the problem and exam starter file. [HL, +1 point]
• The procedure counter-print does not have an exclamation point. [HL, +1 point]
• In problem four, “we” appears as “wel”. [LY, +1 point]
• In problem one, it appears that the students you copied the code from forgot to press ctrl-i. [IDK, +1 point]
• There’s no question mark on pred? in the sample code file. [Various, +0 points]
• When Sam added extra examples to next-larger, one of them was syntactically incorrect. [KB, +1 point]

Citations

Some of the problems on this exam are based on (and at times copied from) problems on previous exams for the course. Those exams were written by Charlie Curtsinger, Janet Davis, Rhys Price Jones, Titus Klinge, Samuel A. Rebelsky, John David Stone, Henry Walker, and Jerod Weinman. Many were written collaboratively, or were themselves based upon prior examinations, so precise credit is difficult, if not impossible.

Some problems on this exam were inspired by conversations with our students and by correct and incorrect student solutions on a variety of problems. We thank our students for that inspiration. Usually, a combination of questions or discussions inspired a problem, so it is difficult and inappropriate to credit individual students.