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.
Topics: Numeric Values, Documentation, Creating Procedures, Higher-Order Procedures
We have learned three different ways to create procedures in this class so far:
section
to fill in some of an existing procedure’s parameterso
to apply single-parameter procedures in sequencelambda
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.
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.
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.
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"
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?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?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
.
We will post answers to questions of general interest here while the exam is in progress. Please check here before emailing questions!
round-to-multiple-of-three-c
uses a lambda
expression even though we aren’t allowed to use lambda
in our solution. What gives?(define round-to-multiple-of-three-c increment)
. In any case, make sure you don’t include the lambda
in your actual answer.section
, some use o
, but none use both. Is that okay?round-to-multiple-of-three
always round down?round
procedure you will sometimes round up and sometimes round down. That’s fine.x
.” Instead, you need to explain why adding one to x
is important.remove-odds
procedure running?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.
check-=
rather than check-equal?
.“Everything” was mistyped as “everthing.” [+1 point, CN]
The first example was missing a closing paren. [+1 point, AB, SC, CK, LR, others]
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.