211 F '05
Set 1
Set 2
Set 3
Set 4
Set 5
Set 6
Set 7
Set 8
Set 9
Set 10
Set 11
Set 12
Set 13
Set 14

Problem Set 7

If you run any of the functions (as opposed to just testing them), comment out the code for running the functions before you submit your solution.

N.B.: Tests are not runs. A test is when you evaluate an expression and compare it to some expected result, while a run is when you evaluate an expression without anticipating any particular result for the expression.

Due date: 10/28 @ NOON

The purpose of this problem set is to revisit self-referential data definitions and to understand functions that consume several complex arguments at once (multiplexing).

You will benefit from local definitions for this problem set though you can solve all problems without this knowledge.

HtDP Problems:

recursion: 14.1.3, 14.1.5, 14.3.3, 14.4.1, 14.4.2, 14.4.3, 14.4.4

multiplexing: 17.7.1, 17.7.2, 17.7.3, 17.7.4

Additional Problem 1:

Design the function find-sublist. It consumes two lists of symbols, big and pat, and determines whether the latter occurs en-block somewhere in the former.

Additional Problem 2:

A set is a collection of things that are all mutually distinct.

You can represent a set of symbols as a list of symbols such that all symbols are mutually unequal (symbol=?).

Design the function element-of?, which determines whether a given element is in a given set.

Design the function add-element, which consumes a symbol and a set and constructs a new set that includes this symbol.

Design the function remove-element, which removes a given symbol from a given set. Hint: Is it always true that

    (boolean=? (element-of? e (remove-element e s)) false)

for all elements e and sets s?

Design the function union, which creates a set from the elements of two given sets.

Design the function intersect, which creates a set from the elements that are common to two given sets.

Additional Problem 3:

[Note: This problem continues problem 2.]

A relation is a set of tuples. For illustrative purposes, we use tuples of symbols:

;; A tuple is (list Symbol Symbol). 
;; Example:
(define a-tuple '(a b))

;; A relation is a set of tuples.

Design the function domain, which collects all firsts from a given relation in a set.

Design the function range, which collects all seconds from a given relation in a set.

Design the function at. It consumes a set Sand a relation R. Its purpose is to collect all the seconds from all tuples in R whose first is a member of S.

Design the function x. It consumes two sets and creates a relation that combines all elements from the first set with all elements from the second set. Example:

(equal? (x '(a b) '(x y z))
        '((a x) (a y) (a z) (b x) (b y) (b z)))

Challenge Problem [no points]:

This data definition describes a tree of symbols:

(define-struct node (name left right))
;; Tree = empty | (make-node Symbol Tree Tree)

Design a function that consumes such a tree and produces an image of the tree. The function should draw each leaf (empty) as a red bullet and each branch as the combination of two trees via a fork:

 ;; draw-fork : Number String -> Image 
 ;; produce a branching picture like this: 
 ;; |               |
 ;; +-------+-------+ 
 ;;         |
 ;; width: w; left up at 1/4 * w; 
 ;;           right up at 3/4 * w; 
 ;;           down at 1/2 * w
 ;; pinhole @ (0,0)
 (define (draw-fork w label) ...)

The left and the right tree should sit on top of the left and right branch of the fork, respectively; both should use the same width. The downward stem should be centered. Hint: Design functions that help you compose images vertically and horizontally; both should consume images whose pinhole is at (0,0).


sample tree

last updated on Sat Nov 26 15:34:41 EST 2005generated with PLT Scheme