University of Victoria (Canada)
Algorithms and combinatorics of maximal compact codes
Abstract
dc:description.abstractThe implementation of two different algorithms for generating compact codes of some size N are presented. An analysis of both algorithms is given. in an attempt to prove whether or not the algorithms run in constant amortized time. Meta-Fibonacci sequences are also investigated in this paper. Using a particular numbering on k-ary trees, we find that a group of meta-Fibonacci sequences count the number of nodes at the bottom level of these k-ary trees. These meta-Fibonacci sequences are also related to compact codes. Finally, generating functions are proved for the meta-Fibonacci sequences discussed.
Degree
thesis:*- Level thesis:degree_level
- Master of Science M.Sc.
- Department thesis:degree_department
- Department of Computer Science
- Year dc:date.issued
- 2010
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Deugau, Christopher Jordan
- Advisors dc:contributor.supervisor
-
- Ruskey, Frank
- Roelants van Baronaigien, Dominique
Subjects
dc:subject × 3Rights
dc:rights- Statement dc:rights
-
- Available to the World Wide Web
- Language dc:language.iso
- en, English
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- http://hdl.handle.net/1828/2101