Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Mathematics (4)
- Algebra (2)
- Artificial Intelligence and Robotics (2)
- Arts and Humanities (2)
- Geometry and Topology (2)
-
- Other Computer Sciences (2)
- Programming Languages and Compilers (2)
- Social and Behavioral Sciences (2)
- Software Engineering (2)
- Applied Mathematics (1)
- Art and Design (1)
- Bioinformatics (1)
- Composition (1)
- Computational Linguistics (1)
- Databases and Information Systems (1)
- Discrete Mathematics and Combinatorics (1)
- Dynamical Systems (1)
- Economic Theory (1)
- Economics (1)
- Education (1)
- Graphics and Human Computer Interfaces (1)
- Higher Education (1)
- Life Sciences (1)
- Linguistics (1)
- Music (1)
- Music Theory (1)
- Number Theory (1)
- Institution
- Keyword
-
- Algorithms (3)
- Artificial Neural Networks (2)
- Accuracy (1)
- Algorithm (1)
- B+ tree (1)
-
- BCH Codes (1)
- Bike routes (1)
- Biking (1)
- Binomial Coefficients (1)
- Bioinformatics (1)
- Chord (1)
- Cloud computing (1)
- College room allotment (1)
- Complexity (1)
- Computer science (1)
- Computer software (1)
- Computing (1)
- Cooper's Philosophy (1)
- Cyclic Codes (1)
- Cycling (1)
- De novo design (1)
- Decision Trees (1)
- Dijkstra (1)
- Distributed hash algorithms (1)
- End (1)
- Fault tolerance (1)
- Feature Selection (1)
- Game Theory (1)
- General Error Locator Polynomials (1)
- Genetic Algorithm (1)
- Publication Year
- Publication Type
Articles 1 - 20 of 20
Full-Text Articles in Theory and Algorithms
Exploration Of Feature Selection Techniques In Machine Learning Models On Hptlc Images For Rule Extraction, Bozidar-Brannan Kovachev
Exploration Of Feature Selection Techniques In Machine Learning Models On Hptlc Images For Rule Extraction, Bozidar-Brannan Kovachev
Honors Theses
Research related to Biology often utilizes machine learning models that are ultimately uninterpretable by the researcher. It would be helpful if researchers could leverage the same computing power but instead gain specific insight into decision-making to gain a deeper understanding of their domain knowledge. This paper seeks to select features and derive rules from a machine learning classification problem in biochemistry. The specific point of interest is five species of Glycyrrhiza, or Licorice, and the ability to classify them using High-Performance Thin Layer Chromatography (HPTLC) images. These images were taken using HPTLC methods under varying conditions to provide eight …
Improving Adjacency List Storage Methods For Polypeptide Similarity Analysis, Arianna Swensen
Improving Adjacency List Storage Methods For Polypeptide Similarity Analysis, Arianna Swensen
Honors Theses
Protein design is a complex biomolecular and computational problem. Working on increasingly large protein folding problems requires an improvement in current analysis methods available. This work first discusses various methods of protein design, including de novo protein design, which is the primary focus of this thesis. Then, a new approach utilizing a B+ tree to effectively store and query a graph of keys and vertices is proposed in order to store the number of times two polypeptides are considered to be similar. This approach is found to have a reduction in time complexity from current mapping methods and thus provides …
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 …
Surface Reconstruction Library, Jhye Tim Chi
Surface Reconstruction Library, Jhye Tim Chi
Honors Theses
The project aims to convert an arbitrary point cloud into a triangular mesh. Point clouds are a list of 3d points that model the topology of an object. Point clouds can have various issues, such as missing or noisy data. For the scope, we had no control over point cloud generation. We were also unable to deal with underlying registration or alignment problems. Triangular meshes are a list of triangles that have 3d vertices. This aggregate list of triangles defines the reconstructed surface. Our project implementation is based on Alexander Hornung and Leif Kobbelt’s method for surface reconstruction using the …
Generative Art, Caleb Harmon
Generative Art, Caleb Harmon
Honors Theses
Generative Art is systems that produce complex structures and visuals through computation.
Dijkstra’S Pathfinder, Taylor F. Malamut
Dijkstra’S Pathfinder, Taylor F. Malamut
Honors Theses
Dijkstra’s algorithm has been widely studied and applied since it was first published in 1959. This research shows that Dijkstra’s algorithm can be used to find the shortest path between two stations on the Washington D.C. Metro. After exploring different types of research and applying Dijkstra’s algorithm, it was found that the algorithm will always yield the shortest path, even if visually a shorter path was initially expected.
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 …
Iterated Local Search Algorithms For Bike Route Generation, Aidan Pieper
Iterated Local Search Algorithms For Bike Route Generation, Aidan Pieper
Honors Theses
Planning routes for recreational cyclists is challenging because they prefer longer more scenic routes, not the shortest one. This problem can be modeled as an instance of the Arc Orienteering Problem (AOP), a known NP-Hard optimization problem. Because no known algorithms exist to solve this optimization problem efficiently, we solve the AOP using heuristic algorithms which trade accuracy for speed. We implement and evaluate two different Iterated Local Search (ILS) heuristic algorithms using an open source routing engine called GraphHopper and the OpenStreetMap data set. We propose ILS variants which our experimental results show can produce better routes at the …
Modular Scheduling System For Westside School District, Tyler Bienhoff
Modular Scheduling System For Westside School District, Tyler Bienhoff
Honors Theses
Westside School district offers a modular scheduling system for their high school that is more similar to a college schedule than the typical high school system. Due to the complexity of their master schedule each semester, there are no commercially available products that can assist in creating a schedule. Hence, this thesis discusses a scheduling algorithm and management system that was built specifically for Westside High School with the potential to be expanded for use by other interested schools. The first part of the paper is focused on gathering input from students and faculty for which courses and how many …
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. …
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 …
Effective Ann Topologies For Use As Genotypes For Evaluating Design And Fabrication, John R. Peterson
Effective Ann Topologies For Use As Genotypes For Evaluating Design And Fabrication, John R. Peterson
Honors Theses
There is promise in the field of Evolutionary Design for systems that evolve not only what to manufacture but also how to manufacture it. EvoFab is a system that uses Genetic Algorithms to evolve Artificial Neural Networks (ANNs) which control a modified 3d-printer with the goal of automating some level of invention. ANNs are an obvious choice for use with a system like this as they are canonically evolvable encodings, and have been successfully used as evolved control systems in Evolutionary Robotics. However, there is little known about how the structural characteristics of an ANN affect the shapes that can …
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.
Procedural Generation: An Algorithmic Analysis Of Video Game Design And Level Creation, Logan Bond
Procedural Generation: An Algorithmic Analysis Of Video Game Design And Level Creation, Logan Bond
Honors Theses
Procedural generation is a method for generating mass quantities of data algorithmically rather than manually. One perfect example of this is the recently famous No Man’s Sky, a video game where the entire marketing scheme was structured around its procedurally generated universe. The game’s trailer and advertisements promised its players 18,446,744,073,709,551,616 unique planets[1], all of which were procedurally generated. In other words, the developers did not create exclusive profiles for every single planet, but instead programmed the game in such a way that the planets were built from the code. This method of content creation is the …
Blending Two Automatic Playlist Generation Algorithms, James Curbow
Blending Two Automatic Playlist Generation Algorithms, James Curbow
Honors Theses
We blend two existing automatic playlist generation algorithms. One algorithm is built to smoothly transition between a start song and an end song (Start-End). The other infers song similarity based on adjacent occurrences in expertly authored streams (EAS). First, we seek to establish the effectiveness of the Start-End algorithm using the EAS algorithm to determine song similarity, then we propose two playlist generation algorithms of our own: the Unbiased Random Walk (URW) and the Biased Random Walk (BRW). Like the Start-End algorithm, both the URW algorithm and BRW algorithm transition between a start song and an end song; however, issues …
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 …
Analysis Of The Peerrank Method For Peer Grading, Joshua Kline
Analysis Of The Peerrank Method For Peer Grading, Joshua Kline
Honors Theses
Peer grading can have many benefits in education, including a reduction in the time instructors spend grading and an opportunity for students to learn through their analysis of others work. However, when not handled properly, peer grading can be unreliable and may result in grades that are vastly different from those which a student truly deserves. Therefore, any peer grading system used in a classroom must consider the potential for graders to generate inaccurate grades. One such system is the PeerRank rule proposed by Toby Walsh, which uses an iterative, linear algebra based process reminiscent of the Google PageRank algorithm …
Natural Language Processing For Foreign Language Learning, Jacob Kausler
Natural Language Processing For Foreign Language Learning, Jacob Kausler
Honors Theses
This research presents novel algorithms which generate sentences in a natural language, using natural language generation techniques. The purpose of the algorithms is to benefit foreign language learning. As far as we can tell, ours is the first such research being done in the field. In creating the algorithms, we also developed a piece of software to showcase the work and allow testing by users. The main algorithm begins by generating sentence models by using one of two methods, namely modeled sentence generation and semantic sentence generation. Each of these have benefits and drawbacks, which the user must take into …
An Analysis Of Peer-To-Peer Distributed Hash Algorithms In Improving Fault Tolerance In The Hadoop Running Environment, Benjamin R. Knaus
An Analysis Of Peer-To-Peer Distributed Hash Algorithms In Improving Fault Tolerance In The Hadoop Running Environment, Benjamin R. Knaus
Honors Theses
Cloud computing is a “new frontier” in the world of computing. One of the cloud architectures widely used is the Hadoop running environment. Hadoop consists of many parts—including MapReduce, TaskTrackers, and JobTrackers. Right now, there is no fault-tolerance for JobTrackers in Hadoop. This paper analyzes four different distributed hash algorithms (Pastry, Tapestry, CAN, and Chord) that could be implemented inside Hadoop to improve JobTracker fault-tolerance. We recommend Chord as the best suited for integration and improvement of Hadoop.
Utilization Of Probabilistic Models In Short Read Assembly From Second-Generation Sequencing, Matthew W. Segar
Utilization Of Probabilistic Models In Short Read Assembly From Second-Generation Sequencing, Matthew W. Segar
Honors Theses
With the advent of cheaper and faster DNA sequencing technologies, assembly methods have greatly changed. Instead of outputting reads that are thousands of base pairs long, new sequencers parallelize the task by producing read lengths between 35 and 400 base pairs. Reconstructing an organism’s genome from these millions of reads is a computationally expensive task. Our algorithm solves this problem by organizing and indexing the reads using n-grams, which are short, fixed-length DNA sequences of length n. These n-grams are used to efficiently locate putative read joins, thereby eliminating the need to perform an exhaustive search over all possible read …