After suffering heavy casualties when a Sametizing center on Temas-ton3exploded just before the portal to Temas-Ty-Went opened, the Sametists developed bioMechs to make planets habitable for the Sametists without undue loss of life. Thus relieved of any dangerous job assignments, the Sametists returned to pondering the implications of their closure assumptions upon the dimensions and growth rates of their spatial data structures without fearing for their lives.
At any rate, the Sametists employ a process called Hanan-o-Forming, that uses families of biomachines, from nanomachines capable of modifying a genotype, up to MegaBeasts, who dig, reinforce, and excrete the massive lined tunnels that honeycomb each planet infested with Sametists, and provide various service and maintenance functions throughout every level of the habitat. Once the planet has been Hanan-o-Formed, it can be settled and yet another planet of indefatigable Sametists can be trained. Planet Temas-Too is the latest planet to have been infested, and, to educate the teeming fledgling sametists, a 2nd university system, Hanan University Too (HUT).
This project will guide you in erecting Hanan University Too (HUT) using the Hanan-o-Forming Process (HOP). The HOP devours the natural resources of the planet and extrudes the standardized environment that provides the appropriate living and learning atmosphere for Sametists. Note that the HOP lays out and develops the intricate cell_ - _web structures for which MegaBeast-based habitats are renowned, while minimizing the costs associated with the HOP. Legend has it that they follow the ancient rules of Pascal, but no one has been able to verify that suspicion.
The atmosphere of Temas-Too is too toxic for the Sametist's nictating membraneous respiratory structures, which provide the host cells for many of BioMech's Hanan-o-bots, or h'obots as they are called. So, a special environment must be established before the MegaBeasts can be unleashed beneath the planet's surface. Once the MegaBeast-ready sites have been completed, the MegaBeasts and their companion E-bots are unleashed to construct learning sites and the supporting interconnection network that will make up HUT.
Motivation:
The ulterior motive of this project is to force you to explore the process of combining data abstractions based on mixing and matching specific properties or attributes of the real-life or made-up processes to produce composite data-structures that facilitate providing the required service to the customer. That is, what tradeoffs are necessary to satisfy potentially conflicting constraints of time, cost, and space? Note that non-functional requirements4such as the need for real-time performance, demands that the code satisfying the process constraints be efficient, as well as correct, because failure is both dangerous and costly. So, additional constraints on the problem may become necessary as we begin to understand the issues associated with developing a HOP HUT. Furthermore, the lessons learned in one portion of the project will definitely help you in later parts.
Project Overview
The assignment is to be done in four (4) segments, with the parts (and due dates) specified below. A command interpreter, to be used in all parts of the project, must be constructed to facilitate design and testing of your project. The command decoder will be modified throughout the course; so, you might find yourself upgrading this more often than you think :-).
Part 1 asks you to implement a data dictionary (DD), ordered by cell name, using a Binary Search Tree (BST). The DD will contain the information gathered regarding potential cell locations, organized by name or CID (cell identifier). Then, you will implement a PR quadtree to represent the spatial relationships among the cells chosen for implantation of MegaBeasts thoughout the planet. The long term goal is to expand this PR quadtree into a map of all existing knowledge sites and critical inter-site pathways.
In part 2, you will implement the DD using a B+ tree, and will use an adjacency list in congress with the PR quadtree from part 1 to plan and track the generation the biometallic web that permeates planet's crust and supports the Mega-beast processes. This web will form the foundation of the paths to be traversed by Sametists as they move from knowledge site to knowledge site, picking up the diverse concepts that are the mark of the true Sametist. The PR quadtree-based map from part 1 will be expanded to include the inter-cite web, or E-bot net, and to detect points of intersection within the E-bot net. You will also develop the ability to draw the HUT map on an X-based machine so as to support debugging of the updated map structure in part 3.
In part 3, deletion will be added to the B+-tree, and the PR quadtree-based map will be expanded to become a PM1 quadtree which will represent spatial relationships among cells and will capture the planned E-bot net necessary to link the knowledge cites and to indicate directional choices along the E-bot net. In part 4, deletion in the PM1 quadtree is introduced, to further capture points, lines, and planes appropriate for the HUT in a single structure, and to allow planning of the final HUT campus using heuristic algorithms to deal with complex mapping constraints. Each part of the project will also include several applications essential to making this venture profitable.
In each part, points are allotted for program documentation, conformance to requirements and efficiency. Furthermore, a separate BNF specification for the output will be posted for each part, along with sample input and output files. Note that student assistance in generating test data files is always appreciated.
Make sure that you follow all instructions specified in this document, the webpage, the newsgroup and in the class. If you don't implement an instruction, make sure you follow the directions and fail passively, because we won't grade past a core dump. And, you only get one complimentary core dump per semester.
The most current version of this document and the corresponding bnf will be posted on the webpage at all times. We will not be able to incorporate ALL modifications or clarifications to the specifications. Thus, the project specification consists of the most recent version of the document on the webpage, plus any modifications posted after the last update of the main version of the specification. So, keep track of postings by the ta or by me that might improve your understanding of the project. Remember, always make sure that your project complies with the most recent postings before submitting. In general, we will freeze the specification at least 1 week before the project due date.