CS212 Exams
Spring 1997 - Prelim 1

Abstraction

In this problem you will be implementing sets of numbers in terms of lists. For the purposes of this problem, the operations element-of-set?, adjoin-set, and intersection-set are defined on sets, and must obey the following contract:

As you can see the contract is missing -- I'm looking for it, so when I find it, I'll post it.

 

  1. Write the procedure intersection-set for this implementation of sets as unordered lists.





  2. What is the order of growth of your procedure as a function of the sizes of the two sets, m and n? Briefly justify your answer.




  3. Now we consider re-implementing sets as ordered lists, using the following definitions
(define (adjoin-set x set)
  (cond ((empty? set) (list x))
        ((= x (head set)) set)
        ((< x (head set)) (cons x set))
        (else (cons (head set)
                    (adjoin-set x (tail set))))))

(define (element-of-set? x set)
  (cond ((empty? set) #f)
        ((= x (head set)) #t)
        ((< x (head set)) #f)
        (else (element-of-set? x (tail set)))))

Write a linear time implementation of intersection-set given this new ordered representation of sets (i.e., for two sets of length m and n your procedure should run in time O(m+n).)







Solution

Return to CS 212 Prelim 1 - Spring 1997