4 hours ago

my attempt to do the exercises in sicp.

## Monday, July 21, 2008

### sicp exercise 2.60

;; Exercise 2.60. We specified that a set would be represented as a list with no duplicates. Now suppose we allow duplicates. For instance, the set {1,2,3} could be represented as the list (2 3 2 1 3 2 2). Design procedures element-of-set?, adjoin-set, union-set, and intersection-set that operate on this representation. How does the efficiency of each compare with the corresponding procedure for the non-duplicate representation? Are there applications for which you would use this representation in preference to the non-duplicate one?

(define true #t)

(define false #f)

(define (append list1 list2)

(cond ((null? list1) list2)

(else (cons (car list1) (append (cdr list1) list2)))))

(define (element-of-set? ele set)

(cond ((null? set) false)

((= (car set) ele) true)

(else (element-of-set? ele (cdr set)))))

(define (adjoin-set ele set)

(cons ele set))

(define (union-set set1 set2)

(append set1 set2))

(define (intersection-set set1 set2)

(cond ((or (null? set1) (null? set2)) (list))

((element-of-set? (car set1) set2) (cons (car set1) (intersection-set (cdr set1) set2)))

(else (intersection-set (cdr set1) set2))))

(define set1 (list 1 2 3 4 1 2 3))

(define set2 (list 9 8 3 1 3 8 9))

(define set3 (list 9 8 7 6 7 7 7))

(display (union-set set1 set2)) (newline)

(display (union-set set1 set3)) (newline)

(display (union-set set2 set3)) (newline)

(display (adjoin-set 100 set1)) (newline)

(display (intersection-set set1 set2)) (newline)

;; the adjoin-set and union-set can be done in O(1) instead of O(n) and O(n^2)

;; the element-of-set? and intersection-set are still O(n) and O(n^2)

Subscribe to:
Post Comments (Atom)

## No comments:

Post a Comment