211 F '06
The Hand In
The Recipes
The World
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 11

Due date: 11/21 @ 6pm

Programming Language: Intermediate Student Language with lambda

Problem 0 [5%]:

Find one interesting article from the weeks news on the use of software/computers in society. Summarize the article in your own words with a single 200-word paragraph, as a pair, one playing writer, the other playing editor. Add both the article and the summary in with the rest of your problem set.

The goal of this problem set is to practice the design of generative recursive functions and the use of data representations that employ first-class functions.

HtDP Problems:

Solve problems 27.1.4 and 27.1.5 using the world.ss teachpack.
27.3.1, 27.3.6, 28.2.1, 28.2.2, 28.2.3, 28.2.4

Problem A1:

An important idea in program design is programming to interfaces. Someone will tell you that there is a class of data, e.g., Set, and then list the functions that are available for this class, e.g.,
contains Set Anything -> Boolean

does s contain x?

(define (contains s x) ...)
add-element Set Anything -> Set

create a set that contains x and all the elements in s and

(define (add-element s x) ...)
lst->set [Listof Anything] -> Set

create a set from the elements of l

(define (lst->set l) ...)
union Set Set -> Set

create a set from all the elements that are in s or t

(define (unions s t) ...)
intersection Set Set -> Set

create a set from all the elements that are in s and t

(define (intersection s t) ...)
minus Set Set -> Set

create a set from all the elements that are in s but not in t

(define (minus s t) ...)
X Set Set -> Set

create the set that pairs all elements from s with all elements from t

(define (X s t) ...)
where Anything is the class of all Scheme objects.

When someone else wants to program with sets, you tell them to use the above conventions. You can implement (design) the data representation and the interface functions in many different ways.

In class, we have discussed two distinct representations of sets: lists and functions. The former are simple, the latter can represent infinite sets. Your tasks are:

  1. Let Set = [Listof Anything] without repetition. Design all of the above functions. Make up your own favorite representation of pairs.
  2. Let Set = [Anything -> Boolean]. Design all of the above functions. Use the same test suite for both implementations.
  3. Add test cases that show how the function-based representation can deal with larger sets than the list-based one.
  4. Add test cases that show how the list-based representation can deal with lists that do contain the same element more than once.
  5. Run the following stress tests on your two implementation of the X function and report your results:
    ;; Set Set Anything [Set Set -> Set] -> Boolean 
    ;; create the cross-product X of set1 and set2, 
    ;; then check whether element is in the result
    (define (test set1 set2 element X)
      (local ((define N 10000)
              (define (xxx i) (X set1 set2))
              (define lst* (time (build-list N xxx)))
              (define the-set (list-ref lst* (random N))))
        (time (contains the-set element))))
    (test some-set another-set some-element X)
    A report consists of the following items: computer (Dell Pentium II, Mac OS 9 PPC, etc); memory; version of drscheme; times reported.

last updated on Thu Nov 30 11:55:15 EST 2006generated with PLT Scheme