Exam 4: Higher, deeper, faster

Assigned: Wednesday, 2 May 2018

Prologue Due: Friday, 4 May 2018 by 10:30 p.m.

Exam Due: Tuesday, 8 May 2018 by 10:30 p.m.

Cover Sheet Due: Wednesday, 9 May 2018 by the start of class

Epilogue Due: Wednesday, 9 May 2018 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.01: 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 problems do you expect to be the most difficult for you to solve? Why?

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

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.01: 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 all six problems.

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

Problem 1: Subvector

Topics: vectors, vector recursion

Many data types such as lists and strings can be broken down into smaller parts using procedures like drop, take, and substring. Similarly, vectors can naturally be broken down into subvectors.

Document and write a procedure, (subvector vec i j), that takes a vector and two indices and returns a new vector that contains exactly the elements of vec between the indices i (inclusive) and j (exclusive). In writing this procedure, you may create exactly one new vector, and you may not use any lists. Hence, you will not find it productive to use vector-append, list->vector, or vector->list.

Below are several example calls to subvector.

> (subvector #(7 2 5 4 1) 0 2)
'#(7 2)
> (subvector #(7 2 5 4 1) 3 5)
'#(4 1)
> (subvector #("a" "e" "c") 0 1)
'#("a")
> (subvector #("a" "e" "c") 2 2)
'#()
> (subvector #("a" "e" "c") 0 3)
'#("a" "e" "c")

Problem 2: Filtering trees

Topics: Trees

Filtering data has been fundamental to our investigation of datasets. In particular, we have used the (filter pred? lst) procedure to select elements out of lists that meet the criteria of pred?. However, it is sometimes more appropriate to use other data structures such as vectors or trees. Filtering elements out of these structures is just as useful.

Write but do not document a procedure (tree-select tree pred?) that takes a tree and a predicate as parameters and produces a list of all the elements in tree that satisfy the predicate pred?. You must recurse over the tree directly; you may not first turn the tree into a list.

Here are a few examples.

> (define tree1 (node 4 (node 2 (leaf 1) (leaf 3)) (node 6 (leaf 5) (leaf 7))))
> (define tree2 (node "a" (node 2 empty (leaf "b")) (node 12.7 (leaf "c") empty)))
> (define tree3 empty)
> (tree-select tree1 odd?)
'(1 3 5 7)
> (tree-select tree1 even?)
'(2 4 6)
> (tree-select tree2 number?)
'(2 12.7)
> (tree-select tree2 string?)
'("b" "a" "c")
> (tree-select tree3 even?)
'()

Extra Credit: The most straightforward implementation of tree-select is not the most efficient. Therefore, solutions that run in linear time in the number of elements in the tree will receive a modicum of extra credit.

Problem 3: File append

Topics: Files, File recursion

We have often combined lists and vectors together using the append and vector-append procedures. Similarly, it is helpful to append two files together to produce a new file.

Write but do not document a procedure (file-append file1 file2 dst-file) that takes three strings as input (representing the paths to three separate files) and writes the contents of the first two files to the third file. The contents of the first file should precede the contents of the second file, similar to how (append lst1 lst2) places the contents of lst1 before the contents of lst2. Your procedure may open each of the three files exactly once.

Problem 4: Whatzitdo?

Topics: vectors and vector recursion, higher-order procedures, code reading, documentation

Consider the following interesting procedure definition.

(define dead-boys-song
  (lambda
    (*)
  (lambda
    (/)                                          (letrec ([+
  (lambda
    (list)                                       (or (and (=
      list
      (- (vector-length /) 1)) (vector-ref / list))
      (* (vector-ref / list)
      (+ (increment list)))))]) (+ 0)))))

Determine what this procedure does and reformat it so that it follows reasonable standards. (For example, the parameter to a lambda should be on the same line as the lambda, the first parameter to any procedure should be on the same line as that procedure, the remaining parameters to a procedure should be on separate lines with the same indent.)

a. Rename the procedure, parameters, and local variables so that they will make sense to the reader.

b. Write 6P-style documentation for the renamed procedure. Please place that documentation immediately before the procedure.

c. This procedure has three lambdas. Explain the role of each.

Problem 5: Indices of large values

Topics: lists, algorithm analysis, recursion

Consider the following procedure which generalizes index-of-largest to find the indices of all the largest values, rather than just the single largest value.

;;; Procedure:
;;;   indices-of-largest
;;; Parameters:
;;;   lst, a nonempty list of real numbers
;;; Purpose:
;;;   Find the indices of the largest values in lst
;;; Produces:
;;;   indices, a list of integers
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * indices is nonempty
;;;   * Every value in indices is between 0 and (- (length lst) 1), inclusive.
;;;   * For any i in indices, j not in indices, where j is a valid index of lst,
;;;     (> (list-ref lst i) (list-ref lst j)).
(define indices-of-largest
  (lambda (lst)
    ; The kernel builds up the list of indices.
    ; pos represents the next position we have to
    ; look at
    (let kernel ([indices (list 0)]
                 [pos 1])
      (cond
        ; If we're out of elements, just use the list we've built
        [(>= pos (length lst))
         indices]
        ; If the position is already in the list of indices, skip it
        [(member? pos indices)
         (kernel indices
                 (+ pos 1))]
        ; If the element at the given position is bigger than
        ; the biggest we've seen, start again with just that
        ; position.
        [(> (list-ref lst pos)
            (list-ref lst (car indices)))
         (kernel (list pos)
                 0)]
        ; If the element at the given position is equal to
        ; the biggest we've seen, add it to the list of
        ; indices.
        [(= (list-ref lst pos)
            (list-ref lst (car indices)))
         (kernel (append indices (list pos))
                 (+ pos 1))]
        ; Otherwise, the element at the given position
        ; is smaller than something we've seen, so
        ; ignore it
        [else
         (kernel indices
                 (+ pos 1))]))))

The procedure appears to be correct.

> (check-equal? (indices-of-largest (list 5 4 3 2 1))
                '(0))
> (check-equal? (indices-of-largest (list 2 5 4 3 1))
                '(1))
> (check-equal? (indices-of-largest (list 1 2 5 4 3))
                '(2))
> (check-equal? (indices-of-largest (list 1 2 4 5 3))
                '(3))
> (check-equal? (indices-of-largest (list 4 3 2 1 5))
                '(4))
> (check-equal? (indices-of-largest (list 1))
                '(0))
> (check-equal? (indices-of-largest (list 2 0 -1 2 1 2))
                '(0 3 5))
> (check-equal? (indices-of-largest (list -1 -1 -1 -1))
                '(0 1 2 3))
> (check-equal? (indices-of-largest (list 0 1 2 3 2 1 3 2 1))
                '(3 6))

However, warning bells have likely gone off in your head because there are many components of the procedure that we’ve identified as inefficient programming practices. There are also a few strange programming choices.

a. Indicate which parts of the procedure are likely to be inefficient.

b. Rewrite this procedure so that it is more efficient. You should keep as much of the general logic as you can, but eliminate or revise code that is inefficient. You may find that you need to add parameters to the kernel, add one or more let statements, and even do a bit of extra processing when you hit the base case.

c. Summarize the changes you’ve made to the procedure and why you made those changes.

Note: When you fix one of the subtle but important inefficiencies in the code, you should also be able to remove one of the five cases in the cond statement.

Problem 6: Analyzing quicksort

Topics: sorting, lists, algorithm analysis

You’ve learned one sorting mechanism that applies the divide-and-conquer technique to achieve faster sorting: merge sort. But merge sort is not the only divide-and-conquer sorting algorithm. There’s a famous alternative called Quicksort. While Quicksort is normally done with vectors, we’ll consider a list-based version.

Merge sort divides the elements without considering the values of the elements. Can we perhaps gain power by looking at the values? Consider the problem of sorting a list of integers. If we knew the median value, we could break the list into three lists: the values less than the median, the values equal to the median, and the values greater than the median. Once we’ve done that, we can recursively sort the list of smaller values and the list of larger values and then append the three together.

Suppose we had the list '(5 2 9 1 3 8 0 4 2 7 5). The median value is 4. So we separate it into three lists.

• Values less than 4: '(2 1 3 0 2)
• Values equal to 4: '(4)
• Values greater than 4: '(5 9 8 7 5)

We sort the two lists. (How? Recursively!)

• Values less than 4, sorted: '(0 1 2 2 3)
• Values equal to 4: '(4)
• Values greater than 4: '(5 5 7 8 9)

And then we join everything together with append, giving us '(0 1 2 2 3 4 5 5 7 8 9).

How do we write this procedure? It’s fairly straightforward. First, we’ll write the procedure that separates the list into three parts.

;;; Procedure:
;;;   partition
;;; Parameters:
;;;   lst, a list of real numbers
;;;   num, a real number
;;; Purpose:
;;;   Separate lst into three lists: things less than num, things equal
;;;   to num, and things greater than num.
;;; Produces:
;;;   vol, a vector of lists of real numbers of the form 
;;;     #(smaller equal greater).
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * (append smaller equal greater) is a permutation of lst.
;;;   * All values in smaller are less than num.
;;;   * All values in equal are equal to num.
;;;   * All values in greater are larger than num.
(define partition
  (lambda (lst num)
    (let kernel ([remaining lst]
                 [smaller null]
                 [equal null]
                 [greater null])
      (if (null? remaining)
          (vector smaller equal greater)
          (let [(val (car remaining))]
            (kernel (cdr remaining)
                    (if (< val num) (cons val smaller) smaller)
                    (if (= val num) (cons val equal) equal)
                    (if (> val num) (cons val greater) greater)))))))

Next, we will write the primary Quicksort procedure.

;;; Procedure:
;;;   quicksort
;;; Parameters:
;;;   lst, a list of real numbers
;;; Purpose:
;;;   Sort the list using the legendary quicksort algorithm.
;;; Produces:
;;;   sorted, a list
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * sorted is a permutation of lst.  No elements are added or removed.
;;;   * sorted is sorted.  For all reasonable i, (list-ref sorted i) <=
;;;     (list-ref sorted (+ i 1)).
(define quicksort
  (lambda (lst)
    (if (or (null? lst) (null? (cdr lst)))
        lst
        (let [(parts (partition lst (median lst)))]
          (append (quicksort (vector-ref parts 0))
                  (append (vector-ref parts 1)
                          (quicksort (vector-ref parts 2))))))))

How do we find the median value of a list of real numbers? It turns out that that’s a hard problem. The normal approach is “sort the list and look in the middle”. But that doesn’t work if we’re using the median to sort. The typical implementation of Quicksort makes an interesting choice: It selects a random element of the list and uses that as a median.

(define random-element
  (lambda (lst)
    (list-ref lst (random (length lst)))))

Is this a good choice? Let’s do some experimental analysis to find out.

a. Update the code above so that it counts calls to car, cdr, null? and cons. To do so, you will likely need to find or write versions of list-ref, length, and append that you can annotate to count calls.

b. Run a series of experiments on lists of length 100, 200, 400, and 800 to determine whether the Quicksort algorithm appears to take approximately (* c n (log_2 n)) steps for some constant c.

You should do experiments with lists that are already sorted (e.g., using iota to generate the lists). You should do experiments with lists whose elements are randomly generated. Make sure to do at least five experiments for each size/type and to include evidence of your experiments in the exam.

                        sorted, average                 random, average
n     nlogn     n*n     car   cdr   cons  null?         car   cdr   cons  null?
---   -----   -----     ---   ---   ----  -----         ---   ---   ----  -----
100     664   10000
200    1529   40000
400    3458  160000
800    7715  640000

c. What do your experiments tell you about the running time of the list based Quicksort? Does it seem like nlogn, n*n, or something else?

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. You will also lose your opportunity to invoke “there’s more than life”.

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

Somewhere between 0 and 5, depending on the mood of the grader. You may also lose your opportunity to invoke “there’s more than life”.

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. You will also lose your opportunity to invoke “there’s more than life”.

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

Somewhere between 0 and 5, depending on the mood of the grader. You may also lose your opportunity to invoke “there’s more than life”.

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. You may also lose your opportunity to invoke “there’s more than life”.

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.

; Time Log:
;   Date        Start   Finish  Elapsed Activity
;   2018-05-04  18:00   18:20   20 min  Wrote four tests
;   2018-05-05  20:30   21:00   30 min  Three non-working versions
;                                       (marked as a, b, and c below).
;                                       Decided to sleep on it.
;   2018-05-06  08:00   08:10   10 min  Woke up with an idea.  Coded it.
;                                       it seems to work
;   2018-05-06  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 mayanswer 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.

Have you heard any really good ideas that you’re willing to share? [Added 15:30 2018-05-03]

“I’m going to use the debugger, particularly on problem 4.”

“I’ve looked at the problems I think will be hardest and sent Sam questions.”

Questions on problem 1

Can I use vector-take and vector-drop? [Added 14:00 2018-05-03]

No. Those are procedures we have not covered in the class. They would also create an intermediate vector. Your goal in this problem is to use direct recursion.

Questions on problem 2

Can the predicate be leaf?? [Added 10:00 2018-05-02]

The predicates should be questions about the value, not about the structure.

Did you really mean to use two question marks in that question? [Added 10:00 2018-05-02]

Yes. One is for the leaf? predicate. One is for the question itself.

I’m tempted to use append in this procedure, but I know that append is generally inefficient. Should I avoid using append? [Added 14:00 2018-05-03]

While we generally discourage you from using append if you can avoid it, we did note that the natural solution to this problem is inefficient. You will not lose points for using append unless your use is particularly problematic.

Any hints on making this more efficient? [Added 15:30 2018-05-03]

While you probably don’t need a separate helper for the inefficient solution, you will need one for the efficient solution. Consider including an extra parameter that keeps track of the values you already know should be in the list.

Do you have any suggestions on how I should approach this problem? [Added 9:00 2018-05-04]

Trust the magic recursion fairy.

Questions on problem 3

Can I assume that the files contain only textual data? [Added 10:00 2018-05-02]

Yes.

Can I assume that the file names end with .txt? [Added 10:00 2018-05-02]

No.

What should happen if the destination file already exists? [Added 17:00 2018-05-02]

It’s up to you. You can have the procedure fail to run. You can replace the file. Just make sure that the documentation explains your choice.

How might I show that the procedure works correctly? [Added 9:00 2018-05-04]

Show the content of the first file. Show the content of the second file. Merge the two files. Show the content of the result.

Can I use read to read the data? [Added 15:00 2018-05-05]

We’d recommend against it. read is used for reading Scheme values. You’re dealing with text files. read-char is probably your best best.

Questions on problem 4

Can I change the first lambda to take two parameters, rather than one? [Added 17:00 2018-05-02]

No.

It looks to me like the procedure returns #<procedure> or something similar. Is that right? [Added 17:00 2018-05-02]

Yes. That’s also what you get back from something like (section + <> 5). Review the reading on higher-order procedures.

Any hints on solving this problem? [Added 8:00 2018-05-04]

Once you’ve figured out the parameter types (there are three of them), I’d suggest that you work out a few simple calls by hand, just as we worked out how sum worked when we were first dealing with recursive procedures. (If the procedure is tail-recursive, you might also find it useful to make a table.)

Can I turn the kernel into a named let? I find those clearer. [Added 15:00 2018-05-05]

Sure. But you still have to explain why there was a lambda in the first place.

Questions on problem 5

Would it be bad to use reverse? [Added 9:00 2018-05-04]

It would be bad to use reverse on every recursive call. But if you use it once or twice total, it should be fine.

Questions on problem 6

What should we count? [Added 9:00 2018-05-04]

Calls to car, cdr, cons, and null?. You may find that they are similar. You may find they are different. But together, they should give you some sense as to how well the procedure runs.

Errata

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

• The semester was incorrect in the starter code. [JK, 0 pt]
• Sam is unable to multiply. 200x200 is 40000 not 20000. [OB, 1 pt]

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.