Solution Files

Hinting

Homework 7 includes a hinting sytem that generates hints specifically for your submitted code. If you ever find yourself stuck, you can ask for hints by using adding the --hint flag to the ok command.

$ python3 ok -q pow --hint
...
Hint: There are extra parentheses on line ...

The system tries to generate hints specific to your program by applying multiple techniques, including:

Question 1

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)
(car (cdr s))
) (define (caddr s)
(car (cddr s))
)

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>))

consisting 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 #f are interpreted as true values (unlike Python). (Our particular version of the Scheme interpreter allows you to write True and False in place of #t and #f, and prints boolean values as True and False. This is not standard.)

Conditional expressions are evaluated as follows. The predicate <p1> is evaluated first. If its value is #f, then <p2> is evaluated. If <p2>'s value is also #f, then <p3> is evaluated. This process continues until the first predicate <pi> is found whose value is true, in which case the interpreter returns the result of evaluating each of the corresponding list of consequent expressions <eli> and returning the last value as the value of the whole conditional expression. The else keyword, if present, is taken to be true, so that if none of the <p>'s is found to be true, the interpreter evaluates the else-expressions and returns the last value. If no clause has a true predicate, the result is an "unspecified value". Unless some of the consequent expressions have side-effects, there is no point in having more than one in a list <eli>.

This is a somewhat simplified version of the semantics of cond, covering the cases we usually encounter.

Question 2

Using cond, define a procedure sign that returns -1 for negative arguments, 0 for zero, and 1 for positive arguments:

(define (sign x)
(cond ((> x 0) 1) ((= x 0) 0) ((< x 0) -1))
)

Use OK to unlock and test your code:

python3 ok -q sign -u
python3 ok -q sign

Question 3: 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:

  1. b2k = (bk)2
  2. b2k+1 = b(bk)2

You may use the built-in predicates even? and odd?.

(define (square x) (* x x))

(define (pow b n)
(cond ((= n 0) 1) ((even? n) (square (pow b (/ n 2)))) (else (* b (pow b (- n 1)))))
)

Use OK to unlock and test your code:

python3 ok -q pow -u
python3 ok -q pow

Question 4

Implement a procedure called ordered?, which takes a list of numbers and returns True if the numbers are in nondescending order, and False otherwise.

Hint: The built-in null? function returns whether its argument is nil.

(define (ordered? s)
(if (or (null? s) (null? (cdr s))) true (and (<= (car s) (cadr s)) (ordered? (cdr s))))
)

Use OK to unlock and test your code:

python3 ok -q ordered -u
python3 ok -q ordered

Question 5

Implement the procedure nodots, which takes a nested list of numbers that may not be well-formed and returns a nested list with the same content and structure, but which does not have any dots when displayed. Lists are not well-formed if they do not properly terminate in a null list. In such cases, the list will print with a dot before the final item to indicate that its last two items are contained in a single pair. For example,

(cons 1 (cons 2 3))

would print as

(1 2 . 3)

for which nodots should substitute

(1 2 3)

You may find the built-in null? and pair? predicates useful.

(define (nodots s)
(define (dotted s) (and (pair? s) (not (or (pair? (cdr s)) (null? (cdr s)))))) (cond ((null? s) s) ((dotted s) (list (nodots (car s)) (cdr s))) ((pair? s) (cons (nodots (car s)) (nodots (cdr s)))) (else s))
)

Use OK to unlock and test your code:

python3 ok -q nodots -u
python3 ok -q nodots

Sets as Ordered Lists

One way to represent a set is by using an ordered list, where the ordering is used to speed up search (although only by a constant factor). The following few questions explore this idea, assuming a "set" is a Scheme list with no repeated elements that is already ordered from least to greatest.

Question 6

Define contains?, which returns whether a set s contains value v. 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)
((> (car s) v) false) ((= (car s) v) true) ((< (car s) v) (contains? (cdr s) v))
)) ; Equivalent Python code, for your reference: ; ; def empty(s): ; return s is Link.empty ; ; 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)

Use OK to unlock and test your code:

python3 ok -q contains -u
python3 ok -q contains

Question 7

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.

(define (add s v)
    (cond ((empty? s) (list v))
((= (car s) v) s) ((> (car s) v) (cons v s)) ((< (car s) v) (cons (car s) (add (cdr s) v)))
))

Use OK to unlock and test your code:

python3 ok -q add -u
python3 ok -q add

Question 8

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. A 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)
((= (car s) (car t)) (cons (car s) (intersect (cdr s) (cdr t)))) ((< (car s) (car t)) (intersect (cdr s) t)) ((> (car s) (car t)) (intersect s (cdr t)))
)) ; 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 (union s t) (cond ((empty? s) t) ((empty? t) s)
((= (car s) (car t)) (cons (car s) (union (cdr s) (cdr t)))) ((< (car s) (car t)) (cons (car s) (union (cdr s) t))) ((> (car s) (car t)) (cons (car t) (union s (cdr t))))
))

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

Question 9: Survey

Please fill out the midsemester survey. You will receive a passphrase after finishing the survey to submit with the homework.

(define (survey)
     'passphrase-here
      )

Use OK to unlock and test your code:

python3 ok -q survey -u
python3 ok -q survey