CS 342 Additional Homework for Chapter 6 Due: March 18, 1992 General directions: be sure we have given you some specific help (either in recitation or personally) with each problem before solving these additional problems. 1. 2. (To make up for problem 2 on page 266). A "Bag" or multiset is like a set except that an element may occur many times. Implement a Bag cluster which has the following operations empty: -> Bag empty?: Bag -> Bool insert_once: Bag, Elem -> () modifies: the first argument effect: inserts the element into the bag as a side-effect insert_n: Bag, Elem, Int -> () modifies: the first argument effect: inserts the element into the bag the given number of times multiplicity: Bag, Elem -> Int effect: returns the number of times the element occurs in the bag; uses = to compare elements. delete_once: Bag, Elem -> () modifies: the first argument effect: if the element is in the bag, remove one occurrence of it; uses = to compare elements. delete_all: Bag, Elem -> () modifies: the first argument effect: if the element is in the bag, remove all occurrences of it; uses = to compare elements. size: Bag -> Int equal: Bag, Bag -> Bool effect: return true if the arguments have the same abstract value. 3. (To make up for problem 5 on page 267). Implement a cluster Complex of complex numbers (a+bi). You should include at least the following operations: create: Int, Int -> Complex add, sub, mul, div: Complex, Complex -> Complex equal: Complex, Complex -> Bool and any other operations you think necessary or useful. Part of your grade will be on how well these are designed. None of the operations of a Complex number should change the number, that is, this is to be an immutable type. 4. (To make up for problem 7 on page 267) The new release of the X window system allows circular and even oval windows. This problem deals with circular windows, called Disks. The abstract value of a Disk is a circular region in the X-Y plane. Implement a cluster Disk with the following operations: new: Point, Int -> Disk requires: the Int argument is not negative effect: return a new Disk whose center is the given point, with the given radius center: Disk -> Point effect: return the center of the given Disk radius: Disk -> Int effect: return the radius of the given Disk empty?: Disk -> Int effect: return true if and only if the radius of the given Disk is 0 contains: Disk, Point -> Bool effect: return true if and only if the given Point is contained withing the given disk, or on its boundary. intersect?: Disk, Disk -> Bool effect: return true if and only if there are integers x and y such that the point (x,y) is in both the disks. intersection: Disk, Disk -> Disk effect: return a new Disk, all of whose points are contained in both argument Disks, and which has the largest radius of all such Disks. move: Disk, Point -> () effect: change the state of the Disk argument so that the new center of the given Disk is the given point grow: Disk, Int effect: change the state of the Disk argument so that the new radius of the given Disk is old radius plus the given integer. 5. 6. (To make up for problem 6) You should read sections 6.1 of the text and section 6.7 paying special attention to 6.7.3. (a) In Section 6.4 of the text, the author describes Polynomials. From his description, what are: (i) the abstract values of the objects, (ii) a vocabulary or notation for abstractly manipulating the abstract values, (iii) and the operations on the objects, giving for each operation its name, type, and a English description of its effect, using the notations or vocabulary of (ii). (b) Do the same thing (parts i-iii) for the cluster Array described on pages 217-218 of the text.