CSCI2110 Assignment 4

The purpose of this assignment is to get you to create and use the tree data structure and practice a bit more recursion to further improve your programming skills.

As discussed in class and the first tutorial, for each problem you will be provided with a description of the problem and a JUnit test class to test your code. A similar JUnit test class will be used to evaluate your code. You can use Eclipse or other IDEs to run the JUnit test class to test your code.

Your code must compile. If it does not compile, you will receive a 0 on the assignment.

Background: Phylogenetic Trees

A phylogenetic (or evolutionary) tree represents the evolution of species over time. Each node in the tree corresponds to a species and parent-child relationship represents an evolution from one species to another. Scientists build such trees based on genetic and fossil data, indicating that one species evolved from another. In particular, given a sequence of statements of the form X evolved from Y, a computer can be used to build a phylogenetic tree.

Problem: Generating a Phylogenetic Tree

Given a series of statements of the form X evolved from Y, where X and Y denote species, construct a corresponding phylogenetic tree. The tree should then be displayed in a manner similar to the output in Assignment 3. For example, given the input

 leeches evolved from flatworms cecil evolved from snakes monkeys evolved from one-celled forms lochness monster evolved from snakes snakes evolved from one-celled forms flatworms evolved from one-celled forms fung evolved from sponges 

 sponges evolved from one-celled forms end 

Figure 2: Sample phylogenetic data. the result phylogenetic tree would look like:

 one-celled forms |-flatworms | |-leeches |-monkeys |-snakes 

 | |-cecil | |-lochness monster |-sponges | |-fung 

Figure 3: A representation a phylogenetic tree generated from data in Figure 2

Your task is to create a program that generates phylogenetic tree based on phylogenetic data and output a representation of the tree.

Write a program called EvoTree.java that reads in phylogenetic data from the console (System.int) and outputs the corresponding phylogenetic tree. Your EvoTree class must implement the provided Tester interface and also contain the main() method where your program starts running. This is because your program will be tested via this interface. The interface contains a single method:

 public ArrayList compute( Scanner input ); 

This method must perform the required computation.

Input

The compute() method takes a Scanner object, which contains one or more lines. Each line, except the last one, is of the form

Species A evolved from Species B

where Species A and Species B are names of specific species. The species names can comprise one or more words, but will never contain the words evolved from. The last line of input is simply the word end. See Figure 2 for an example.

Hint: Use the nextLine() method of the Scanner object to read one line of input at a time, and then parse the line. See the solution for Assignment 1 for how to parse input one line at a time.

Semantics

Each line of the form Species A evolved from Species B represents a direct evolution from species B to species A. The input lines are in arbitrary order.

All data will generate a single tree. That is, there will only be one species that is not evolved from some other species (the root of the tree).

Each species (except the root) will be evolved from exactly one species, but multiple species may evolve from a single species, as in the example. (This is a simplification.)

Output

The method compute( Scanner input ) should return an ArrayList of Strings denoting the phylogenetic tree. Each species should be a separate String. All children of a node in the tree are to be displayed in lexically sorted order. Each species should be prefixed with d 1 |- followed by |- followed by the species name where d is the depth of the node and denotes a space. This is exemplified in Figure 3.

Example

sample input	sample output
leeches evolved from flatworms	one-celled forms
cecil evelved from snakes	| -flatworks
monkeys evolved from one-celled forms	| |-leeches
lockness monster evolved from snakes	| -monkeys
snakes evolved from one-celled forms	| -snakes
flatworms evloved from one-celled forms	| | -cecil
fung evolved from sponges	| | -lochness monster
sponges evolved from one-celled forms	| -sponges
end	| |-fung

Hints and Suggestions

The sample solution uses a 2-pass algorithm. The first pass builds the phylogenetic tree. This can be done iteratively. The second pass recursively outputs the tree. This pass is very similar to the one in the previous assignment.

There is not a lot of code to write. The sample solution is under 100 lines of code.

Your code must compile. If it does not compile, you will receive a 0 on the assignment.

Your code must be well commented and indented. Please see the Assignments section

for this course on Brightspace for Code Style Guidelines.

You may assume that all input will be correct.

Be sure to test your programs using the provided JUnit test class.

Grading

The assignment will be graded based on three criteria:

- Functionality Does it work according to specifications?. This is determined in an auto-mated fashion by running your program on a number of inputs and ensuring that the outputs match the expected outputs. The score is determined based on the number of tests that your program passes. So, if your program passes t tests, you will receive t/T that proportion of the marks.

- Quality of Solution Is it a good solution? This considers whether the solution is correct, efficient, covers boundary conditions, does not have any obvious bugs, etc. This is determined by visual inspection of the code. Initially full marks are given to each solution and marks are deducted based on faults found in the solution.

- Code Clarity Is it well written? This considers whether the solution is properly format- ted, well documented, and follows coding style guidelines.

If your program does not compile, it is considered non-functional and of extremely poor quality, meaning you will receive 0 for the solution.

What to Hand In

Submit the source files for your program in a zip file (.zip). You should have at least one source file: EvoTree.java. If you are using Eclipse, we recommend that you submit the entire project bundle. Submission is to be done via Brightspace. Your code must compile. If it does not compile, you will receive a 0 on the assignment.