CS 22

CS 22 -- Homework 6


Due: Monday, Feb. 4

  1. Read pp. 79-87
  2. Email solutions and evidence of testing for:
    1. Suppose we want to use lists to represent sets. Order and repetition are not important in sets, that is, the set {1, 2, 3} is equal to the set {3, 2, 1} is equal to the set {2, 2, 1, 3}. On the other hand, each of the lists '(1, 2, 3) , '(3, 2, 1) , and '(2, 2, 1, 3) are distinct as lists so the built-in equal? predicate will show them unequal. Your task is to define a setequal? predicate that will return #t if two lists (given as arguments) are equal as sets and return false if the two lists are not equal as sets.

      Hint 1: The sets, A and B are equal if A is contained in B and B is contained in A, where set containment is defined: X is contained in Y if every element of X is a member of Y. Earlier, we wrote a predicate memb? that would determine if a single element was a member of a list. It would be worth looking at this definition again. We ought to be able to define a predicate "contains?" that takes two lists as arguments and returns #t if the first argument is contained in the second when they are viewed as sets and returns #f if they are unequal as sets. Think about this.
      Hint2 (for contains?): A predicate that calls itself is reasonable here.
      You need a stopping condition. If A is empty (determined by the built-in predicate null?), then A is certainly contained in B.
      If the first element of A is not in B then A is certainly NOT contained in B.
      If the first element of A is in B, then A is contained in B if the rest of A is contained in B.

    2. page 60, ex1.30
    3. page 61, ex1.32a (use to make sum and product and test your new sum and product on some examples from SICP).


Please review Homework Policy, Good Programming Style, and Academic Integrity from the CS22 Web site.