Theory and Algorithms Commons^™

An Exploration Of Procedural Methods In Game Level Design, Hector Salinas

Computer Science and Computer Engineering Undergraduate Honors Theses

Video games offer players immersive experiences within intricately crafted worlds, and the integration of procedural methods in game level designs extends this potential by introducing dynamic, algorithmically generated content that could stand on par with handcrafted environments. This research highlights the potential to provide players with engaging experiences through procedural level generation, while potentially reducing development time for game developers.

Through a focused exploration on two-dimensional cave generation techniques, this paper aims to provide efficient solutions tailored to this specific environment. This exploration encompasses several procedural generation methods, including Midpoint Displacement, Random Walk, Cellular Automata, Perlin Worms, and Binary Space …

Developing Detection And Mapping Of Roads Within Various Forms Of Media Using Opencv, Jordan C. Lyle

Computer Science and Computer Engineering Undergraduate Honors Theses

OpenCV, and Computer Vision in general, has been a Computer Science topic that has interested me for a long time while completing my Bachelor’s degree at the University of Arkansas. As a result of this, I ended up choosing to utilize OpenCV in order to complete the task of detecting road-lines and mapping roads when given a wide variety of images. The purpose of my Honors research and this thesis is to detail the process of creating an algorithm to detect the road-lines such that the results are effective and instantaneous, as well as detail how Computer Vision can be …

Universal Computation Using Self-Assembling, Crisscross Dna Slats, Jackson S. Bullard

Computer Science and Computer Engineering Undergraduate Honors Theses

I first give a brief introduction to formal models of computation. I then present three different approaches for computation in the aTAM. I later detail generating systems of crisscross slats given an arbitrary algorithm encoded in the form of a Turing machine. Crisscross slats show potential due to their high levels of cooperativity, so it is hoped that implementations utilizing slats are more robust to various growth errors compared to the aTAM. Finally, my software converts arbitrary crisscross slat systems into various physical representations that assist in analyzing their potential to be realized in experiments.

Gauging The State-Of-The-Art For Foresight Weight Pruning On Neural Networks, Noah James

Computer Science and Computer Engineering Undergraduate Honors Theses

The state-of-the-art for pruning neural networks is ambiguous due to poor experimental practices in the field. Newly developed approaches rarely compare to each other, and when they do, their comparisons are lackluster or contain errors. In the interest of stabilizing the field of pruning, this paper initiates a dive into reproducing prominent pruning algorithms across several architectures and datasets. As a first step towards this goal, this paper shows results for foresight weight pruning across 6 baseline pruning strategies, 5 modern pruning strategies, random pruning, and one legacy method (Optimal Brain Damage). All strategies are evaluated on 3 different architectures …

Side-Channel Analysis On Post-Quantum Cryptography Algorithms, Tristen Teague

Computer Science and Computer Engineering Undergraduate Honors Theses

The advancements of quantum computers brings us closer to the threat of our current asymmetric cryptography algorithms being broken by Shor's Algorithm. NIST proposed a standardization effort in creating a new class of asymmetric cryptography named Post-Quantum Cryptography (PQC). These new algorithms will be resistant against both classical computers and sufficiently powerful quantum computers. Although the new algorithms seem mathematically secure, they can possibly be broken by a class of attacks known as side-channels attacks (SCA). Side-channel attacks involve exploiting the hardware that the algorithm runs on to figure out secret values that could break the security of the system. …

A Comparison Of Word Embedding Techniques For Similarity Analysis, Tyler Gerth

Computer Science and Computer Engineering Undergraduate Honors Theses

There have been a multitude of word embedding techniques developed that allow a computer to process natural language and compare the relationships between different words programmatically. In this paper, similarity analysis, or the testing of words for synonymic relations, is used to compare several of these techniques to see which performs the best. The techniques being compared all utilize the method of creating word vectors, reducing words down into a single vector of numerical values that denote how the word relates to other words that appear around it. In order to get a holistic comparison, multiple analyses were made, with …

Semi-Supervised Spatial-Temporal Feature Learning On Anomaly-Based Network Intrusion Detection, Huy Mai

Computer Science and Computer Engineering Undergraduate Honors Theses

Due to a rapid increase in network traffic, it is growing more imperative to have systems that detect attacks that are both known and unknown to networks. Anomaly-based detection methods utilize deep learning techniques, including semi-supervised learning, in order to effectively detect these attacks. Semi-supervision is advantageous as it doesn't fully depend on the labelling of network traffic data points, which may be a daunting task especially considering the amount of traffic data collected. Even though deep learning models such as the convolutional neural network have been integrated into a number of proposed network intrusion detection systems in recent years, …

Improving Bayesian Graph Convolutional Networks Using Markov Chain Monte Carlo Graph Sampling, Aneesh Komanduri

Computer Science and Computer Engineering Undergraduate Honors Theses

In the modern age of social media and networks, graph representations of real-world phenomena have become incredibly crucial. Often, we are interested in understanding how entities in a graph are interconnected. Graph Neural Networks (GNNs) have proven to be a very useful tool in a variety of graph learning tasks including node classification, link prediction, and edge classification. However, in most of these tasks, the graph data we are working with may be noisy and may contain spurious edges. That is, there is a lot of uncertainty associated with the underlying graph structure. Recent approaches to modeling uncertainty have been …

Trunctrimmer: A First Step Towards Automating Standard Bioinformatic Analysis, Z. Gunner Lawless, Dana Dittoe, Dale R. Thompson, Steven C. Ricke

Computer Science and Computer Engineering Undergraduate Honors Theses

Bioinformatic analysis is a time-consuming process for labs performing research on various microbiomes. Researchers use tools like Qiime2 to help standardize the bioinformatic analysis methods, but even large, extensible platforms like Qiime2 have drawbacks due to the attention required by researchers. In this project, we propose to automate additional standard lab bioinformatic procedures by eliminating the existing manual process of determining the trim and truncate locations for paired end 2 sequences. We introduce a new Qiime2 plugin called TruncTrimmer to automate the process that usually requires the researcher to make a decision on where to trim and truncate manually after …

On The Explanation And Implementation Of Three Open-Source Fully Homomorphic Encryption Libraries, Alycia Carey

Computer Science and Computer Engineering Undergraduate Honors Theses

While fully homomorphic encryption (FHE) is a fairly new realm of cryptography, it has shown to be a promising mode of information protection as it allows arbitrary computations on encrypted data. The development of a practical FHE scheme would enable the development of secure cloud computation over sensitive data, which is a much-needed technology in today's trend of outsourced computation and storage. The first FHE scheme was proposed by Craig Gentry in 2009, and although it was not a practical implementation, his scheme laid the groundwork for many schemes that exist today. One main focus in FHE research is the …

Applying Imitation And Reinforcement Learning To Sparse Reward Environments, Haven Brown

Computer Science and Computer Engineering Undergraduate Honors Theses

The focus of this project was to shorten the time it takes to train reinforcement learning agents to perform better than humans in a sparse reward environment. Finding a general purpose solution to this problem is essential to creating agents in the future capable of managing large systems or performing a series of tasks before receiving feedback. The goal of this project was to create a transition function between an imitation learning algorithm (also referred to as a behavioral cloning algorithm) and a reinforcement learning algorithm. The goal of this approach was to allow an agent to first learn to …

Dependency Mapping Software For Jira, Project Management Tool, Bentley Lager

Computer Science and Computer Engineering Undergraduate Honors Theses

Efficiently managing a software development project is extremely important in industry and is often overlooked by the software developers on a project. Pieces of development work are identified by developers and are then handed off to project managers, who are left to organize this information. Project managers must organize this to set expectations for the client, and ensure the project stays on track and on budget. The main block in this process are dependency chains between tasks. Dependency chains can cause a project to take much longer than anticipated or result in the under utilization of developers on a project. …

Tamscript - High Level Programming Interface For The Abstract Tile Assembly Model, Perry Mills

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper describes a programming interface, TAMScript, for use with the PyTAS simulator. The interface allows for the dynamic generation of tile types as the simulation progresses, with the goal of reducing complexity for researchers. This paper begins with an introduction to the PyTAS software and a description of the 3D model which it simulates. Next, the changes made to support a dynamic generation scheme are detailed, and some of the potential benefits of this scheme are outlined. Then several of the example scripts which have been written using the TAMScript interface are reviewed. Finally, the potential for future research …

Computational Complexity Of Determining The Rigidity Of Ftam Assemblies, Ian Perkins

Computer Science and Computer Engineering Undergraduate Honors Theses

In this paper, we discuss a tile-based self-assembly model called the Folding Tile Assembly Model (FTAM). We briefly define what makes the FTAM unique in its ability to have folding 2D tiles. We also discuss the difficulty of determining the computational complexity of certain FTAM properties despite it being simpler for less dynamic models. Specifically, we discuss the property of rigidity in FTAM assemblies by devising a simple definition of rigidity, so that it is easier to determine its complexity. We use a reduction between an assembly and a 3SAT instance along with a series of proofs to give a …

Music Feature Matching Using Computer Vision Algorithms, Mason Hollis

Computer Science and Computer Engineering Undergraduate Honors Theses

This paper seeks to establish the validity and potential benefits of using existing computer vision techniques on audio samples rather than traditional images in order to consistently and accurately identify a song of origin from a short audio clip of potentially noisy sound. To do this, the audio sample is first converted to a spectrogram image, which is used to generate SURF features. These features are compared against a database of features, which have been previously generated in a similar fashion, in order to find the best match. This algorithm has been implemented in a system that can run as …

Ant Colony Optimization For Continuous Spaces, Rachel Findley

Computer Science and Computer Engineering Undergraduate Honors Theses

Ant Colony Optimization (ACO) is an optimization algorithm designed to find semi-optimal solutions to Combinatorial Optimization Problems. The challenge of modifying this algorithm to effectively optimize over a continuous domain is one that has been tackled by several researchers. In this paper, ACO has been modified to use several variations of the algorithm for continuous spaces. An aspect of ACO which is crucial to its success when optimizing over a continuous space is choosing the appropriate object (solution component) out of an infinite set to add to the ant's path. This step is highly important in shaping good solutions. Important …

Wi-Fi Sensing Algorithms Utilizing Zigbee Rf Reciever For Use In Emergency Communications Mesh, Alexander Nelson

Computer Science and Computer Engineering Undergraduate Honors Theses

This thesis introduces the idea of a low-power Wi-Fi sensing wake-up controller for an emergency communications mesh network, progressively developing a prototype system which could be used in a live environment. Wireless network protocols are reviewed, as well as a limited view of cluster analysis, in order to introduce relevant concepts crucial to understanding this thesis. Algorithms for system implementation are developed, and pseudocode, designed to be configurable and platform independent, is given for each. Design goals for the system are identified with potential approaches are defined in order to optimize for each. An example hardware configuration is given, in …

Service Oriented Transitive Closure Solution, Jonathan Baran

Computer Science and Computer Engineering Undergraduate Honors Theses

The goal of this project is a service based solution that utilizes parallel and distributed processing algorithms to solve the transitive closure problem for a large dataset. A dataset may be view conceptually as a table in a database, with a physical structure representing a file containing a sequence of records and fields. Two records are said to be transitively related if and only if they are directly related due to sharing of one or more specific fields, or a sequence may be made from one record to the other under the condition that all intermediate entries are related the …

Visualization Of An Approach To Data Clustering, Marisabel Guevara

Computer Science and Computer Engineering Undergraduate Honors Theses

Using visualization and clustering goals as guidelines, this thesis explores a graphic implementation of a data clustering technique that repositions vertices by applying physical laws of charges and springs to the components of the graph. The resulting visualizations are evidence of the success of the approach as well as of the data sets that lend themselves to a clustering routine. Due to the visual product of the implementation, the algorithm is most useful as an aid in understanding the grouping pattern of a data set. Either for a rapid analysis or to assist in presentation, the visual result of the …