HMWK4

Due: 6 April 2017, by end of class

1) Explain the two problems with abstract data types that are ameliorated by inheritance.

2) Explain one disadvantage of inheritance.

3) Consider the (pseudo-code) function:   defn fib x =  if x < 2 then 1 else fib(x-1) + fib (x-2);

Show the sequence of stack allocations in the execution of fib(5).

4) Write a ruby function which takes a list of sets, and returns the "union-reduced" list of sets.

that means:  If any pair of sets in the list have common member, they are replaced (in the list) by the union of the two sets.  Keep doing this until all of the remaining sets are disjoint.

E.g. start with:  (4 5 7) (3 10 11 13) (11 13) (8) (4 8 12 16) (7 12)

     (merge sets 1 & 2)   (4 5 7) (3 10 11 13) (8) (4 8 12 16) (7 12)

     (merge sets 2 & 3)   (4 5 7) (3 10 11 13) (4 8 12 16) (7 12)

     (merge sets 0 & 2)   (4 5 7 8 12 16) (3 10 11 13) (7 12)

     (merge sets 0 & 2)   (4 5 7 8 12 16) (3 10 11 13)

which is the result, as the remaining sets are disjoint.