Physical Sciences and Mathematics Commons^™

Foundations Of Memory Capacity In Models Of Neural Cognition, Chandradeep Chowdhury

Master's Theses

A central problem in neuroscience is to understand how memories are formed as a result of the activities of neurons. Valiant’s neuroidal model attempted to address this question by modeling the brain as a random graph and memories as subgraphs within that graph. However the question of memory capacity within that model has not been explored: how many memories can the brain hold? Valiant introduced the concept of interference between memories as the defining factor for capacity; excessive interference signals the model has reached capacity. Since then, exploration of capacity has been limited, but recent investigations have delved into the …

A Novel Approach To Extending Music Using Latent Diffusion, Keon Roohparvar, Franz J. Kurfess

Master's Theses

Using deep learning to synthetically generate music is a research domain that has gained more attention from the public in the past few years. A subproblem of music generation is music extension, or the task of taking existing music and extending it. This work proposes the Continuer Pipeline, a novel technique that uses deep learning to take music and extend it in 5 second increments. It does this by treating the musical generation process as an image generation problem; we utilize latent diffusion models (LDMs) to generate spectrograms, which are image representations of music. The Continuer Pipeline is able to …

Neural Tabula Rasa: Foundations For Realistic Memories And Learning, Patrick R. Perrine

Master's Theses

Understanding how neural systems perform memorization and inductive learning tasks are of key interest in the field of computational neuroscience. Similarly, inductive learning tasks are the focus within the field of machine learning, which has seen rapid growth and innovation utilizing feedforward neural networks. However, there have also been concerns regarding the precipitous nature of such efforts, specifically in the area of deep learning. As a result, we revisit the foundation of the artificial neural network to better incorporate current knowledge of the brain from computational neuroscience. More specifically, a random graph was chosen to model a neural system. This …

Solving Fjssp With A Genetic Algorithm, Michael John Srouji

Computer Science and Software Engineering

The Flexible Job Shop Scheduling Problem is an NP-Hard combinatorial problem. This paper aims to find a solution to this problem using genetic algorithms, and discuss the effectiveness of this. Initially, I did exploratory work on whether neural networks would be effective or not, and found a lot of trade offs between using neural networks and chromosome sequencing. In the end, I decided to use chromosome sequencing over neural networks, due to the scope of my problem being on a small scale rather than on a large scale.

Therefore, the genetic algorithm was implemented using chromosome sequencing. My chromosomes were …

Legislative Language For Success, Sanjana Gundala

Master's Theses

Legislative committee meetings are an integral part of the lawmaking process for local and state bills. The testimony presented during these meetings is a large factor in the outcome of the proposed bill. This research uses Natural Language Processing and Machine Learning techniques to analyze testimonies from California Legislative committee meetings from 2015-2016 in order to identify what aspects of a testimony makes it successful. A testimony is considered successful if the alignment of the testimony matches the bill outcome (alignment is "For" and the bill passes or alignment is "Against" and the bill fails). The process of finding what …

Modeling And Solving The Outsourcing Risk Management Problem In Multi-Echelon Supply Chains, Arian A. Nahangi

Master's Theses

Worldwide globalization has made supply chains more vulnerable to risk factors, increasing the associated costs of outsourcing goods. Outsourcing is highly beneficial for any company that values building upon its core competencies, but the emergence of the COVID-19 pandemic and other crises have exposed significant vulnerabilities within supply chains. These disruptions forced a shift in the production of goods from outsourcing to domestic methods.

This paper considers a multi-echelon supply chain model with global and domestic raw material suppliers, manufacturing plants, warehouses, and markets. All levels within the supply chain network are evaluated from a holistic perspective, calculating a total …

Solving Chromatic Number With Quantum Search And Quantum Counting, David Lutze

Master's Theses

This thesis presents a novel quantum algorithm that solves the Chromatic Number problem. Complexity analysis of this algorithm revealed a run time of O(2^n/2n²(log2n)²). This is an improvement over the best known algorithm, with a run time of 2ⁿn^O(1) [1]. This algorithm uses the Quantum Search algorithm (often called Grover's Algorithm), and the Quantum Counting algorithm. Chromatic Number is an example of an NP-Hard problem, which suggests that other NP-Hard problems can also benefit from a speed-up provided by quantum technology. This has wide implications as many real world problems can …

Design And Implementation Of A Deterministic And Nondeterministic Finite Automaton Simulator, Camron C. Dennler

Computer Science and Software Engineering

The purpose of this project is to assist students in visualizing and understanding the structure and operation of deterministic and nondeterministic finite automata. This software achieves this purpose by providing students with the ability to build, modify, and test automata in an intuitive environment. This enables a simple and efficient avenue for experimentation, which upholds the Cal Poly ideal of Learning by Doing.

Readers of this report should be familiar with basic concepts in the theory of finite state machines; a general understanding of object-oriented programming is also necessary.

Quantum Random Walk Search And Grover's Algorithm - An Introduction And Neutral-Atom Approach, Anna Maria Houk

Physics

In the sub-field of quantum algorithms, physicists and computer scientist take classical computing algorithms and principles and see if there is a more efficient or faster approach implementable on a quantum computer, i.e. a ”quantum advantage”. We take random walks, a widely applicable group of classical algorithms, and move them into the quantum computing paradigm. Additionally, an introduction to a popular quantum search algorithm called Grover’s search is included to guide the reader to the development of a quantum search algorithm using quantum random walks. To close the gap between algorithm and hardware, we will look at using neutral-atom (also …

Neural Network Pruning For Ecg Arrhythmia Classification, Isaac E. Labarge

Master's Theses

Convolutional Neural Networks (CNNs) are a widely accepted means of solving complex classification and detection problems in imaging and speech. However, problem complexity often leads to considerable increases in computation and parameter storage costs. Many successful attempts have been made in effectively reducing these overheads by pruning and compressing large CNNs with only a slight decline in model accuracy. In this study, two pruning methods are implemented and compared on the CIFAR-10 database and an ECG arrhythmia classification task. Each pruning method employs a pruning phase interleaved with a finetuning phase. It is shown that when performing the scale-factor pruning …

Grammar-Based Procedurally Generated Village Creation Tool, Kevin Matthew Graves

Computer Engineering

This project is a 3D village generator tool for Unity. It consists of three components: a building, mountain, and river generator. All of these generators use grammar-based procedural generation in order to create a unique and logical village and landscape each time the program is run.

Dish: Democracy In State Houses, Nicholas A. Russo

Master's Theses

In our current political climate, state level legislators have become increasingly impor- tant. Due to cuts in funding and growing focus at the national level, public oversight for these legislators has drastically decreased. This makes it difficult for citizens and activists to understand the relationships and commonalities between legislators. This thesis provides three contributions to address this issue. First, we created a data set containing over 1200 features focused on a legislator’s activity on bills. Second, we created embeddings that represented a legislator’s level of activity and engagement for a given bill using a custom model called Democracy2Vec. Third, we …

Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase

Computer Science and Software Engineering

In this project, I sought to develop and prove new algorithms to create spanning trees on general graphs with per-vertex degree constraints. This means that each vertex in the graph would have some additional value, a degree constraint d. For a spanning tree to be correct, every vertex v_i in the spanning tree must have a degree exactly equal to a degree constraint d_i. This poses an additional constraint on what would otherwise be a trivial spanning tree problem. In this paper, two proofs related to my studies will be discussed and analyzed, leading to my algorithm …

The Effect Of Endgame Tablebases On Modern Chess Engines, Christopher D. Peterson

Computer Engineering

Modern chess engines have the ability to augment their evaluation by using massive tables containing billions of positions and their memorized solutions. This report examines the importance of these tables to better understand the circumstances under which they should be used. The analysis conducted in this paper empirically examines differences in size and speed of memorized positions and their impacts on engine strength. Using this technique, situations where memorized tables improve play (and situations where they do not) are discovered.

Topographic Maps: Image Processing And Path-Finding, Calin Washington

Master's Theses

Topographic maps are an invaluable tool for planning routes through unfamiliar terrain. However, accurately planning routes on topographic maps is a time- consuming and error-prone task. One factor is the difficulty of interpreting the map itself, which requires prior knowledge and practice. Another factor is the difficulty of making choices between possible routes that have different trade-offs between length and the terrain they traverse.

To alleviate these difficulties, this thesis presents a system to automate the process of finding routes on scanned images of topographic maps. The system allows users to select any two points on a topographic map and …

Funqual: User-Defined, Statically-Checked Call Graph Constraints In C++, Andrew P. Nelson

Master's Theses

Static analysis tools can aid programmers by reporting potential programming mistakes prior to the execution of a program. Funqual is a static analysis tool that reads C++17 code ``in the wild'' and checks that the function call graph follows a set of rules which can be defined by the user. This sort of analysis can help the programmer to avoid errors such as accidentally calling blocking functions in time-sensitive contexts or accidentally allocating memory in heap-sensitive environments. To accomplish this, we create a type system whereby functions can be given user-defined type qualifiers and where users can define their own …

Optimal Layout For A Component Grid, Michael W. Ebert

Computer Science and Software Engineering

Several puzzle games include a specific type of optimization problem: given components that produce and consume different resources and a grid of squares, find the optimal way to place the components to maximize output. I developed a method to evaluate potential solutions quickly and automated the solving of the problem using a genetic algorithm.

Neural Network Ai For Fightingice, Alan D. Robison

Computer Engineering

Game AI in the fighting game genre, along the lines of Street Fighter, Mortal Kombat and Tekken, is traditionally script-based, with hard-coded reactions to various situations. Though this approach is often easy to understand and tweak, it requires substantial time and understanding of the game to implement in a way that is challenging and satisfying for the player due to the very large possibility space. This paper explores the use of neural networks as an alternative approach by implementing and training a network to select an action to take each frame based on the game state.

Battle Bot Ai – Patriot Bot, James Johnston

Computer Engineering

An entry in the the 'Battle Block AI' competition hosted by 'The AI Games'.

Co-Rotational Finite Element Solid Simulation With Collisions, Patrick Riordan

Computer Science and Software Engineering

This paper is a tutorial on how to implement a deformable solid simulation with collisions based off of Matthias Mueller's Real Time Physics Course Notes. It covers the topics continuum mechanics, finite element analysis, implicit Euler integration, and handling collision.

Calculating Staircase Slope From A Single Image, Nicholas Joseph Clarke

Master's Theses

Realistic modeling of a 3D environment has grown in popularity due to the increasing realm of practical applications. Whether for practical navigation purposes, entertainment value, or architectural standardization, the ability to determine the dimensions of a room is becoming more and more important. One of the trickier, but critical, features within any multistory environment is the staircase. Staircases are difficult to model because of their uneven surface and various depth aspects. Coupling this need is a variety of ways to reach this goal. Unfortunately, many such methods rely upon specialized sensory equipment, multiple calibrated cameras, or other such impractical setups. …

Procedural Music Generation And Adaptation Based On Game State, Timothey Andrew Adam

Master's Theses

Video game developers attempt to convey moods to emphasize their game's narrative. Events that occur within the game usually convey success or failure in some way meaningful to the story's progress. Ideally, when these events occur, the intended change in mood should be perceivable to the player. One way of doing so is to change the music. This requires musical tracks to represent many possible moods, states and game events. This can be very taxing on composers, and encoding the control flow (when to transition) of the tracks can prove to be tricky as well.

This thesis presents AUD.js, a …

Regen: Optimizing Genetic Selection Algorithms For Heterogeneous Computing, Scott Kenneth Swinkleb Winkleblack

Master's Theses

GenSel is a genetic selection analysis tool used to determine which genetic markers are informational for a given trait. Performing genetic selection related analyses is a time consuming and computationally expensive task. Due to an expected increase in the number of genotyped individuals, analysis times will increase dramatically. Therefore, optimization efforts must be made to keep analysis times reasonable.

This thesis focuses on optimizing one of GenSel’s underlying algorithms for heterogeneous computing. The resulting algorithm exposes task-level parallelism and data-level parallelism present but inaccessible in the original algorithm. The heterogeneous computing solution, ReGen, outperforms the optimized CPU implementation achieving a …

In Perfect Xen, A Performance Study Of The Emerging Xen Scheduler, Ryan Hnarakis

Master's Theses

Fifty percent of Fortune 500 companies trust Xen, an open-source bare-metal hypervisor, to virtualize their websites and mission critical services in the cloud. Providing superior fault tolerance, scalability, and migration, virtualization allows these companies to run several isolated operating systems simultaneously on the same physical server. These isolated operating systems, called virtual machines, require a virtual traffic guard to cooperate with one another. This guard known as the Credit2 scheduler along with the newest Xen hypervisor was recently developed to supersede the older schedulers. Since wasted CPU cycles can be costly, the Credit2 prototype must undergo significant performance validation before …

Protocases, Christopher M. Polis

Computer Engineering

Design and implementation of a 3D printing web application.

Integrated Collision Avoidance System Sensor Evaluation Final Design Project, Alex F. Graebe, Bridgette S. Kimball, Drew T. Lavoise

Mechanical Engineering

Following the development of Aircraft Collision Avoidance Technology (ACAT) by the National Aeronautics and Space Administration (NASA), a need arose to transition the life-saving technology to aid the general aviation community. Considering the realistic cost of implementation, it was decided that the technology should be adapted to function on any smartphone, using that device as an end-to-end solution to sense, process, and alert the pilot to imminent threats. In September of 2012, the SAS (Sense and Survive) Senior Project Team at California Polytechnic University (Cal Poly), San Luis Obispo was assigned the task of using smartphone technology to accurately sense …

An Algorithm For Quantum Circuit Optimization, Raymond Garwei Wong

Computer Science and Software Engineering

In the past 20 years, many researchers shifted their focus to developing computers based on quantum mechanical phenomenon as current computers started to plateau in performance. Some problems such as integer factorization have been shown to perform much more efficiently on a quantum computer than on its classical counterpart. However, quantum computers will continue to remain the object of theoretical research unless it can be physically manifested, and quantum circuit optimization hopes to be a useful aid in turning the theory into a reality. My project looks at a possible approach to solving the issue of circuit optimization by incorporating …

On The Complexity Of Scheduling University Courses, April L. Lovelace

Master's Theses

It has often been said that the problem of creating timetables for scheduling university courses is hard, even as hard as solving an NP-Complete problem. There are many papers in the literature that make this assertion but rarely are precise problem definitions provided and no papers were found which offered proofs that the university course scheduling problem being discussed is NP-Complete.

This thesis defines a scheduling problem that has realistic constraints. It schedules professors to sections of courses they are willing to teach at times when they are available without overloading them. Both decision and optimization versions are precisely defined. …