Project

Information about the programming project will be posted here.

All submissions will be done through the Department's submit server. Also, remember that your submission must run correctly on the Grace cluster.

Part 0:

Your project will involve inputting/outputting XML documents. For background on XML and our utilities to help you processing XML documents, please see the handout on Processing XML Files for the Programming Project from the class Handouts page.

Here is a document on How to Get Started on MeeshQuest. We have also provided is a zip file with a Skeleton Java Project. (The Getting-Started document explains how to import it into Eclipse.)

Part-0 specifications can be found on the class handouts page.

Part 1:

The same XML framework applies to this part of the assignment. Again, see the document Processing XML Files for the Programming Project from the class Handouts page.

We also have an updated zip file with a Part-1 Skeleton Java Project. It contains both an updated XML schema-definition file, "part1in.xsd", and an updated ".submit" file.

Part-1 specifications can be found on the class Handouts page. The SG Tree data structure is described in greater detail in Lecture 12 (just after Scapegoat trees) from the class Lectures page.

In order to guarantee that everyone generates the same tree, we need to agree on some conventions. (These are not necessarily optimal choices, but we found them to be relatively easy to implement.)

• In the binary search tree, when deleting a node with two children, the replacement node is chosen to be the inorder successor of the deleted node.
• In the SG tree, use integer arithmetic to avoid issues with float-point round-off errors. In particular, a node u satisfies the scapegoat condition if 2*size(u) < 3*size(u.child).
• In the SG tree, if there are multiple nodes along the search path that satisfy the scapegoat, the node that is closest to the root is rebuilt.
• In the SG tree, when inserting a new external node, the splitter in the associated internal node is the key value in its left child.
• In the SG tree, when rebuilding a subtree, if the number k of external nodes is even, split them evenly among the left and right subtrees. If k is odd, the left subtree gets ⌈k/2⌉ external nodes and the right subtree gets the remaining ⌊k/2⌋ external nodes.

Part 2:

We have an updated zip file with a Part-2 Skeleton Java Project. It contains both an updated XML schema-definition file, "part2in.xsd", and an updated ".submit" file.

The Part-2 specifications can be found on the class Handouts page. The SG kd-Tree data structure is described in greater detail in The SG kd-Tree Data Structure.

Here is a link to our source code for Part 1: MeeshQuest - Part 1 - Canonical. You are welcome to use any part(s) of this that you like (without the need to attribute it).

Disclaimer: Of course, as with all free software, "buyer beware". While we believe that this code and its comments are correct, we are only human, and errors are to be expected. Ultimately, you are responsible for the correctness of your code, even if you copied it from us. If you do spot any errors or something appears to be wrong, please notify me.