Open Access. Powered by Scholars. Published by Universities.®
- Keyword
- Publication Type
Articles 1 - 4 of 4
Full-Text Articles in Theory and Algorithms
Decoding Cyclic Codes Via Gröbner Bases, Eduardo Sosa
Decoding Cyclic Codes Via Gröbner Bases, Eduardo Sosa
Honors Theses
In this paper, we analyze the decoding of cyclic codes. First, we introduce linear and cyclic codes, standard decoding processes, and some standard theorems in coding theory. Then, we will introduce Gr¨obner Bases, and describe their connection to the decoding of cyclic codes. Finally, we go in-depth into how we decode cyclic codes using the key equation, and how a breakthrough by A. Brinton Cooper on decoding BCH codes using Gr¨obner Bases gave rise to the search for a polynomial-time algorithm that could someday decode any cyclic code. We discuss the different approaches taken toward developing such an algorithm and …
Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke
Pascal's Triangle Modulo N And Its Applications To Efficient Computation Of Binomial Coefficients, Zachary Warneke
Honors Theses
In this thesis, Pascal's Triangle modulo n will be explored for n prime and n a prime power. Using the results from the case when n is prime, a novel proof of Lucas' Theorem is given. Additionally, using both the results from the exploration of Pascal's Triangle here, as well as previous results, an efficient algorithm for computation of binomial coefficients modulo n (a choose b mod n) is described, and its time complexity is analyzed and compared to naive methods. In particular, the efficient algorithm runs in O(n log(a)) time (as opposed to …
Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell
Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell
Honors Theses
Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …
Normal Surfaces And 3-Manifold Algorithms, Josh D. Hews
Normal Surfaces And 3-Manifold Algorithms, Josh D. Hews
Honors Theses
This survey will develop the theory of normal surfaces as they apply to the S3 recognition algorithm. Sections 2 and 3 provide necessary background on manifold theory. Section 4 presents the theory of normal surfaces in triangulations of 3-manifolds. Section 6 discusses issues related to implementing algorithms based on normal surfaces, as well as an overview of the Regina, a program that implements many 3-manifold algorithms. Finally section 7 presents the proof of the 3-sphere recognition algorithm and discusses how Regina implements the algorithm.