Arithmetic Computations and Memory Management Using a Binary Tree Encoding af Natural Numbers

Description:

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.

Creator(s): Haraburda, David
Creation Date: December 2011
Partner(s):
UNT Libraries
Collection(s):
UNT Theses and Dissertations
Usage:
Total Uses: 179
Past 30 days: 6
Yesterday: 0
Creator (Author):
Publisher Info:
Publisher Name: University of North Texas
Publisher Info: www.unt.edu
Place of Publication: Denton, Texas
Date(s):
  • Creation: December 2011
Description:

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.

Degree:
Discipline: Computer Science
Level: Master's
PublicationType: Master's Thesis
Language(s):
Subject(s):
Keyword(s): Binary trees | pairing functions | type isomorphisms | memory management
Contributor(s):
Partner:
UNT Libraries
Collection:
UNT Theses and Dissertations
Identifier:
  • ARK: ark:/67531/metadc103323
Resource Type: Thesis or Dissertation
Format: Text
Rights:
Access: Public
Holder: Haraburda, David
License: Copyright
Statement: Copyright is held by the author, unless otherwise noted. All rights Reserved.