Assignment 1

Assignment 1
CS 256
due September 29, 1998
100 points

Implement the candidate elimination algorithm, using the outline given in the file version.drs, and an implemenation of your choice of the concept space. The given code assumes selectors g, s, and (the dummy selector) rest, and constructor build-version-space for version spaces. It assumes selector example and predicate is-positive for classified examples, where the selector returns the example without the classification. Finally, it assumes a predicate covers? and functions immedspecs and immedgenls that return respectively the list of immediate specializations and generalizations of a concept.

If G and S converge before all test cases in the sequence have been seen, you may terminate the testing of the sequence. If they fail to converge after all test cases are seen, print the values of G and S after the last test case. Test with (a) the concept space of the card examples covered in class, and test sequences

  1. (+ (2 club))
    (- (3 spade))
    (- (k club))
    (+ (9 club))
  2. (+ (2 club))
    (- (q diamond))
    (- (5 club))
    (+ (k club))
    (+ (a spade))
  3. (+ (k heart))
    (+ (k diamond))
    (- (2 heart))
    (- (j diamond))
    (- (k club))
  4. (+ (k heart))
    (- (k diamond))
    (+ (2 heart))
  5. (+ (k heart))
    (- (k diamond))
    (- (2 heart))
    (+ (q heart))
and (b) the hierarchy of Figure 13.5, and test sequences
  1. (+ (small red ball))
    (+ (small white ball)
    (- (small red brick))
    (+ (large blue ball))
  2. (+ (small red ball))
    (+ (small white brick)
    (+ (large blue cube))
  3. the test instances of Figure 13.8, but with the first positive instance moved to the beginning.
  4. the test instances of Figure 13.8, but with the second positive instance moved to the beginning.
  5. the test instances of Figure 13.9.