Homework 7:
Due by 11:59pm on Thursday, 10/25
Instructions
Download hw07.zip.
Our course uses a custom version of Scheme (which you will build for Project 4) included in the starter ZIP archive. To start the interpreter, type
python3 scheme
. To run a Scheme program interactively, typepython3 scheme -i <file.scm>
. To exit the Scheme interpreter, type(exit)
.
Submission: When you are done, submit with python3 ok
--submit
. You may submit more than once before the deadline; only the
final submission will be scored. Check that you have successfully submitted
your code on okpy.org. See Lab 0 for more instructions on
submitting assignments.
Using Ok: If you have any questions about using Ok, please refer to this guide.
Readings: You might find the following references useful:
Grading: Homework is graded based on effort, not correctness. However, there is no partial credit; you must show substantial effort on every problem to receive any points.
Q0: Survey
Before you get started writing code, please fill out the midterm survey.
Important Submission Note
You're not done yet! Add the passphrase you receive at the end of the survey to passphrase at the top of the homework. For example, if the passphrase was
CS61A
(it isn't 🙂), then the first line of your file should read:
passphrase = 'CS61A'
Instead of:
passphrase = '*** PASSPHRASE HERE ***'
Use Ok to test your code:
python3 ok -q survey
Q1: Cadr and Caddr
Define the procedures cadr
and caddr
, which return the second
and third elements of a list, respectively:
(define (cddr s)
(cdr (cdr s)))
(define (cadr s)
'YOUR-CODE-HERE
)
(define (caddr s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q cadr-caddr -u
python3 ok -q cadr-caddr
Conditional expressions
The cond
special form is a general conditional expression, similar to
a multi-clause conditional statement in Python. The general form of a
conditional expression is:
(cond
(<p1> <el1>)
(<p2> <el2>)
...
(<pn> <eln>)
(else <else-expressions>))
This consists of the symbol cond
followed by sequences of expressions (<p>
<el>)
called clauses.
The first expression in each pair is a predicate: an expression whose value is interpreted as either being true or false.
In Scheme, all values except the special boolean value False
(historically
called #f
) are interpreted as true values. There is also a boolean value
True
(historically called #t
). In the 61A Scheme interpreter, False
and
#f
can be used interchangeably.
Conditional expressions are evaluated as follows:
- The predicates
<p1>
,<p2>
, ...,<pn>
are evaluated in that order until one of them evaluates to a true value (anything butFalse
). - If some predicate, such as
<p2>
, evaluates to a true value, then the following sequence of consequent expressions, such as<el2>
, is evaluated, and its final expression provides the value of the wholecond
expression. - Otherwise, if an
else
clause is present, then the sequence ofelse-expressions
is evaluated, and its final expression provides the value of the wholecond
expression. - If no clause has a true predicate and there is no
else
clause, then the value of thecond
is unspecified and should not be used.
Q2: Sign
Using a cond
expression, define a procedure sign
that takes in one
parameter x
and returns -1 if x
is negative, 0 if x
is zero, and 1 if x
is positive.
(define (sign x)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q sign -u
python3 ok -q sign
Q3: Pow
Implement a procedure pow
for raising the number b
to the power of a
nonnegative integer n
that runs in Θ(log n) time.
Hint: Consider the following observations:
- b2k = (bk)2
- b2k+1 = b(bk)2
You may use the built-in predicates
even?
andodd?
.
(define (square x) (* x x))
(define (pow b n)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q pow -u
python3 ok -q pow
Q4: Ordered
Implement a procedure called ordered?
, which takes a list of numbers and
returns True
if the numbers are in nondescending order, and False
otherwise. Numbers are considered nondescending if each subsequent number is
either larger or equal to the previous, that is:
1 2 3 3 4
Is nondescending, but:
1 2 3 3 2
Is not.
Hint: The built-in
null?
function returns whether its argument isnil
.
(define (ordered? s)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q ordered -u
python3 ok -q ordered
Sets as Ordered Lists
A set is a type of collection that stores unique elements. The main operation associated with sets is checking whether a given value is in a set.
There is no such built-in set data type in Scheme, but one way to represent a set is by using an ordered list, where the ordering is used to make union/intersection functions more convenient. The following few questions explore this idea. Specifically, we will represent sets using Scheme lists ordered from least to greatest with no repeated elements.
Q5: Add
First, define add
, which takes a set s
and a value v
as arguments. It
returns a representation of a set containing the values in s
and the value
v
. There should be no repeated elements in the return value.
We've provided a function empty?
which returns True
if the given set s
has
no elements.
(define (empty? s) (null? s))
(define (add s v)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q add -u
python3 ok -q add
Q6: Contains
Next, define contains?
, which returns whether a set s
contains value v
.
; Sets as sorted lists
(define (contains? s v)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q contains -u
python3 ok -q contains
Q7: Intersect and Union
Finally, define intersect
, which returns a set containing only values that
appear in both sets s
and t
, and union
, which returns a set containing
all values that appear in either set s
or t
.
Your implementation for both functions should run in linear time in the length of the input sets.
(define (intersect s t)
'YOUR-CODE-HERE
)
(define (union s t)
'YOUR-CODE-HERE
)
Use Ok to unlock and test your code:
python3 ok -q intersect -u
python3 ok -q intersect
python3 ok -q union -u
python3 ok -q union