Exam 1 – Starting Scheme

Assigned
Wednesday, Sep 19, 2018
Due
Tuesday, Sep 25, 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. You should have received an email notification that you were added to this class on gradescope; follow the directions in that email to set up a password and log in. To upload your exam, click on CSC151-01 on your gradescope dashboard, click Exam 1, 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 exam1.rkt starter source code.

Problem 1: Multiples of Three

Topics: Numeric Values, Documentation, Creating Procedures, Higher-Order Procedures

We have learned three different ways to create procedures in this class so far:

  • We can use section to fill in some of an existing procedure’s parameters
  • We can use o to apply single-parameter procedures in sequence
  • We can create new procedures from Scheme expressions using lambda

Consider a procedure (round-to-multiple-of-three x). This procedure takes one parameter, x, and returns that value rounded to the nearest multiple of three.

> (round-to-multiple-of-three 1)
0.0
> (round-to-multiple-of-three 2)
3.0
> (round-to-multiple-of-three 14.1)
15.0
> (round-to-multiple-of-three 1.5)
0.0
; NOTE: Your DrRacket may round differently. 3.0 is also acceptable
> (round-to-multiple-of-three -2.5)
-3.0
> (round-to-multiple-of-three 4.5)  
3.0
; NOTE: Your DrRacket may round differently. 6.0 is also acceptable

There are countless ways to write such a procedure, but we will ask you to write it using two different techniques: once using lambda, and once using a combination of section and o.

a. Write the 6P-style documentation for round-to-multiple-of-three.

b. Implement round-to-multiple-of-three using lambda. To avoid name collisions, name this procedure round-to-multiple-of-three-b. You may not use composition or sectioning in this implementation.

c. Implement round-to-multiple-of-three using a combination of section and o. To avoid name collisions, name this procedure round-to-multiple-of-three-c. You may not use lambda in this implementation.

Problem 2: Testing Multiples of Three

Topics: Numeric Values, Testing

Write a comprehensive test suite for your round-to-multiple-of-three procedure from the previous problem. You should name your test suite test-round-to-multiple-of-three.

To receive full credit, your test suite must have at least nine test cases that cover distinct categories of input; the starter code includes one case, and you must write eight additional test cases. Each test case must be labeled with a descriptive name, and have at least three checks that fit that description.

The starter code includes a round-to-multiple-of-three procedure that invokes round-to-multiple-of-three-b. Write your test suite so it tests the round-to-multiple-of-three procedure; this makes it easy to test either version b or c by changing the generic version’s definition.

Problem 3: Whatzitdo

Topics: Code Reading, Documentation

Sometimes students (and professors) come up with difficult-to-read solutions to problems. Here is one such solution:

(define
  :/                                              (lambda (
  :)     (map (o (section list-ref : <>) (section - (length
  :)                                   <> 1)) (iota (length
  :)                                                   ))))

Figure out what this procedure does and then do the following:

a. Rename the procedure and parameter(s) so that their type and purpose is clear.

b. Reformat the code.

c. Explain how the procedure works in your own words. Your explanation should not closely resemble the Scheme code for this procedure.

d. Write 6P-style documentation for the code.

Problem 4: Converting Lists to Readable Strings

Topics: Lists, Strings, Creating Procedures

One important step in writing useful programs is presenting data to users. While Scheme makes it possible to create many interesting structures for data, we almost always display those data to users as strings. One such interesting data structure we have learned about is lists, which also appear in English language text as comma-separated phrases with “ and “ between the second-to-last and last elements of the list.

Write and document a procedure (readable-list lst) that takes a list of strings and produces a single string that contains each of the elements of the list displayed as an English list. For example:

> (readable-list (list "Take a card with a computer name"
                       "find the computer on the classroom map"
                       "put the card in the bucket"
                       "go to the computer"
                       "introduce yourself to your partner."))
"Take a card with a computer name, find the computer on the classroom map, put the card in the bucket, go to the computer and introduce yourself to your partner."

> (readable-list (list "almond butter" "bread" "strawberry preserves"))
"almond butter, bread and strawberry preserves"

> (readable-list (list "peanut butter" "jelly"))
"peanut butter and jelly"

> (readable-list (list "CSC151"))
"CSC151"

Hints

  • The readable-list procedure combines multiple strings into one string. What procedure do we know that combines values from a list together? How can we combine strings?
  • Notice that readable-list must treat the last item in a list differently from the preceding items. How can we get a list of everything except the last value in an input list? What about just the last value in that list?

Problem 5: Removing odd values

Topics: Filtering, Sorting

We’ve seen a variety of techniques for removing negative numbers from a list of numbers. One of the most promising (as long as we don’t care about ordering) is to add a 0 to the front of the list, sort the list, find the index of the 0, and then drop everything up to that 0. You can, for example, find that approach in the lab on unit testing.

Can we use the same technique to eliminate the odd integers in a list of integers? Surprisingly, yes. How? It requires that we devise a different way of comparing numbers. As you’ve seen, the sort routine will order numbers “any” way you like, as long as there’s a way to say whether or not one number comes before another. When we sort a list of numbers with <, we get them ordered from smallest to largest. When we sort a list of numbers with >, we get them ordered from largest to smallest.

We can choose other ways of ordering values when we use sort. For example, here’s how we might compare two numbers according to their absolute values.

;;; Procedure:
;;;   abs<?
;;; Parameters:
;;;   num1, a real number
;;;   num2, a real number
;;; Purpose:
;;;   Compare the absolute value of num1 to the absolute value of num2
;;; Produces:
;;;   less?, a truth value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * if (abs num1) < (abs num2) then less? is #t.
;;;   * otherwise, less? is #f.
(define abs<?
  (lambda (num1 num2)
    (< (abs num1) (abs num2))))

We can then use this to sort a list of numbers by their absolute value.

> (sort (list 42 1 -5 3 18 -0.5 -11 22 -4) abs<?)
'(-0.5 1 3 -4 -5 -11 18 22 42)

We could also write

> (sort (list 42 1 -5 3 18 -0.5 -11 22 -4) (lambda (a b) (< (abs a) (abs b))))
'(-0.5 1 3 -4 -5 -11 18 22 42)

How does that help us remove all the odd numbers from a list? We can write a comparator that says that any odd number is less than any other number.

> (sort (iota 10) (lambda (a b) ___))
'(9 7 5 3 1 0 2 4 6 8)
> (sort (list 1 2 5 1 2 4 3 -1 -11 12 14 -2) (lambda (a b) ___))
'(-11 -1 3 1 5 1 2 2 4 12 14 -2)

Implement and document remove-odds using that technique as well as the ideas from remove-negatives.

Note: If the lambda expression in those examples is confusing, you could write a separate procedure.

;;; Procedure:
;;;   odd-first?
;;; Parameters:
;;;   a, an integer
;;;   b, an integer
;;; Purpose:
;;;   Determine if a comes before b according to the metric
;;;   "odd numbers come before even numbers.
;;; Produces:
;;;   first?, a Boolean value
;;; Preconditions:
;;;   [No additional]
;;; Postconditions:
;;;   * If a is odd, first? is #t
;;;   * Otherwise, first? is #f
;;; Philosophy:
;;;   Used to order lists of integers to put odd numbers first.
(define odd-first?
  (lambda (a b)
    #t)) ; STUB
> (sort (iota 10) odd-first?)
'(9 7 5 3 1 0 2 4 6 8)
> (sort (list 1 2 5 1 2 4 3 -1 -11 12 14 -2) odd-first?)
'(-11 -1 3 1 5 1 2 2 4 12 14 -2)

Note: You may not use the filter procedure to implement remove-odds.

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!

Question 1

The stub procedure for round-to-multiple-of-three-c uses a lambda expression even though we aren’t allowed to use lambda in our solution. What gives?
I’m not sure how else to make a stub; perhaps it should have read (define round-to-multiple-of-three-c increment). In any case, make sure you don’t include the lambda in your actual answer.
I wrote code for part C that defines multiple procedures. Some use section, some use o, but none use both. Is that okay?
Yes! It sounds like you broke your solution up into parts, but as long as the final procedures combines them that’s just fine.
The examples show that 1.5 is rounded down to zero. Should round-to-multiple-of-three always round down?
If you use Scheme’s round procedure you will sometimes round up and sometimes round down. That’s fine.

Question 2

Do we have to write three examples for each of the eight new test cases?
Yes. That’s just 24 tests.
Are fractions and decimals different cases?
Yes. Your cases should probably cover both exact and inexact number representations.

Question 3

What does it mean to “reformat” the code?
Change the placement of line breaks, reindent, and generally clean up the appearance of the code. This helps us see what parameters go with each procedure invocation. This is something you should do in addition to renaming parameters and the outer procedure. Hitting ctrl+I is a good start, but you will probably need to add and remove some line breaks.
How should we describe how the procedure works?
You can reference the steps the procedure runs in the Scheme code, but you will need to add an explanation of what the procedure is accomplishing with each step. For example, it would not be sufficient to say “Then the procedure adds one to x.” Instead, you need to explain why adding one to x is important.

Question 4

This problem is really hard. What should I do?
It is indeed quite difficult. You should not spend an inordinate amount of time on this problem. If you have a solution that works with a list of three or more strings you can receive as much as 80% on the problem. Solutions that work with lists of two or more strings can receive up to 90%. If you can handle a list of just one string you can earn 100% on the problem. Each of these scores assume you get everything else correct, including documentation, code formatting, clear parameter names, etc.

Question 5

Do we need to show examples of our remove-odds procedure running?
Yes! You do not need to write a test suite, though.

General Questions

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.

Problem 2

  • The starter code should have incldued test cases that use check-= rather than check-equal?.

Problem 4

  • “Everything” was mistyped as “everthing.” [+1 point, CN]

  • The first example was missing a closing paren. [+1 point, AB, SC, CK, LR, others]

Problem 5

  • …according to their absolute value. should use “values” rather than “value.” [+1 point, CN]

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.