CS 3500 - Assignment #1 Due: Tuesday, September 17, 2013 at 11:59 pm The purpose of this assignment is: * To review basic Java programming concepts * To review static methods in Java * To review the Java API (application programming interface) * To acquaint you with the development system you choose to use * To learn the required process for submitting homework in this course * To begin our study of abstraction-based software design with an algebraic specification for an abstract data type of immutable sets You will complete an implementation in Java of the FSetString ADT that is specified below. Collaboration between students is forbidden on this assignment. You are responsible for keeping your code hidden from all other students. You will submit this assignment within Web-CAT. Your file of Java code should begin with a block comment that lists 1. Your name, as you want the instructor to write it. 2. Your email address. 3. Any remarks that you wish to make to the instructor. Part of your grade will depend on the quality and correctness of your code, part will depend on the readability of your code(comments and indentation), and part will depend on how well you follow the procedure above for submitting your work. Late assignments may be discounted, and very late assignments may be discarded. This assignment is worth 60 points: 25 points for automated code style, 25 points for automated testing, 10 points for TA grading. -------------------------------------------------- Your assignment is to write the code for a single file, FSetString.java, that implements the specification below. A test program (/course/cs3500f13/Assignments/A1/TestFSetString.java) will be provided. Alternate access: http://www.ccs.neu.edu/home/vkp/3500-fl13/TestFSetString.java The design recipe for implementing classes based on the algebraic specification can be found at http://www.ccs.neu.edu/home/vkp/3500-fl13/recipe.txt -------------------------------------------------- Specification of the FSetString ADT. FSetString is an immutable abstract data type whose values represent finite sets with elements of type String. The FSetString ADT shall be implemented in Java and will be tested using Sun's Java 2 Runtime Environment, Standard Edition, version 1.6.0. The code for this implementation shall be in the default package, and shall define a public class named FSetString. The operations of the FSetString class shall be provided by the following public methods of the FSetString class: Signature: Public static methods: emptySet : -> FSetString insert : FSetString x String -> FSetString add : FSetString x String -> FSetString size : FSetString -> int isEmpty : FSetString -> boolean contains : FSetString x String -> boolean isSubset : FSetString x FSetString -> boolean absent : FSetString x String -> FSetString union : FSetString x FSetString -> FSetString intersect : FSetString x FSetString -> FSetString Public dynamic methods (for which the receiver is an FSetString): toString : -> String equals : Object -> boolean hashCode : -> int Restrictions: Null arguments may not be passed to any of the above methods except for equals(Object). Algebraic specification: FSetString.add(s0, k0) = s0 if FSetString.contains(s0, k0) FSetString.add(s0, k0) = FSetString.insert(s0, k0) if !(FSetString.contains(s0, k0)) FSetString.size(FSetString.emptySet()) = 0 FSetString.size(FSetString.insert(s0, k0)) = FSetString.size(s0) if FSetString.contains(s0, k0) FSetString.size(FSetString.insert(s0, k0)) = 1 + FSetString.size(s0) if !(FSetString.contains(s0, k0)) FSetString.isEmpty(FSetString.emptySet()) = true FSetString.isEmpty(FSetString.insert(s0, k0)) = false FSetString.contains(FSetString.emptySet(), k) = false FSetString.contains(FSetString.insert(s0, k0), k) = true if k.equals(k0) FSetString.contains(FSetString.insert(s0, k0), k) = FSetString.contains(s0, k) if !(k.equals(k0)) FSetString.isSubset(FSetString.emptySet(), s2) = true FSetString.isSubset(FSetString.insert(s0, k0), s2) = FSetString.isSubset(s0, s2) if FSetString.contains(s2, k0) FSetString.isSubset(FSetString.insert(s0, k0), s2) = false if !(FSetString.contains(s2, k0)) FSetString.absent(FSetString.emptySet(), k) = FSetString.emptySet() FSetString.absent(FSetString.insert(s0, k0), k) = FSetString.absent(s0, k) if k.equals(k0) FSetString.absent(FSetString.insert(s0, k0), k) = FSetString.insert(FSetString.absent(s0, k), k0) if !(k.equals(k0)) FSetString.union(FSetString.emptySet(), s2) = s2 FSetString.union(FSetString.insert(s0, k0), s2) = FSetString.union(s0, s2) if FSetString.contains(s2, k0) FSetString.union(FSetString.insert(s0, k0), s2) = FSetString.insert(FSetString.union(s0, s2), k0) if !(FSetString.contains(s2, k0)) FSetString.intersect(FSetString.emptySet(), s2) = FSetString.emptySet() FSetString.intersect(FSetString.insert(s0, k0), s2) = FSetString.insert(FSetString.intersect(s0, s2), k0) if FSetString.contains(s2, k0) FSetString.intersect(FSetString.insert(s0, k0), s2) = FSetString.intersect(s0, s2) if !(FSetString.contains(s2, k0)) s.toString() = "{...(" + FSetString.size(s) + " elements)...}" Values of the FSetString ADT shall also implement the public dynamic methods equals(Object) and hashCode() such that If s1 is a value of the FSetString ADT, then s1.equals(null) returns false. If s1 is a value of the FSetString ADT, but x is not, then s1.equals(x) returns false. If s1 and s2 are values of the FSetString ADT, then s1.equals(s2) if and only if for every String k FSetString.contains(s1, k) if and only if FSetString.contains(s2, k) If s1 and s2 are values of the FSetString ADT, and s1.equals(s2) then s1.hashCode() == s2.hashCode(). -------------------------------------------------- Warning: -------- Do not wait until the last minute to submit your work. Do it early and often - there is no limit on the number of submissions and you can retrieve your earlier submissions as if they were saved in a version control system. It takes a bit of time to do the automatic grading and the system can be slow when too many students are submitting simultaneously.