The Task
Each student must write a collection class, which would be suitable to be kept in a class library. Note: your job is to write part of a library; in this assignment you should not use a collection class library (of course, you can still use the built-in arrays of Java, and you can use java.util.Scanner and the classes in java.lang and java.io, such as String).
The class you write must be be called RadixSearchTrie. It must have a constructor with no arguments, to produce an object representing an empty collection. It must be part of a package called GeneCollection; that is, the RadixSearchTrie.java file must be in a directory called GeneCollection.
To clients, this class should appear as an implementation of the interface GCInterface. The interface is as follows.
package GeneCollection;
/*
* This interface represents the API
* suitable for an object which keeps a collection
* of genes, each with associated information.
* A gene is given by a String, with the
* special property that every character is A, C, G or T.
* In real uses, the associated information would
* be voluminous, including discoverer, literature citation,
* species, chromosome identifier, location within chromosome,
* purpose, date first mentioned, etc etc;
* however for this simple example we will
* assume the associated information is just a String description.
*/
public interface GCInterface {
/*
* Find the description associated with a given gene.
* If the gene is not in the collection, return null.
*/
public String findDescription(String gene);
/*
* add a new gene to the collection, with an
* associated description.
* Neither argument may be null.
* If the gene is already present in the collection,
* the new description replaces the old;
* otherwise the new description and gene are added.
*/
public void newGene(String gene, String description);
/*
* return the number of genes in the collection.
*/
public int numberOfGenes();
/*
* return the number of genes in the collection
* which have a given gene as prefix.
*/
public int numberOfGenes(String prefix);
/*
* remove a gene and its associated description.
* This must not be called with a null argument.
*/
public void remove(String gene);
}
Internally, the collection class must be structured as a radix search trie.
As well as the collection class and any associated classes for Nodes, you must produce a textual file called README.txt. This must contain a statement about the authorship of the code you submit, including acknowledgements of all assistance you received (for example, conversations with friends, resources you found on the web, etc). The README must also contain a big-O running time for each method you implemented, and an answer to the following question:
“Fred Foolish claims that the worst case scalability of the getDescription method in the radix trie is O(log n) where n is the total length of all the genes in the collection. Fred says this because the depth of a tree is approximately the logarithm of the number of nodes, and you have at most one node for each character in each gene. Show that Fred is wrong in general, and explain the errors in his argument.”
________________________________________
Assessment
This assignment is due at the last moments of Friday September 25th; submission is via WebCT. It is worth 10% of the marks for the unit. Make sure you check that your assignment has been submitted! It it’s late it cannot get full marks!
The total mark will be based on these components:
,
