CSE 2010, HW3

 Submit Server: class = cse2010, assignment = hw3SxGroupHelp
x is 14, 23, or j—1 and 4 are merged into 14, j is for java.
Many entities, such as electronics and biological organisms, can be organized in a taxonmy. How would you design a
system that stores the taxonomy and allow queries on the taxonmy?
The goal of HW3 is to build a tree from categories of entities and answer queries on the tree. Your submission has a tree
with a linked structure of tree nodes and supports (at least) the following operations:
• addChild(parentNode, childNode) // to maintain alphabetical/lexicographical order of the children
• getChildren(node)
• getParent(node)
For each node, you may not assume it has a fixed or maximum number of children.
Input: Input is from the command-line arguments for hw3.c (HW3.java) in this order:
1. filename of the data—the first line has the top category, followed by its sub-categories; each of the following lines has
a category, followed by its sub-categories.
2. filename of queries, each line has one of the following queries:
• DirectSupercategory category
• DirectSubcategories category
• AllSupercategories category
• AllSubcategories category
• NumberOfAllSupercategories category
• NumberOfAllSubcategories category
• IsSupercategory category supercategory
• IsSubcategory category subcategory
• ClosestCommonSupercategory category1 category2
You may assume categories in the queries exist in the data. Sample input files are on the course website.
Output: Output goes to the standard output (screen), each line has an answer with the corresponding query:
• DirectSupercategory category supercategory
• DirectSubcategories category subcategory1 subcategory2 ...
• AllSupercategories category supercategory1 supercategory2 ...
• AllSubcategories category subcategory1 subcategory2 ...
• NumberOfAllSupercategories category count
• NumberOfAllSubcategories category count
• IsSupercategory category supercategory yes/no
• IsSubcategory category subcategory yes/no
• ClosestCommonSupercategory category1 category2 closestCommonSupercategory
DirectSubcategories (if any) are in the alphabetical/lexicographical order. AllSubcategories (if any) are in “pre-order.”
AllSupercategories (if any) are in the order of supercategory, grand-supercategory, ... IsSupercategory/IsSubcategory refers
to any supercategory/subcategory. ClosestCommonSupercategory (if any) is the deepest supercategory of both categories.
Sample output is on the course website.
Submission: Submit hw3.c (HW3.java) that has the main method and other program files. Submissions for Indvidual and
GroupHelp have the same guidelines as HW1.
Note the late penalty on the syllabus if you submit after the due date and time as specified at the top of the assignment.
1