Assignment 1

 

CS 3500 Assignment #1

Assigned:  Tuesday, January 8, 2013

Due:  Tuesday, January 15, 2013 Friday, January 18, 2013

        (Deadline changed when class for Tuesday, January 15, 2013 was canceled)


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 FSet 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.  Turn in your work on this

assignment before 11:59 pm on the due date by following instructions

on the course's main assignments web page,

http://www.ccs.neu.edu/course/cs3500sp13/Assignments.html


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. Assignments submitted between 12:00 am

and 11:59 pm the day after the due date will receive a 20 percentage point

penalty on the assignment.

-------------------------------------------------------------------------------------------------------


Your assignment is to write the code for a single file, FSet.java,

that implements the specification below.  A test program

(/course/cs3500sp13/Assignments/A1/TestFSet.java) will be provided.


-------------------------------------------------------------------------------------------------------


Specification of the FSet ADT.


FSet is an immutable abstract data type whose values represent

finite sets with elements of type Integer.


The FSet ADT shall be implemented in Java and will be tested on

CCIS Linux machines with only their standard software.

The code for this implementation shall be in the default package and

shall define a public class named FSet.  The operations of the

FSet class shall be provided by the following public methods

of the FSet class:


Signature:


  Static methods:


    emptySet  :                       ->  FSet

    include   : FSet x Integer        ->  FSet

    add       : FSet x Integer        ->  FSet

    size      : FSet                  ->  int

    isEmpty   : FSet                  ->  boolean

    contains  : FSet x Integer        ->  boolean

    isSubset  : FSet x FSet           ->  boolean

    remove    : FSet x Integer        ->  FSet

    union     : FSet x FSet           ->  FSet

    intersect : FSet x FSet           ->  FSet


  Dynamic methods (for which the receiver is an FSet):

    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:


    FSet.add (s, k)  =  s

                      if FSet.contains (s, k)

    FSet.add (s, k)  =  FSet.include (s, k)

                      if ! (FSet.contains (s, k))


    FSet.size (FSet.emptySet())  =  0

    FSet.size (FSet.include (s0, k0))

        =  FSet.size (s0)

                      if FSet.contains (s0, k0)

    FSet.size (FSet.include (s0, k0))

        =  1 + FSet.size (s0)

                      if ! (FSet.contains (s0, k0))


    FSet.isEmpty (FSet.emptySet())  =  true

    FSet.isEmpty (FSet.include(s0, k0))  =  false


    FSet.contains (FSet.emptySet(), k)  =  false

    FSet.contains (FSet.include (s0, k0), k)

        =  true

                      if k.equals(k0)

    FSet.contains (FSet.include (s0, k0), k)

        =  FSet.contains (s0, k)

                      if ! (k.equals(k0))


    FSet.isSubset (FSet.emptySet(), s2)  =  true

    FSet.isSubset (FSet.include (s0, k0), s2)

        =  FSet.isSubset (s0, s2)

                      if FSet.contains (s2, k0)

    FSet.isSubset (FSet.include (s0, k0), s2)

        =  false 

                      if ! (FSet.contains (s2, k0))


    FSet.remove (FSet.emptySet(), k)  =  FSet.emptySet()

    FSet.remove (FSet.include (s0, k0), k)

        =  FSet.remove (s0, k)

                      if k.equals(k0)

    FSet.remove (FSet.include (s0, k0), k)

        =  FSet.include (FSet.remove (s0, k), k0)

                      if ! (k.equals(k0))


    FSet.union (FSet.emptySet(), s2)  =  s2

    FSet.union (FSet.include (s0, k0), s2)

        =  FSet.union (s0, s2)

                      if FSet.contains (s2, k0)

    FSet.union (FSet.include (s0, k0), s2)

        =  FSet.include (FSet.union (s0, s2), k0)

                      if ! (FSet.contains (s2, k0))


    FSet.intersect (FSet.emptySet(), s2)  =  FSet.emptySet()

    FSet.intersect (FSet.include (s0, k0), s2)

        =  FSet.include (FSet.intersect (s0, s2), k0)

                      if FSet.contains (s2, k0)

    FSet.intersect (FSet.include (s0, k0), s2)

        =  FSet.intersect (s0, s2)

                      if ! (FSet.contains (s2, k0))


    s.toString() = "{...(" + FSet.size(s) + " elements,

          contains 2: " + FSet.contains(s, 2) + ")...}"


Values of the FSet ADT shall also implement the public

dynamic methods equals(Object) and hashCode() such that


    If s1 is a value of the FSet ADT, then


        s1.equals(null) returns false.


    If s1 is a value of the FSet ADT, but x is not, then


        s1.equals(x) returns false.


    If s1 and s2 are values of the FSet ADT, then

    s1.equals(s2) if and only if


        for every Integer k


            FSet.contains (s1, k) if and only if

            FSet.contains (s2, k)


    If s1 and s2 are values of the FSet ADT, and


        s1.equals(s2)


    then s1.hashCode() == s2.hashCode().