Two applications of a binary tree data type based on a simple pairing function (a bijection between natural numbers and pairs of natural numbers) are explored. First, the tree is used to encode natural numbers, and algorithms that perform basic arithmetic computations are presented along with formal proofs of their correctness. Second, using this "canonical" representation as a base type, algorithms for encoding and decoding additional isomorphic data types of other mathematical constructs (sets, sequences, etc.) are also developed. An experimental application to a memory management system is constructed and explored using these isomorphic types. A practical analysis of this system's runtime complexity and space savings are provided, along with a proof of concept framework for both applications of the binary tree type, in the Java programming language.
| Identifer | oai:union.ndltd.org:unt.edu/info:ark/67531/metadc103323 |
| Date | 12 1900 |
| Creators | Haraburda, David |
| Contributors | Tarau, Paul, Mihalcea, Rada, 1974-, Buckles, Bill |
| Publisher | University of North Texas |
| Source Sets | University of North Texas |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
| Format | Text |
| Rights | Public, Haraburda, David, Copyright, Copyright is held by the author, unless otherwise noted. All rights Reserved. |
Page generated in 0.0868 seconds