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 exam4.rkt starter source code.
Topics: pairs and pair structures, lists, recursion
We’ve seen many types of data in Scheme, but two have had an interesting recursive structure: lists and binary trees. For example, consider the following definition of a list:
A list is:
- a pair of some value and a list.
For this problem, you will create a new recursively-defined datatype known as a tsil. A tsil is:
The only hard requirement for creating a datatype in Scheme is to write a predicate that can check if a value conforms to the definition of the datatype.
Write and document the procedure
(tsil? val) that checks if a value is a tsil.
llun is defined in your starter code, as is the predicate
Consider the following example uses of
> (tsil? (list 1 2 3)) #f > (tsil? (cons llun 2)) #t > (tsil? (cons null 5)) #f > (tsil? llun) #t > (tsil? (cons (cons (cons llun 3) 2) 1)) #t > (tsil? "I am a tsil") #f > (tsil? 'no-really-I-am-a-tsil) #f
Topics: pairs and pair structures, lists, structural recursion
For the previous problem, you implemented a
tsil? predicate to work with our new tsil datatype.
While this is sufficient to consider our datatype complete, it would be more useful if we had some utilities to work with tsil values.
Your task for this problem is to write, but not document, four tsil procedures:
(tsil-ref tsl index), which takes a tsil and index, and returns the value at the given offset.
(list->tsil lst), which takes a list and produces an equivalent tsil
(tsil->list tsl), which takes a tsil and produces an equivalent list
(tsil-length tsl), which takes a tsil and returns its length
We consider a list and tsil equivalent if they contain the same values at the same indices.
For a concrete example, consider the list produced by
(list 1 2 3).
The equivalent tsil is
(cons (cons (cons llun 3) 2) 1), as the
1 is held in the outermost pair, the
2 is in the next pair, and the
3 is in the innermost pair.
Consider the following example uses of these procedures as you complete your implementations:
> (define my-tsil (cons (cons (cons llun 3) 2) 1)) > my-tsil '(((llun . 3) . 2) . 1) > (tsil-length my-tsil) 3 > (tsil-ref my-tsil 0) 1 > (tsil-ref my-tsil 2) 3 > (tsil->list my-tsil) '(1 2 3) > (define another-tsil (list->tsil (list "this" "is" #\a 'tsil))) > another-tsil '((((llun . tsil) . #\a) . "is") . "this") > (tsil-length another-tsil) 4 > (tsil->list another-tsil) '("this" "is" #\a tsil)
Topics: code reading, documentation
Sometimes students (and professors) come up with difficult-to-read solutions to problems. Here is one such solution:
(define enifed (lambda (rambda schmambda) (let tel ( [rdc (cdr schmambda)] [rac (car schmambda)]) (if (null? rdc) rac (tel (cdr rdc) (rambda rac (car rdc)))))))
Figure out what this procedure does and then do the following:
a. Rename the procedure and parameter(s) so that their type and purpose is clear.
b. Reformat the code.
c. Explain how this procedure achieves its goal.
d. Write 6P-style documentation for the code.
You do not need to preserve all the versions of this code; your exam file only has to contain 6Ps, the reformatted and renamed procedure, and your explanation for part c.
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.
'(2 1 3 0 2)
'(5 9 8 7 5)
We sort the two lists. (How? Recursively!)
'(0 1 2 2 3)
'(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
partition procedures above so they counts calls to
To do so, you will likely need to find or write versions of
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.,
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?
Topics: trees, predicate procedures, recursion
We have used trees to store data, either in a free-form way, or with constraints on ordering as in binary search trees. However, trees can do much more than just store data. Decision trees are one example use of trees for something other than data storage.
A decision tree is a tree that contains a series of questions (predicates, in Scheme lingo).
Given an input value, we can execute the decision tree by beginning at the root of the tree.
The contents of the root node will be a predicate, which we run on our input value.
If the result of the predicate is
#t, we proceed down the right subtree.
If the result is
#f, proceed down the left subtree.
Once we reach a leaf node, we return the contents of the node as our final answer.
For example, consider the decision tree
(node odd? (leaf "even number") (node positive? (leaf "negative odd number") (leaf "positive odd number"))), which we will run on the input 7.
At the root of this tree, we see the
We can run this predicate on our input, 7, which returns
We then proceed to the right subtree, which contains the predicate
(positive? 7), which also returns
We then move to the right subtree, where we encounter a leaf.
Instead of running a predicate, when we encounter a leaf we simply return the contents of the leaf node, in this case a
"positive odd number".
Had we evaluated the tree with a negative odd number, we would instead produce
"negative odd number", and if we had run the tree on an even number we would receive
Write, but do not document, a procedure
(run-decision-tree decision-tree input) that follows this process to run a decision tree on a given input.
The following examples illustrate a more interesting application of decision trees. We will first define a helper procedure:
; Look in a list of past courses to see if a student has taken a particular course (define has-taken (lambda (course past-courses) (not (= -1 (index-of course past-courses)))))
Next, we define a decision tree. This decision tree takes as input a list of courses a student has taken in the CS introductory sequence, and returns a list of courses that student is now eligible to take, having satisfied the prerequisites:
(define cs-intro-sequence (node (section has-taken "CSC 151" <>) (leaf (list "CSC 151")) (node (section has-taken "CSC 161" <>) (leaf (list "CSC 161")) (node (section has-taken "CSC 207" <>) (leaf (list "CSC 207")) (leaf "All done!")))))
Consider the following example uses of this decision tree:
> (run-decision-tree cs-intro-sequence (list "CSC 151")) '("CSC 161") > (run-decision-tree cs-intro-sequence (list "CSC 151" "CSC 161")) '("CSC 207")
You can find a much larger decision tree that covers the entire core of the computer science curriculum at Grinnell in the exam starter code. This decision tree does not check for electives, but does include all courses that count as required courses toward the major. Here are some sample uses of that decision tree:
> (run-decision-tree cs-curriculum (list "CSC 151" "CSC 161")) '("CSC 207" "CSC 208" "CSC 211" "CSC 213") > (run-decision-tree cs-curriculum (list "CSC 151" "CSC 161" "CSC 208")) '("CSC 207" "CSC 211" "CSC 213") > (run-decision-tree cs-curriculum (list "CSC 151" "CSC 161" "CSC 207" "CSC 208")) '("CSC 211" "CSC 213" "CSC 301" "CSC 324" "CSC 341") > (run-decision-tree cs-curriculum (list "CSC 151" "CSC 161" "CSC 207" "CSC 208" "CSC 211" "CSC 213" "CSC 301" "CSC 324" "CSC 341")) "All done! Just make sure you've completed your elective."
run-decision-tree implementation must be able to run both the
cs-curriculum decision trees, but your three examples must use a decision tree of your own design.
We will post answers to questions of general interest here while the exam is in progress. Please check here before emailing questions!
'llunboth a tsil and a symbol. What gives?
llun(which is defined as a symbol in the starter code), or a pair of a tsil and some value.
(cons 3 llun)a tsil?
llunor a pair of a tsil and some value. The order of values in the pair is not arbitrary; the same is true for lists, but tsils expect the recursive value in the car rather than the cdr position of the pair.
(list llun 1 2 3)a tsil?
(cons llun (list 1 2 3)). This is a pair of a
llunand some value, so it is indeed a tsil. However, it’s a tsil of length 1, which may not be what you expected.
tsil?crashes on some of your inputs. That makes me sad.
caron a non-pair. Make sure you check for pairs!
random-elementso all their calls to
cdr, etc. are counted. You do not need to count calls to
cdr, etc. in the
random-listprocedure. The idea here is that you are counting calls that happen during the execution of
quicksort, but not in generating the test input you run
#|before the pasted material. Put a
|#after the pasted material.
|#or semicolons. You might also add a note or two as to what you were trying to do.
list-ref? I’d swear we’ve used it, but I can’t find where.
lambdathat looks like
(define (proc params) body). Can I use that?
(random 1000000). If you end up with a number less than six digits, add zeros to the left side of the number until you have six digits.
; STUBon some of the procedures. What does that mean?
Please check back periodically in case we find any new issues.
)in the first example. [No EC. Fixed before end of first day.]
tsil->length. [+1/2 point. SB]
has-takenpredicate should have had a question mark. I am not updating the problem because that would break your example code if you already downloaded the starter file. Because this is a style rather than correctness issue, there will be no bonus point for this error.
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.