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 exam3.rkt starter source code.
Topics: Files, Strings, Randomness and Simulation
Computer scientists are fond of using acronyms for common concepts, but sometimes we’re more interested in an acronym that’s easy to pronounce than one that’s particularly descriptive. A backronym is an acronym that began in acronym form, with its source words added later. For example, the now-defunct Yahoo! search engine was not originally an acronym, but users have proposed a number of possible backronyms:
For this problem, write a procedure
(backronym str dictionary) that takes a string and dictionary (a list of words in any order) as input and produces a random backronym using words in the given dictionary.
You do not need to document
backronym, but you should write 4Ps for any helper procedures.
As part of your solution you will also need to write a
(read-dictionary filename) procedure.
You do not need to document
read-dictionary, but you should write 4Ps for any helper procedures.
This procedure should open the file passed in as
filename, read all the lines of the file, and return them in a list.
When you have a working implementation you may want to use the file
"/usr/share/dict/words" available on most Linux and macOS computers, but you should begin with the
cs-dictionary.txt file, which has a list of computer science terms derived from Wikipedia’s list of words about computers.
The following example uses of
backronym illustrate how these procedures may be used.
> (read-dictionary "cs-dictionary.txt") '("Adobe" "Acrobat" "address" ... "yottabyte" "zip") > (define cs-dict (read-dictionary "cs-dictionary.txt")) > (backronym "CS" cs-dict) "computer spamming" > (backronym "CSC" cs-dict) "Chrome search C++" > (backronym "HSSC" cs-dict) "hardware supercomputer spyware client" > (define full-dict (read-dictionary "/usr/share/dict/words")) > (backronym "CS" full-dict) "cataracted snakeberry" > (backronym "Racket" full-dict) "rachischisis aphthitalite centistere kinnikinnick electrocoagulation toothache" > (backronym "Scheme" full-dict) "sanitation cynically harbinge exorcisation misfield extraequilibrium"
backronym will return matching words ignoring the case of the input text;
make sure you implement character comparisons using
char-ci=? and not
You may assume that the dictionary passed to
backronym will contain at least one word that begins with every letter.
You may not use the
file->lines procedure built into Racket in your solution, but you might find some useful starter code in the files lab.
Topics: Pairs and pair structures, HOPs
As we saw earlier in the semester, Scheme has some useful procedures like
cdadr that allow us to quickly access values in pair structures.
However, these short-hand procedures are only available for up to four pair accessor operations.
For this problem, you should write and document a procedure
(make-pair-accessor name) that produces a pair accessor procedure from a string of its Scheme-style name.
Consider the following example inputs:
> (define my-cadr (make-pair-accessor "cadr")) > (my-cadr (list 1 2 3)) 2 > (define my-cdaddr (make-pair-accessor "cdaddr")) > (map iota (iota 5)) '(() (0) (0 1) (0 1 2) (0 1 2 3)) > (my-cdaddr (map iota (iota 5))) '(1) > (define my-cdddddr (make-pair-accessor "cdddddr")) > (my-cdddddr (iota 10)) '(5 6 7 8 9)
You may assume that
make-pair-accessor will only be called on valid input strings;
you do not need to validate the input in your code, but you should include a description of the valid inputs in your preconditions.
Topics: Vectors, HOPs
map procedure has been quite helpful for constructing lists.
Unfortunately, we have not seen an equivalent procedure for vectors.
Write and document two procedures
(vmap proc vec) and
(vmap! proc vec).
vmap procedure constructs a new vector by applying the procedure
proc to each element of the vector
(Note that the vector
vec is not changed in this procedure.)
vmap! procedure is similar to
vmap except it modifies the original vector
vec using side effects and returns nothing.
> (define vec (vector 1 2 3)) > vec '#(1 2 3) > (vmap increment vec) '#(2 3 4) > vec '#(1 2 3) > (vmap! increment vec) > vec '#(2 3 4)
You may not use
list->vector or any other procedures that are similar to
vmap! in your solution.
Topics: code reading, HOPs
Sometimes students (and professors) come up with difficult-to-read solutions to problems. Here’s one such solution. Isn’t it beautiful?
(define x (lambda (y z) (apply o (make-list y z))))
a. Clean up this procedure. You should reformat the code (add carriage returns and indent to format clearly); rename the procedure, parameters, and variables; and simplify any unnecessarily complicated or redundant code.
b. Write 6P-style documentation for the procedure.
c. Explain how the procedure achieves its purpose.
Topics: Recursion, Tree
In one of your recent labs, you have seen how to create a binary search tree from a given vector. Now we want you to create your own procedure to be able to insert elements into an existing binary search tree.
Write, but do not document, the procedure
(bst-insert tree val) that treats
tree as a binary search tree and inserts
val into it by applying the following rules:
valis less than a node’s contents,
valshould be inserted in this node’s left subtree.
valshould be inserted in this node’s right subtree. This procedure will take a tree as input, and produce a new tree that contains the inserted value as output.
bst-insert procedure should work for any real number value.
> (bst-insert empty 22) '#(node 22 empty empty) > (bst-insert (bst-insert empty 22) 34) '#(node 22 empty #(node 34 empty empty)) > (bst-insert (bst-insert (bst-insert empty 22) 34) 15) '#(node 22 #(node 15 empty empty) #(node 34 empty empty))
You may not use
vector->tree or any other tree procedure not provided with the exam starter code.
Hint: You may find it useful to test your tree using the
bst-find procedure from the binary trees lab.
We will post answers to questions of general interest here while the exam is in progress. Please check here before emailing questions!
file->linesprocedure when we write
mapor an equivalent procedure over a list will not be accepted.
letrec. You can read ahead and use this if you like.
#|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.
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.