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 read-dictionary and 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"
Note that backronym will return matching words ignoring the case of the input text;
make sure you implement character comparisons using char-ci=? and not char=?.
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.
caddadadr proceduresTopics: Pairs and pair structures, HOPs
As we saw earlier in the semester, Scheme has some useful procedures like caddr and 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
The 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).
The vmap procedure constructs a new vector by applying the procedure proc to each element of the vector vec.
(Note that the vector vec is not changed in this procedure.)
The 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 map, vector->list, list->vector or any other procedures that are similar to vmap and 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:
val is less than a node’s contents, val should be inserted in this node’s left subtree.val should 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.Your 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->lines procedure when we write read-dictionary?map or an equivalent procedure over a list will not be accepted.letrec. You can read ahead and use this if you like.section?#| before the pasted material. Put
a |# after the pasted material.#| and |# 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.list-ref.lambda that 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.; STUB on 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.