Exam 4

Assigned: Tuesday, November 29

Due: Tuesday, December 6 by 10:30pm

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. Please rename this file to 000000.rkt, but replace 000000 with your assigned random number.

Problem 1: Resilient Words

Topics: Strings, Files, Recursion

A word is “resilient” if you can remove all of the word’s letters one at a time without producing a non-word sequence of characters. For the purposes of this problem, we will treat upper- and lower-case words as equal. As an example, the word “ping” is resilient because we can remove letters in the following sequence:

1. Remove “g”, which yields the word “pin”
2. Remove “p”, which yields the word “in”
3. Remove “n”, which yields the word “i”
4. Remove the “i”, which yields the empty string (our base case)

Note that word resilience is a recursive property; a length n word is resilient if removing one of its letters produces either the empty string or a length n-1 resilient word.

To test whether a word is resilient, we need a dictionary. Luckily, our GNU/Linux machines have one available. The file /usr/share/dict/words contains a long list of words and acronyms, one per line.

Write and document two procedures, (read-dictionary filename) and (is-resilient? word dictionary). The read-dictionary procedure takes a filename as a parameter, which it will open and read into some form that is convenient for you to use in the next procedure. The is-resilient? procedure takes a string word and a dictionary produced by the read-dictionary procedure and returns true if word is resilient in the context of the given dictionary. There are a few details you should consider as you write your procedures:

1. The is-resilient? procedure should be completely case-insensitive. Upper- and lower-case letters should be treated the same, whether they appear in dictionary, word, or both.
2. You do not need special handling for punctuation (apostrophes and hyphens). Treat these like any other letter that can be dropped from a word.
3. You are free to choose whatever representation you like for your dictionary. A list is one possible choice, but other representations may save you some work in the is-resilient? procedure.

The following lines in DrRacket show an example use of these two procedures:

> (define my-dictionary (read-dictionary "/usr/share/dict/words"))
> (is-resilient? "Ping" my-dictionary)
#t
> (is-resilient? "Myanmar" my-dictionary)
#f
> (is-resilient? "splatters" my-dictionary)
#t

Extra Credit: Finding the Longest Resilient Words

For up to three points of extra credit, write a procedure (longest-resilient-words dictionary-filename) that takes the name of a dictionary file as a parameter and returns a list of the longest resilient words in that dictionary. You do not need to document this procedure.

Problem 2: Counting Pairs

Topics: Pairs, Deep Recursion

As you may recall, we sometimes refer to the two-element-box created by the cons procedure as a “pair.” It can be very useful to identify just how many pairs appear in a structure, in part because it tells us a bit about the effort required to make the structure.

Write and document a procedure, (count-pairs value), that takes as input a Scheme value (e.g., a pair structure or list) and determines how many pairs (cons cells) appear in that structure.

For example,

> (count-pairs null)
0
> (count-pairs 5)
0
> (count-pairs (cons 5 null))
1
> (count-pairs (list 5))
1
> (count-pairs (cons null 5))
1
> (count-pairs (cons (cons 'a 'b) 'c))
2
> (count-pairs (list 1 2 3 4 5))
5
> (count-pairs (list null null null))
3
> (count-pairs (list (list 1 2 3) (list 4 5)))
7

As the examples above suggest, you need to look within lists to determine if their individual elements themselves contains pairs. (You may find that this happens automatically as you handle non-lists.) However, you need not look within vectors to see if they contain any pair structures.

> (count-pairs (vector (list 1)))
0

Problem 3: Printing Binary Trees

Topics: Trees

Write and document two procedures (print-tree! root) and (print-reverse-tree! root) that takes a binary tree root as input.

A binary search tree is a special form of binary tree that follows two specific rules: every child to the left of a node is less than or equal to the node’s value (including nodes further down the tree), and every child to the right of a node is greater than the node’s value (again, including nodes further down the tree).

When given a binary search tree like the ones below, the print-tree! procedure will print the values in the tree in ascending order, and print-reverse-tree! will print the tree’s values in descending order.

> (define tree1 (node 4 (node 2 (leaf 1) (leaf 3)) (node 6 (leaf 5) (leaf 7))))
> (define tree2 (node 4 (node 2 empty (leaf 3)) (node 6 (leaf 5) empty)))
> (print-tree! tree1)
Output! 1 2 3 4 5 6 7
> (print-tree! tree2)
Output! 2 3 4 5 6
> (print-reverse-tree! tree1)
Output! 7 6 5 4 3 2 1
> (print-reverse-tree! tree2)
Output! 6 5 4 3 2

That these procedures work for all trees—not just binary search trees—but they won’t necessarily print values in ascending or descending order; these procedures will print elements from un-sorted trees in un-sorted order. The order that nodes are printed depends on the structure of the tree, not the values in the tree. Consider the example below:

> (define tree3 (node 'a (node 'b (leaf 'd) empty) (leaf 'c)))
> (print-tree! tree3)
Output! d b a c
> (print-reverse-tree! tree3)
Output! c a b d

The printed output of each procedure should be space-separated (and it is OK to have a trailing space at the end of the output). The structure of the trees given are modeled using the procedures in the lab on trees and the relevant procedures are provided in the exam4.rkt file. For debugging and testing purposes, you may find the visualize-tree procedure in the tree-lab code to be helpful.

Problem 4: Analyzing Alternate Approaches

Topics: Map, Lists, Analyzing Procedures

When we first learned how to use map, we often used the technique of “take a single expression, insert map before each operation, and turn each value into a list, either with make-list or by using something like iota.”

For example, suppose we make one circle as follows.

(define circle-37
  (vshift-drawing (* 10 (modulo 37 10))
                  (hshift-drawing (* 5 37)
                                  (scale-drawing (increment (modulo 37 7))
                                                 drawing-unit-circle))))

In the extreme, we may end up writing something like the following.

(define many-circles
  (lambda (n)
    (map vshift-drawing
         (map *
              (make-list n 10)
              (map modulo
                   (iota n)
                   (make-list n 10)))
         (map hshift-drawing
              (map *
                   (make-list n 5)
                   (iota n))
              (map scale-drawing
                   (map increment
                        (map modulo
                             (iota n)
                             (make-list n 7)))
                   (make-list n drawing-unit-circle))))))

a. Using the techniques from the reading on analyzing procedures and the corresponding lab, update many-circles to count calls to cons, car, cdr, and null?. You can find implementations of all of the main procedures (e.g., map, make-list, and iota) in the exam code file.

b. Find out how many calls there are to cons, car, cdr, and null?. if we are making lists of 5, 10, 20, and 40 circles.

c. Come up with an approximate formula for the number of calls based on n.

d. Rewrite the code so that there are no more than 2*n calls to cons in making a list of n circles. Any helpers you write should be local.

Note: You may want to preview the list of circles with something like (drawing->image (drawing-compose (many-circles 50)) 200 100).

Problem 5: Whatzitdo

Topics: Vectors, Lists, Higher Order Procedures, Iteration

The following procedure performs a useful operation. While it’s a little difficult to tell what this procedure does, the original author clearly has his ducks in a row. Yes, I realize this is technically a column.

(define    daffy
(lambda (  puddles        )
  (let ([  darkwing       (lambda (
           donald
           huey
           count-duckula  ) (let ([
           louie          (vector-ref
           donald
           huey           )][
           dewey          (vector-ref
           donald
           count-duckula  )]) (vector-set!
           donald
           huey
           dewey          )(vector-set!
           donald
           count-duckula
           louie          )))]) (map (l-s
    apply  darkwing       )(map list (make-list (quotient (vector-length
           puddles        ) 2)
           puddles        )(iota (quotient (vector-length
           puddles        ) 2))(map (r-s - 1) (map (l-s - (vector-length
           puddles        )) (iota (quotient (vector-length
           puddles        ) 2)))))))
           puddles        ))

Figure out what this procedure does, then do the following.

a. Rename the procedure and parameters so their types and purpose are clear.

b. Reformat the code so it is readable and properly indented. Remember that you can press ctrl+i to auto-indent the code.

c. Eliminate any unnecessary operations or redundant computations to make the code more concise.

d. Document the updated procedure.

Problem 6: Nest

Topics: Higher Order Procedures, Numeric Recursion

As you may have noted, sometimes we “nest” repeated calls to the same procedure. For example, to compute x to the eighth power, we might write (square (square (square x))).

Write but do not document a procedure (nest n fun) that returns a new procedure that takes one input and applies fun the specified number of times.

> (define octo (nest 3 square))
> octo
#<procedure>
> (octo 2)
256
> (octo 3)
6561

> (define no-square (nest 0 square))
> (no-square 5)
5

> (define much-redder (nest 6 irgb-redder))
> (irgb->string (much-redder (irgb 0 0 0)))
"192/0/0"
> (irgb->string (much-redder (irgb 10 20 40)))
"202/20/40"

> (map (nest 7 increment) (iota 5))
'(7 8 9 10 11)

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!

General Questions and Answers

What is a general question?

A question that is about the exam in general, not a particular problem.

Do the two 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 be told “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. Select the text. Under the Racket menu, use “Comment out with semicolons.”

Should we include examples and, if so, how do we include them?

You should certainly include examples. We would recommend that you copy and paste them from the interactions pane to right below the problem in the definitions pane, and then comment them out with semicolons. (Select and then choose “Comment out with semicolons” from the “Racket” menu. Do not use “Comment out with a box!”

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

Do I need to document global and local helper procedures?

You must document global helpers using the 4Ps. Local helper procedures should have descriptive names, but documentation is not required.

Problem 3

Is it okay if my print-tree! procedure displays two spaces between the elements in the tree?

Yes, that is okay.

Problem 4

Can we use vectors to simplify this procedure?

No. Switching to vectors would just change operations we are counting into operations we aren’t counting in this case. You can still get to 2*n using lists.

Errata

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

Problem 3

• The output for the unsorted tree was shown in sorted order. (+1/2 point, PM, many others)
• The tree2 definition was the same as tree1 when it should have had the nodes of 1 and 7 removed. (+1/2 point, NJ)
• The output for tree3 was missing the required spaces. (+1/2 point, GW, HZ)

Problem 5

• The ducks are technically in a column, not a row. (+1 snark point, BW. Snark points are worth zero actual points)

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