COMP9024 Practice Assignment-1: Implement a new ADT using the class library COMP9024 Data Structures and Algorithms Session 2, 2010 Practice Assignment 1: Implement a new ADT using the class library Please note that you must do this practice assignment in order to learn and acquire the required problem solving skills for the course. Some of the questions in the mid session exam and the final exam will be based on the exercises in this assignment. In week-4, I will release a test file that you could use to evaluate your solution. Please contact your lecturer if you have any problems, and also to receive feedback on your programming style and problem solving approaches. Aim: To understand how the class library can be used to define and implement a new ADT representing a set of strings. Part-1 (Implementing and testing a class) You need to implement an ADT that represents a set consisting of strings. For example, { "John", "Rita", "Lau", "Peter", "Ann", "Jenny" } The document that describes the required operations (also called API) of String Set ADT is at, StringSet.html Your task is to implement the class StringSet.java, using the class Vector available at java.util.Vector. In this exercise, the aim is to learn how to implement a new ADT using some of the basic java classes. You need to implement the above ADT using ONLY java.util.Vector class. Please note that Java provides classes that implement the Interface Set, however in this exercise do not use them. Also, later in the course we will discuss how to implement many of these methods/operations more efficiently. The class StringSet is partially implemented at, StringSet.java What to do Your task is to implement the required 9 (short) methods in the class StringSet.java. The partial implementation of StringSet.java is provided. It creates an instance of the class Vector in it's constructor. You could use methods provided by the class Vector in your implementation of the methods. Handling Exceptions You need to catch all the exceptions and can only throw exceptions of the types defined in the corresponding method headers (if any). For example, inside the method removeElement, you should catch all the exceptions and can only throw exception of type NoSuchElementException. The exception NoSuchElementException is defined (and implemented) at java.util.NoSuchElementException. Time Complexities The following table provides expected time complexities (using big-Oh notations) of the required 9 methods you need to implement. Note that, in general, we can improve some of the following time complexities. Later in the session we will discuss this topic in detail. For this assignment, your methods should provide time complexities equal to or better than (less than) the values provided in the following table. Operations Time size (already implemented), isEmpty, O(1) insertElement, removeElement, elementsWithPrefix, elements, isMember O(n) isSubset, union, intersect O(n2) The class "String" from the java API You may need to use methods from the class String (defined at java.lang.String). Please read the corresponding java API. Testing Your StringSet ADT The (partially completed) testing program TestStringSet.java is provided below, TestStringSet.java You need to modify the above testing program such that you can test all the required methods. You should test your implementation for few different inputs. The aim should be to test your implementation for common as well as uncommon cases. Please read the section on "Testing and Debugging" in the textbook. Part-2 (Documenting a class) You may want to learn how to automatically generate documentation files (in html format) for your ADT (*.java files). Java provides a very useful tool called "javadoc" to automatically generate document files from a given set of class files (*.java files). All the java APIs are also automatically generated using this tool. The document file StringSet.html provided for this assignment was also generated using "javadoc". You should first remove the documentation file provided for this assignment, that is StringSet.html. You can now generate a new document file for your StringSet.java using the following command. % javadoc StringSet.java The above command will generate a file named StringSet.html (along with few other files). Now view the file String.html. It lists all the methods from the file StringSet.java, and also provides brief descriptions for some of the methods. "javadoc" extracts comments from the source files (*.java files) and adds them to the documentation files (*.html files). However, "javadoc" can only extract comments that are written using a specific format. For example, documentation comments are only recognized when placed immediately before class, interface, constructor, method, or field declarations. Documentation comments should start with "/**" character string and end with "*/" character string. javadoc parses special tags (like @return, @exception, @param, etc) that are recognized when they are embedded within a Java doc comment. These doc tags enable you to autogenerate a complete, well-formatted API from your source code. The following pages describe "javadoc": How to Write Doc Comments for Javadoc Section titled "Javadoc" in your textbook Your task now is to modify comments in your StringSet.java such that "javadoc" can automatically generate a complete documentation file. Note that the file provided to you do not properly generate comments for some of the methods! Examples: Valid syntax: javadoc will be able to extract the following comments. /** Removes the string s from this set, if s is already in this set. * If s is not in this set, it throws an exception. * @param s a string * @exception NoSuchElementException if the string s is not in this set. */ public void removeElement(String s) throws NoSuchElementException { /** Returns a set (of type StringSet) that represents a union * of a given set 'Set' and this set. * @param Set a set of type StringSet. * @return a set (of type StringSet) representing a union of * a given set and this set. */ public StringSet union(StringSet Set){ Invalid syntax: javadoc will not be able to extract the following comments (why?). // Returns a set (of type StringSet) that represents an intersection // of a given set 'Set' and this set. public StringSet intersect(StringSet Set){ // Returns an enumeration of the elements in this set. public Enumeration elements(){ ... end ....
