Exam 3

Assigned: Friday, November 4

Due: Friday, November 11 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 exam3.rkt starter source code. Please rename this file to 000000.rkt, but replace 000000 with your assigned random number.

Problem 1: Averaging Safely

Topics: Basic Recursion, Checking Preconditions, Lists

Write and document a procedure called (safe-average-a lst) that when given a list of numbers computes the average of those numbers. You must use direct recursion for this problem; that means you may not use a __-so-far parameter in a helper procedure. The procedure must also be safe in the sense that it verifies all preconditions and gracefully throws errors when they are not satisfied. The error messages must be informative and describe what the error was and where it occurred if applicable.

> (safe-average-a (list 1 2 3))
2
> (safe-average-a 5)
Error! safe-average-a: contract violation
Error! expected: list?
Error! given: 5
> (safe-average-a (list 1 2 3 "hello" 4))
Error! safe-average-a: list must contain all numbers; given "hello"

Problem 2: Averaging Safely with Tail Recursion

Topics: Tail Recursion, Checking Preconditions, Lists, Naming Local Procedures

Write but do not document a new version of your safe averaging procedure called (safe-average-b lst) using tail recursion. Any helper procedure(s) you use in this problem must be locally defined rather than globally defined. As before, the procedure must also verify all preconditions and give appropriate errors.

Problem 3: Whatzitdo

Topics: Map, Compose and Section, Lists, Characters and Strings

Some time ago, a student who I will call “Gle” came up with something like the following as an alternative to an existing procedure.

(define f (lambda (a b c) (list->string (map (compose (l-s string-ref a) (l-s + b)) (iota (- c b))))))

Figure out what the procedure does and then do the following.

a. Rename the procedure and the parameters so that their type and purpose is clear.

b. Reformat the code.

c. Document the updated procedure.

Problem 4: Numbers to Words

Topics: Numeric Recursion, Characters and Strings

While Scheme provides us with useful utilities that can turn numbers like 6 into the string "6" and back, we don’t have a function that can turn 6 into the cardinal "six" or 1342 into "one thousand three hundred forty two". While this is somewhat more complex than the conversion from 6 to "6", we can take advantage of the recursive structure of cardinal numbers.

First, cardinals can be “decomposed” three digits at a time. For example, the number 642 is "six hundred forty two", while the number 642000 is "six hundred forty two thousand", and 642000000 is "six hundred forty two million". If we add non-zero digits to the lower places, as in 642121, we simply concatenate these: 642 becomes "six hundred forty two", then we add "thousand" because these three digits occurred in thousands digits. Next, we append the converted value of 121—"one hundred twenty one"—to produce our final answer: "six hundred forty two thousand one hundred twenty one".

There are repeating patterns within these three digit blocks as well. The number 1 becomes "one", and the number 81 becomes "eighty one". As long as the tens place is not 1 we simply append the cardinal form of the ones place onto the end of the cardinal form of the tens place. Numbers from 11 to 19 will need to be handled as a special case. Hundreds work out very nicely: a number with a 5 in the hundreds place converts to "five hundred" followed by the converted form of the tens and ones places.

Write but do not document a procedure (number->words n) that takes an integer n between one and 999999999999999 (inclusive) and returns a string containing the cardinal form of the given number. You do not need to return "zero" for the input 0; we will only use counting numbers for this problem. Your procedure must use recursion to avoid unnecessary duplicated code. You may not write special cases for each of the sixteen digits.

Hints

You will need to extract specific digits from a decimal number to implement number->words. To get the hundreds digit of a number n run (quotient n 100). Likewise, the tens digit is (quotient n 10).

You will also need to break a larger number up into three digit chunks. You can actually think of numbers a bit like lists. Imagine for a moment that we had a list of digits (list 210 543 876) that represent the number 876543210. The first element in the list is the ones through the hundreds place, the second element is the thousands through the hundred thousands place, and the third holds the millions through hundred millions digits.

With this list, we can access the first block of three digits with car and the remaining blocks of digits with cdr. Unfortunately our inputs are numbers and not lists, but we can use remainder and quotient with a divisor of 1000:

; Use remainder to get the rightmost three digits from a larger number
> (remainder 876543210 1000)
210

; Use quotient to get the rest of the digits
> (quotient 876543210 1000)
876543

Examples

> (number->words 1002)
"one thousand two"
> (number->words 414)
"four hundred fourteen"
> (number->words 999999999999999)
"nine hundred ninety nine trillion nine hundred ninety nine billion nine hundred ninety nine million nine hundred ninety nine thousand nine hundred ninety nine"
> (number->words 34029)
"thirty four thousand twenty nine"

Problem 5: Remainder

Topics: Numeric Recursion

Write, but do not document, a procedure (my-remainder n d) that takes two integers as input and returns the remainder of n divided by d. The parameter n must be zero or more and the parameter d must be one or more. Note that you may not use the procedures remainder, quotient, /, or any other related procedures to solve this problem (in other words, you must use numeric recursion).

> (my-remainder 5 5)
0
> (my-remainder 574 232)
110
> (my-remainder 1 199)
1

Problem 6: Turtle Trees

Topics: Basic Recursion, Numeric Recursion, Turtle Graphics, Documentation

Write and document a procedure, (turtle-tree! turtle trunk-length branches levels), that uses the provided turtle to draw a tree. You can think of a tree as a trunk (a line) with some number of smaller trees “growing” out of the end of the trunk.

To draw a tree, your turtle should rotate to a random angle between plus and minus 60 degrees, then draw a line that is trunk-length pixels long. The end of the trunk should split into some number of smaller trees, determined by the branches parameter. Each smaller tree should have a slightly shorter trunk length (75% of the previous trunk length works well). This process should repeat until the tree has levels levels; for example, if branches and levels are both 3, the tree should have a total of 13 lines. Before drawing a tree, some set-up is required:

; Create a world, a turtle, set the brush to a fine line, and position the turtle
; at the bottom middle of the image facing up.
(define set-up-turtle
  (lambda ()
    (let* ([world (image-show (image-new 300 200))]
           [tommy (turtle-new world)])
      (turtle-turn! tommy -90)
      (turtle-teleport! tommy 150 200)
      (turtle-set-brush! tommy "2. Hardness 100" 0.15)
      tommy)))

After running the set-up code above, you should be able to run the following examples with a completed turtle-tree! function. While you should run the tests below, to earn full credit on this problem you must include three examples of your own. Try varying the depth, branches, and trunk length to show how your tree procedure responds. Include the resulting images in your exam file using the Insert Image option in DrRacket.

The following code should draw a tree with a trunk length of 60, three branches, and three levels.

> (turtle-tree! (set-up-turtle) 60 3 3)

This next example draws a four-level tree with five branches per level.

> (turtle-tree! (set-up-turtle) 60 5 4)

Here is another possible result of running the turtle-tree! procedure with the same parameters:

> (turtle-tree! (set-up-turtle) 60 5 4)

Finally, here is a five-level tree with seven branches per level. This one will take quite a while to finish drawing.

> (turtle-tree! (set-up-turtle) 60 7 5)

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 1

Are we allowed to use helper procedures?

Yes! You can write a directly-recursive helper procedure and call it. We’ve referred to this as “husk and kernel” procedures in the past. The one thing you should not do is use a so-far parameter.

Can we store local values using let and let*?

Yes. You may also use letrec and named let to define local helper procedures.

Do helper procedures for this problem need to be local?

No. You must document them with 4Ps if they are globally defined.

Problem 2

Do helper procedures for this problem need to be local?

Yes.

Problem 3

What do you mean by “reformat?”

Add or remove line breaks and correct the code’s indentation to improve readability of the code.

Problem 4

Should we define helpers globally or locally?

It’s up to you. Sometimes local helpers are easier to understand, but in some cases it makes it difficult to follow a procedure. Do what makes the most sense to you.

What do you mean by “no special cases for each of the sixteen digits?”

We discussed this in detail in class. If you write cond or if with more than about ten cases, you’re probably approaching the problem in a way we would consider invalid. You should certainly use recursion. If we asked you to extend your procedure to support quadrillions and quintillions, this should be a very small change.

What should we do about extra whitespace in our output?

You can ignore it. Just make sure you have at least one space between words!

What should our procedure return when n is zero?

Anything you want! I will not test your procedure on zero.

Problem 5

What kinds of numeric procedures can we use on this problem?

You may use addition, subtraction, multiplication, and comparison (<, >, =, etc.). You may not use division, quotient, or remainder.

Problem 6

What should happen if we run turtle-tree! with zero levels?

Your turtle should draw nothing.

Turtles turn a random amount at each step. What is this angle relative to?

The random angle should be the angle between the previous branch/trunk and the next branch, not relative to a vertical line.

What should our postconditions be?

Just describe the structure of the resulting image. You can be abstract, since it’s random. You do not need to be as detailed and precise as we are for procedures that give a numeric answer.

What should turtle-tree! do with zero branches?

Anything you like. I will not test it with zero branches.

Errata

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

Starter Code (no extra credit)

• Probems 1 and 2 were missing defines for the two provided stub functions [TP, AM].

Problem 4

• Upper bound was inconsistent between documentation/examples versus the problem description (999 billion … versus 999 trillion …). [EZ, +1/2 point]

Problem 5

• The problem said to document my-remainder, but documentation was provided. [SF, +1 point]

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.