Open Access. Powered by Scholars. Published by Universities.®
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 …
Mechanism Design, Matching Theory And The Stable Roommates Problem, Yashaswi Mohanty
Mechanism Design, Matching Theory And The Stable Roommates Problem, Yashaswi Mohanty
Honors Theses
This thesis consists of two independent albeit related chapters. The first chapter introduces concepts from mechanism design and matching theory, and discusses potential applications of this theory, particularly in relation to dorm allocations in colleges. The second chapter investigates a subset of the dorm allocation problem, namely that of matching roommates. In particular, the paper looks at the probability of solvability of random instances of the stable roommates game under the condition that preferences are not completely random and exogenous but endogenously determined through a dependence on room choice. These probabilities are estimated using Monte-Carlo simulations and then compared with …
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.
Using Genetic Algorithms To Evolve Artificial Neural Networks, William T. Kearney
Using Genetic Algorithms To Evolve Artificial Neural Networks, William T. Kearney
Honors Theses
This paper demonstrates that neuroevolution is an effective method to determine an optimal neural network topology. I provide an overview of the NeuroEvolution of Augmenting Topologies (NEAT) algorithm, and describe how unique characteristics of this algorithm solve various problem inherent to neuroevolution (namely the competing conventions problem and the challenges associated with protecting topological innovation). Parallelization is shown to greatly speed up efficiency, further reinforcing neuroevolution as a potential alternative to traditional backpropagation. I also demonstrate that appropriate parameter selection is critical in order to efficiently converge to an optimal topology. Lastly, I produce an example solution to a medical …