The focus of this section is on representing mathematical sets with Scheme’s builtin data structures, and methods of combining these data structures to enable us to write faster algorithms for performing set operations. We go from a basic list based representation, to binary trees. I found this section to be quite a test of my abstract thinking skills; visualizing the operations on the representations was quite difficult for me.
;;Exercise 2.59
Implementing unionset is fairly straightforward for the unorderedlist representation.
(define (unionset set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((elementofset? (car set1) set2)
(unionset (cdr set1) set2))
(else (cons (car set1) (unionset (cdr set1) set2)))))
;;Exercise 2.60
This exercise was pretty interesting, it makes you think about situations in which what would seem to be an inefficient algorithm is actually the best for a job. Here’s my implementation of the set operations for an unordered set which allows duplicates.
(define (elementofset? x set)
(cond ((null? set) false)
((equal? x (car set)) true)
(else (elementofset? x (cdr set)))))
(define (adjoinset x set)
(cons x set))
(define (intersectionset set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((elementofset? (car set1) set2)
(cons (car set1)
(intersectionset (cdr set1) set2)))
(else (intersectionset (cdr set1) set2))))
(define (unionset set1 set2)
(append set2 set1))
From the code we can see that, when duplicates are allowed,

elementofset?
is still O(n) 
adjoinset
is O(1) from O(n) 
intersectionset
is still O(n^2) 
unionset
is O(n) from O(n^2)
By allowing duplicates, we have sped things up quite a bit, even if the algorithms are going to use up a lot more memory. In choosing which algorithm to use in a certain situation, we need to take into account the environment it will be used in. If we are, for example, on a machine with limited CPU speed, but a lot of memory (not uncommon in machines that have been upgraded), the duplicate representation would be best. On the other hand, if we were dealing with huge numbers, it would be a big drain on memory to use the duplicate representation, and the nonduplicate representation would be better for keeping overhead down.
;;Exercise 2.61
Now we’re starting to optimize the representations a bit more, it’s really neat to see how simple ideas like ordering the sets can produce fairly large performance gains :)
(define (adjoinset x S)
(cond ((null? S) (list x))
((< x (car S)) (cons x S))
((> x (car S)) (cons (car S) (adjoinset x (cdr S))))
((= x (car S)) S)))
The orderedlist representation will take less time to adjoin, on the average, because we will not necessarily have to process the whole list in order to know if a duplicate exists.
;;Exercise 2.62
This particular exercise required a fair bit of thought. Here’s my explanation.
If the first element of set1 is less than the first element of set2, we make that element the car of a new list, and the cdr of the new list is the union of the cdr of set1 and set2…
(define (unionset set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((< (car set1) (car set2))
(cons (car set1) (unionset (cdr set1) set2)))
((> (car set1) (car set2))
(cons (car set2) (unionset set1 (cdr set2))))
((= (car set1) (car set2))
(cons (car set1)
(unionset (cdr set1)
(cdr set2))))))
;;Exercise 2.63
;;A
I think this exercise is designed to see how well we can transform a diagram into the actual representation of a tree as the most difficult part was writing down the trees :D
(define tree1 (maketree 7
(maketree 3
(maketree 1 '() '())
(maketree 5 '() '()))
(maketree 9
'()
(maketree 11 '() '()))))
(define tree2 (maketree 3
(maketree 1 '() '())
(maketree 7
(maketree 5 '() '())
(maketree 9
'()
(maketree 11 '() '())))))
(define tree3 (maketree 5
(maketree 3
'()
(maketree 1 '() '()))
(maketree 9
(maketree 7 '() '())
(maketree 11 '() '()))))
After running these through both functions, you’ll see that both the recursive and iterative procedures produce the same result, which is expected if they are to do the same job…
;B
Yes, they both have the same order of growth, however tree>list2 uses less memory than tree>list3, and thus could be faster in certain situations.
;;Exercise 2.64
Partialtree
works in a very recursive fashion :)
The best way I can explain is to work through an example.
Let’s say we have the list '(1 2 3 4 5)
to turn into a tree.
Partialtree
first assigns equal, or almost equal sizes for the left and right branch of the new tree. So for our tree leftsize
will be 2, and rightsize
will be 3 (because the size of the list is not even). Then, partial tree
cons
es together the result of partialtree
on the left and right halves of the given list. It’s quite a bit for me to wrap my head around, to be sure!
;;Exercise 2.65
Still a work in progress for me…
;;Exercise 2.66
The lookup
procedure is basically elementofset?
, except instead of returning true or false, we return the item requested by key, or false if it’s not found.
(define (lookup key records)
(cond ((null? records) false)
((= key (entry records)) (recordvalue (entry records)))
((< key (entry records))
(lookup key (leftbranch records)))
((> key (entry records))
(lookup key (rightbranch records)))))
;;Where a record structure looks like
(define (makerecord key value)
(cons key value))