Gene Collection


This assignment emphasizes the details of programming a data structure, with careful

attention to making sure that each operation keeps the integrity of the structure. It should also

provided practice in recursion. In addition, you will demonstrate your ability to analyze the

run-time costs of your code. This is an individual assignment: each student must work

independently, and any assistance must be acknowledged in the README file.


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

[url removed, login to view] and the classes in [url removed, login to view] and [url removed, login to view], such as String).

The class you write must 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 [url removed, login to view] file must be in a

directory called GeneCollection.

To clients, this class should appear as an implementation of the interface GCInterface. The

interface is at Page 2 of this document.

Internally, the collection class must be structured as a radix search trie. The detail explanation

of the radix search trie is included in the Appendix Section at the end of this document.

As well as the collection class and any associated classes for Nodes, you must produce a

textual file called README. 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."


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);


Taidot: Java

Näytä lisää: work collection, which java collection to use, web programming course, uses of tree data structure, uses of data structure, use of tree data structure, use of data structure in programming, use of collection in java, use case simple example, trie tree java, trie tree implementation, trie tree, trie structure, trie search, trie on, trie it, trie implementation in c, trie implementation, trie example, trie data structure java, trie data structure in c, trie data structure implementation in c, trie data structure, trie data, trie code

Tietoa työnantajasta:
( 5 arvostelua ) Providence, United States

Projektin tunnus: #424562