University of North Texas
Arithmetic Computations and Memory Management Using a Binary Tree Encoding af Natural Numbers
Abstract
dc:descriptionTwo 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.
Degree
thesis:*- Grantor dc:publisher
- University of North Texas
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Haraburda, David
- Contributors dc:contributor
-
- Tarau, Paul
- Mihalcea, Rada, 1974-
- Buckles, Bill
Subjects
dc:subject × 5Rights
dc:rights- Statement dc:rights
-
- Public
- Haraburda, David
- Copyright
- Copyright is held by the author, unless otherwise noted. All rights Reserved.
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
oclc: 817916588
https://digital.library.unt.edu/ark:/67531/metadc103323/
ark: ark:/67531/metadc103323