Due by 11:59pm on Wednesday, 11/5
Submission: See Lab 1 for submission instructions. We have provided a hw7.scm starter file for the questions below.
Readings: You might find the following references useful:
To complete this homework assignemnt on your own computer, you will either need to install Scheme or use our online Scheme interpreter.
You can load the starter file in STK using the command
stk -load hw7.scmScheme does not have a built-in testing framework. To verify behavior, we will
use the following assert-equal procedure, which tests whether an expression
evaluates to an expected value.
(define (assert-equal value expression)
(if (equal? value (eval expression))
(print 'ok)
(print (list 'for expression ':
'expected value
'but 'got (eval expression)))))When you evaluate your solution, a long sequence of ok should be displayed.
Any test failures will describe the error instead.
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
nil)
(define (caddr s)
; YOUR CODE HERE
nil)
(define (test-car-cadr)
(assert-equal (list 3 4) '(cddr '(1 2 3 4)))
(assert-equal 2 '(cadr '(1 2 3 4)))
(assert-equal 3 '(caddr '(1 2 3 4))))
(test-car-cadr)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> <e1>)
(<p2> <e2>)
...
(<pn> <en>)
(else <else-expression>))consisting of the symbol cond followed by pairs of expressions (<p>
<e>) called clauses. The first expression in each pair is a
predicate: an expression whose value is interpreted as either true
or false.
Conditional expressions are evaluated as follows. The predicate <p1>
is evaluated first. If its value is false, then <p2> is evaluated.
If <p2>'s value is also false, then <p3> is evaluated. This
process continues until a predicate is found whose value is true, in
which case the interpreter returns the value of the corresponding
consequent expression <e> of the clause as the value of the
conditional expression. If none of the <p>'s is found to be true,
the interpreter returns the value of the else expression.
The word "predicate" is used for procedures that return true or
false, as well as for expressions that evaluate to true or false.
Using cond, define a procedure sign that returns -1 for negative
arguments, 0 for zero, and 1 for positive arguments:
(define (sign x)
; YOUR CODE HERE
nil)
(define (test-sign)
(assert-equal -1 '(sign -42))
(assert-equal 0 '(sign 0))
(assert-equal 1 '(sign 42)))
(test-sign)Define the procedure gcd that uses the
Euclidean algorithm
to find the greatest common divisor of two positive integers:
(define (gcd m n)
; YOUR CODE HERE
nil)
(define (test-gcd)
(assert-equal 4 '(gcd 12 8))
(assert-equal 4 '(gcd 12 16))
(assert-equal 8 '(gcd 16 8))
(assert-equal 6 '(gcd 24 42))
(assert-equal 5 '(gcd 5 5)))
(test-gcd)Implement a procedure pow for raising the number b to the power of
integer n that runs in Theta(log n) time. Hint: Use the built-in
predicates even? and odd? and the square procedure to implement
the procedure using successive squaring, as we did in lecture:
(define (square x) (* x x))
(define (pow b n)
; YOUR CODE HERE
nil)
(define (test-pow)
(assert-equal 1024 '(pow 2 10))
(assert-equal 1000 '(pow 10 3))
(assert-equal 243 '(pow 3 5)))
(test-pow)Write the predicate ordered?, which takes a list of numbers and
returns whether the numbers are in ascending order.
(define (ordered? lst)
; YOUR CODE HERE
nil)
(define (test-ordered?)
(assert-equal true '(ordered? '(1 2 3 4 5)))
(assert-equal false '(ordered? '(1 5 2 4 3))))
(test-ordered?)One way to represent a set is to store the elements in a sorted list that
contains no repeated elements. Define a procedure contains? that returns
whether a set s contains value v, assuming s is represented in this way.
The Python implementation of this procedure is provided for your reference.
; Sets as sorted lists
(define (empty? s) (null? s))
(define (contains? s v)
(cond ((empty? s) false)
; YOUR CODE HERE
(else nil)
))
; Equivalent Python code, for your reference:
;
; def empty(s):
; return len(s) == 0
;
; def contains(s, v):
; if empty(s):
; return False
; elif s.first > v:
; return False
; elif s.first == v:
; return True
; else:
; return contains(s.rest, v)
(define odds (list 3 5 7 9))
(define (test-contains)
(assert-equal true '(contains? odds 3))
(assert-equal true '(contains? odds 9))
(assert-equal false '(contains? odds 6)))
(test-contains)Next, define append, 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.
(define (append s v)
(cond ((empty? s) (list v))
; YOUR CODE HERE
(else nil)
))
(define (test-append)
(assert-equal '(2 3 5 7 9) '(append odds 2))
(assert-equal '(3 5 7 9) '(append odds 5))
(assert-equal '(3 5 6 7 9) '(append odds 6))
(assert-equal '(3 5 7 9 10) '(append odds 10)))
(test-append)Next, define intersect, which returns a set containing only values that
appear in both sets s and t. Your implementation should run in linear time
in the length of the input sets. The Python implementation of this procedure is
provided for your reference.
Also, define union, which returns a set containing all values that appear
in either set s or t.
(define (intersect s t)
(cond ((or (empty? s) (empty? t)) nil)
; YOUR CODE HERE
(else nil)
))
; Equivalent Python code, for your reference:
;
; def intersect(set1, set2):
; if empty(set1) or empty(set2):
; return Link.empty
; else:
; e1, e2 = set1.first, set2.first
; if e1 == e2:
; return Link(e1, intersect(set1.rest, set2.rest))
; elif e1 < e2:
; return intersect(set1.rest, set2)
; elif e2 < e1:
; return intersect(set1, set2.rest)
(define eight (list 1 2 3 4 5 6 7 8))
(define (test-intersect)
(assert-equal '(3 5) '(intersect odds (list 2 3 4 5)))
(assert-equal '() '(intersect odds (list 2 4 6 8)))
(assert-equal '(3 5 7) '(intersect odds eight)))
(define (union s t)
(cond ((empty? s) t)
((empty? t) s)
; YOUR CODE HERE
(else nil)
))
(define (test-union)
(assert-equal '(2 3 4 5 7 9) '(union odds (list 2 3 4 5)))
(assert-equal '(2 3 4 5 6 7 8 9) '(union odds (list 2 4 6 8)))
(assert-equal '(1 2 3 4 5 6 7 8 9) '(union odds eight)))
(test-intersect)
(test-union)Another way to represent a set is to store the elements in a binary search tree. A binary search tree's branches are either empty or binary search trees. Also, the entry at the root of the tree must be greater than all entries in the left branch and less than all entries in the right branch.
The following procedures define a data abstraction for a binary search tree.
; A data abstraction for binary trees where nil represents the empty tree
(define (tree entry left right) (list entry left right))
(define (entry t) (car t))
(define (left t) (cadr t))
(define (right t) (caddr t))
(define (empty? s) (null? s))
(define (leaf entry) (tree entry nil nil))Define the procedure in?, which returns whether a binary search tree t
contains an element v. Your implementation should run in logarithmic time in
the number of entries in a balanced input tree. The Python implementation of
this procedure is provided for your reference.
(define (in? t v)
(cond ((empty? t) false)
; YOUR CODE HERE
(else nil)
))
; Equivalent Python code, for your reference:
;
; def contains(s, v):
; if s.is_empty:
; return False
; elif s.entry == v:
; return True
; elif s.entry < v:
; return contains(s.right, v)
; elif s.entry > v:
; return contains(s.left, v)
(define odd-tree (tree 3 (leaf 1)
(tree 7 (leaf 5)
(tree 9 nil (leaf 11)))))
(define (test-in?)
(assert-equal true '(in? odd-tree 1))
(assert-equal false '(in? odd-tree 2))
(assert-equal true '(in? odd-tree 3))
(assert-equal false '(in? odd-tree 4))
(assert-equal true '(in? odd-tree 5)))
(test-in?)Define as-list, which takes a binary search tree and returns a sorted list
containing the entries of the tree. For an optional challenge, define the
procedure so that it runs in linear time in the length of the resulting list.
Converting to and from the sorted list representation in linear time allows
binary search trees to be intersected in linear time.
(define (as-list t)
; YOUR CODE HERE
nil
)
(define (test-as-list)
(assert-equal '(5 7 9 11) '(as-list (right odd-tree)))
(assert-equal '(1 3 5 7 9 11) '(as-list odd-tree)))
(test-as-list)