Exam 3 – Thinking Recursively

Assigned
Wednesday, Nov 14, 2018
Due
Tuesday, Nov 20, 2018 by 10:30pm
Collaboration
You may not receive help from any person other than the instructor for this exam. See the exam procedures for a detailed description of the resources you can and cannot use.
Submitting
Upload your completed exam file to http://gradescope.com. To upload your exam, click on CSC151-01 on your gradescope dashboard, click Exam 3, and then drag your exam file to the upload window. If you want to update your exam you can resubmit the exam file; I will only grade the last version you upload before the deadline.

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.

Problem 1: Backronym Generator

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:

  • Yet Another Hypertext Organizing Oracle!
  • Yet Another Hierarchically Organized Oracle!
  • You Always Have Other Options!

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.

Problem 2: Generating caddadadr procedures

Topics: 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.

Problem 3: Mapping Vectors

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.

Problem 4: Whatzitdo?

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.

Problem 5: Inserting into a Binary Search Tree

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:

  • If val is less than a node’s contents, val should be inserted in this node’s left subtree.
  • Otherwise, 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.

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!

Problem 1

Can we use the file->lines procedure when we write read-dictionary?
Good find, but unfortunately the answer is “no.” We want you to practice using files. You will find some useful starting code in the files lab though, which you are welcome to use.

Problem 2

I think I need to write a procedure that doesn’t do anything as part of my solution. Is that a bad idea?
No! There are quite a few cases where we use the identity procedure, a procedure that takes a value and returns that value unmodified. It’s a good base case for recursive solutions that produce procedures, like this very problem.

Problem 3

Are we allowed to use lists in our solution to this problem?
Yes, although only in a limited way. You may not implement vmap by converting your vector to a list, mapping a procedure, and then turning the result back into a vector. You may find it useful to build a list for some other reason, but solutions that use map or an equivalent procedure over a list will not be accepted.

Problem 4

It looks like the whatzitdo gives me a procedure but it doesn’t do anything. What gives?
Have you tried running that procedure? I promise it does something.

General Questions

Do we need to document locally-defined procedures?
No.
Why can’t I write a recursive local procedure?
You have to use letrec. You can read ahead and use this if you like.
Are we allowed to talk to others about general issues from the first few weeks of class, such as the syntax of section?
No. We’ve had too many problems with “slippery slope” issues.
Questions should go to the instructors.
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.
What do you mean by “implement?”
Write a procedure or procedures that accomplish the given task.
Do we have to make our code concise?
You should strive for readable and correct code. If you can make it concise, that’s a plus, but concision is secondary to readability and correctness. Long or muddled code is likely to lose points, even if it is correct.
Much of your sample 6P-style documentation has incomplete sentences. Can we follow that model? That is, can we use incomplete sentences in our 6P-style documentation?
Yes, you can use incomplete sentences in 6P-style documentation.
You tell us to start the exam early, but then you add corrections and questions and answers. Isn’t that contradictory? Aren’t we better off waiting until you’ve answered the questions and corrected any errors?
We think you’re better able to get your questions answered early if you start early. Later questions will generally receive a response of “See the notes on the exam.”
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. Put a #| before the pasted material. Put a |# after the pasted material.
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 using #| and |# or semicolons. You might also add a note or two as to what you were trying to do.
Do I need to document helper procedures?
You must document helpers using the 4Ps.
Can I use procedures that we have not covered in class?
Probably not. Ask about individual procedures if you’re not sure.
Can I use list-ref? I’d swear we’ve used it, but I can’t find where.
You may certainly use list-ref.
I discovered a way to define procedures without using lambda that looks like (define (proc params) body). Can I use that?
No.
Is extra credit available on this exam?
No explicit extra credit is available. However, we may find that you’ve come up with such wonderful answers that we cannot help but give you extra credit. (Don’t laugh. It happens almost every time.)
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 other websites as a reference for 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.”
Do we have to cite the exam itself?
No.
How do I generate a random six digit number?
(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.
Some of the problems are based on a recent homework assignment. Should I cite my work on that assignment?
If you refer to your work on that assignment, you should cite it.
How do I cite my work on an assignment?
Something like “Student 123456 and partner. Homework Assignment 3. CSC 151.01. 6 September 2018.”
I see the comment ; STUB on some of the procedures. What does that mean?
We use the term “STUB” for a procedure that gives some default value rather than the correct one. Stub procedures are useful when you need the procedure to exist during development, but have not yet had time to implement it. You should remove these comments as you replace stub procedures with real implementations.
How exhaustive do our postconditions need to be when writing 6P-style documentation?
Your postconditions are not a test suite, but they should capture all of the procedure’s behavior. You do not need to give specific input/output examples, but describe what is true about the output as much as you can in a few concise lines.
Are there any requirements for informal tests?
Sort of. They should be good tests, though they need not be exhaustive. Your informal tests only count if they are different from the examples on the exam.
Do we need to show examples of running our helper procedures?
No, but you should be checking them carefully. You don’t need to include these examples in your exam.

Errata

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

Preliminaries

  • The submission instructions referenced exam 2 instead of exam 3 (morning section only). [+1/2 point. SY]

Problem 1

  • The provided documentation misspelled the word “character”. [+1 point, AA]

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.