Theory and Algorithms Commons^™

Using Temporal Session Types To Analyze Time Complexities Of Concurrent Programs, Joseph M. Walbran

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

Das et al. develop a method for analyzing the time complexity of concurrent, message-passing algorithms. Their method is based on adding timing information to datatypes. Specifically, they use a family of datatypes called session types; these constrain the structure of interactions that may take place over a channel of communication. In Das’s system, the timing properties of an algorithm can be verified by a typechecker: if the timing information in the session types is mismatched, the computer will report a type error. In their paper, Das et al. develop the theory for such a typechecker, but do not provide an …

The Impact Of Dynamic Difficulty Adjustment On Player Experience In Video Games, Chineng Vang

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

Dynamic Difficulty Adjustment (DDA) is a process by which a video game adjusts its level of challenge to match a player’s skill level. Its popularity in the video game industry continues to grow as it has the ability to keep players continuously engaged in a game, a concept referred to as Flow. However, the influence of DDA on games has received mixed responses, specifically that it can enhance player experience as well as hinder it. This paper explores DDA through the Monte Carlo Tree Search algorithm and Reinforcement Learning, gathering feedback from players seeking to understand what about DDA is …

Scheduling Aircraft Departures To Avoid Enroute Congestion, Johannes Martinez

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

When scheduled flights are forecast to overcrowd sections of enroute airspace, an air traffic control authority may need to delay departures. Mixed integer linear programming can be used to compute a schedule that resolves the congestion while bringing the sum of all delays to a minimum. Standard linear programming constraint formulations for such scheduling problems, however, have poor run times for instances of realistic size. A new constraint formulation based on cycles and paths through a route graph reduces run times in computational experiments. It shows particularly strong performance for schedules that approach the worst-case solution times in standard formulations.

Fighting Gerrymandering By Automating Congressional Redistricting, Jacob Jenness

Scholarly Horizons: University of Minnesota, Morris Undergraduate Journal

Gerrymandering is a political problem that the United States has had for more than 200 years. Politicians have taken the dull and routine process of drawing congressional districts and turned it into a highly-partisan process. However, with recent improvements in redistricting algorithms, researchers Harry Levin and Sorelle Friedler have introduced their recursive Divide and Conquer Redistricting Algorithm. This algorithm has the potential to automate the process of congressional redistricting, thereby removing the potential for bias. By utilizing a set of partitioning and swapping algorithms, the Divide and Conquer Redistricting Algorithm achieves desirable goals, such as low population deviation, and high …

Reducing Loading On The Contralateral Limb Using Human-In-The-Loop Optimization, Siena Senatore

UNO Student Research and Creative Activity Fair

In most everyday activities, we head towards a specific goal by updating our choices for a more direct path. However, there are specific clinical tasks where taking the direct path is more challenging. Clinical investigations of optimizing a prosthesis involve the assessment of multiple parameter settings through trial and error rather than goal-directed optimization. We investigate if a human-in-the-loop optimization algorithm can guide manual alterations to a prosthesis-simulating device to reduce the ground reaction force on the contralateral limb. In most participants, the optimal condition reduced the loading rate on the contralateral limb compared to the initial condition tested. These …

Autonomous And Resilient Management Of All-Source Sensors For Navigation Integrity: A Comparison And Analysis, Niles A. Tate

Theses and Dissertations

When navigating using Global Navigation Satellite Systems (GNSS), multiple/redundant, synchronous pseudorange measurements are readily available. However, when navigating in a GNSS degraded and/or denied region, this is not guaranteed. In response to this challenge, the ANT Center developed a framework known as Autonomous and Resilient Management of All-source Sensors (ARMAS). The ARMAS framework is designed to be resilient towards data corruption caused from mismodeled, uncalibrated, and faulty sensors. This thesis further expands on this work by performing a comparison against a Residual-Based Receiver Autonomous Integrity Monitoring (RBRAIM) scheme using simulated and real flight data to evaluate each systems performance.

Hybrid Tabu Search Algorithm For Unrelated Parallel Machine Scheduling In Semiconductor Fabs With Setup Times, Job Release, And Expired Times, Changyu Chen, Madhi Fathi, Marzieh Khakifirooz, Kan Wu

Research Collection School Of Computing and Information Systems

This research is motivated by a scheduling problem arising in the ion implantation process of wafer fabrication. The ion implementation scheduling problem is modeled as an unrelated parallel machine scheduling (UPMS) problem with sequence-dependent setup times that are subject to job release time and expiration time of allowing a job to be processed on a specific machine, defined as: R|rj,eij,STsd|Cmax. The objective is first to maximize the number of processed jobs, then minimize the maximum completion time (makespan), and finally minimize the maximum completion times of the non-bottleneck machines. A mixed-integer programming (MIP) model is proposed as a solution approach …

The Effect Of Using The Gamification Strategy On Academic Achievement And Motivation Towards Learning Problem-Solving Skills In Computer And Information Technology Course Among Tenth Grade Female Students, Mazyunah Almutairi, Prof. Ahmad Almassaad

International Journal for Research in Education

Abstract

This study aimed to identify the effect of using the gamification strategy on academic achievement and motivation towards learning problem-solving skills in computer and information technology course. A quasi-experimental method was adopted. The study population included tenth-grade female students in Al-Badi’ah schools in Riyadh. The sample consisted of 54 students divided into two equal groups: control group and experimental group. The study tools comprised an achievement test and the motivation scale. The results showed that there were statistically significant differences between the two groups in the academic achievement test in favor of the experimental group, with a large effect …

Numerical Treatment For Special Type Of Mixed Linear Delay Volterra Integro-Differential Equations, Atheer J. Kadhim

Emirates Journal for Engineering Research

The idea of research is a representation of the nonlinear pseudo-random generators using state-space equations that is not based on the usual description as shift register synthesis but in terms of matrices. Different types of nonlinear pseudo-random generators with their algorithms have been applied in order to investigate the output pseudo-random sequences. Moreover, two examples are given for conciliated the results of this representation.

Provably Weak Instances Of Plwe Revisited, Again, Katherine Mendel

CSB and SJU Distinguished Thesis

Learning with Errors has emerged as a promising possibility for postquantum cryptography. Variants known as RLWE and PLWE have been shown to be more efficient, but the increased structure can leave them vulnerable to attacks for certain instantiations. This work aims to identify specific cases where proposed cryptographic schemes based on PLWE work particularly poorly under a specific attack.

The Nature Of Numbers: Real Computing, Bradley J. Lucier

Journal of Humanistic Mathematics

While studying the computable real numbers as a professional mathematician, I came to see the computable reals, and not the real numbers as usually presented in undergraduate real analysis classes, as the natural culmination of my evolving understanding of numbers as a schoolchild. This paper attempts to trace and explain that evolution. The first part recounts the nature of numbers as they were presented to us grade-school children. In particular, the introduction of square roots induced a step change in my understanding of numbers. Another incident gave me insight into the brilliance of Alan Turing in his paper introducing both …

Robust Error Estimation Based On Factor-Graph Models For Non-Line-Of-Sight Localization, O. Arda Vanli, Clark N. Taylor

Faculty Publications

This paper presents a method to estimate the covariances of the inputs in a factor-graph formulation for localization under non-line-of-sight conditions. A general solution based on covariance estimation and M-estimators in linear regression problems, is presented that is shown to give unbiased estimators of multiple variances and are robust against outliers. An iteratively re-weighted least squares algorithm is proposed to jointly compute the proposed variance estimators and the state estimates for the nonlinear factor graph optimization. The efficacy of the method is illustrated in a simulation study using a robot localization problem under various process and measurement models and measurement …

Algorithm-Based Fault Tolerance At Scale, Joshua Dennis Booth

Summer Community of Scholars (RCEU and HCR) Project Proposals

No abstract provided.

Games For One, Games For Two: Computationally Complex Fun For Polynomial-Hierarchical Families, Kye Shi

HMC Senior Theses

In the first half of this thesis, we explore the polynomial-time hierarchy, emphasizing an intuitive perspective that associates decision problems in the polynomial hierarchy to combinatorial games with fixed numbers of turns. Specifically, problems in �� are thought of as 0-turn games, ���� as 1-turn “puzzle” games, and in general ��ₖ�� as ��-turn games, in which decision problems answer the binary question, “can the starting player guarantee a win?” We introduce the formalisms of the polynomial hierarchy through this perspective, alongside definitions of ��-turn CIRCUIT SATISFIABILITY games, whose ��ₖ��-completeness is assumed from prior work (we briefly justify this assumption …

Finding Optimal Cayley Map Embeddings Using Genetic Algorithms, Jacob Buckelew

Honors Program Theses

Genetic algorithms are a commonly used metaheuristic search method aimed at solving complex optimization problems in a variety of fields. These types of algorithms lend themselves to problems that can incorporate stochastic elements, which allows for a wider search across a search space. However, the nature of the genetic algorithm can often cause challenges regarding time-consumption. Although the genetic algorithm may be widely applicable to various domains, it is not guaranteed that the algorithm will outperform other traditional search methods in solving problems specific to particular domains. In this paper, we test the feasibility of genetic algorithms in solving a …

Machine Learning In Requirements Elicitation: A Literature Review, Cheligeer Cheligeer, Jingwei Huang, Guosong Wu, Nadia Bhuiyan, Yuan Xu, Yong Zeng

Engineering Management & Systems Engineering Faculty Publications

A growing trend in requirements elicitation is the use of machine learning (ML) techniques to automate the cumbersome requirement handling process. This literature review summarizes and analyzes studies that incorporate ML and natural language processing (NLP) into demand elicitation. We answer the following research questions: (1) What requirement elicitation activities are supported by ML? (2) What data sources are used to build ML-based requirement solutions? (3) What technologies, algorithms, and tools are used to build ML-based requirement elicitation? (4) How to construct an ML-based requirements elicitation method? (5) What are the available tools to support ML-based requirements elicitation methodology? Keywords …

A Human-Centered Approach To Improving Adolescent Online Sexual Risk Detection Algorithms, Afsaneh Razi

Electronic Theses and Dissertations, 2020-2023

Computational risk detection has the potential to protect especially vulnerable populations from online victimization. Conducting a comprehensive literature review on computational approaches for online sexual risk detection led to the identification that the majority of this work has focused on identifying sexual predators after-the-fact. Also, many studies rely on public datasets and third-party annotators to establish ground truth and train their algorithms, which do not accurately represent young social media users and their perspectives to prevent victimization. To address these gaps, this dissertation integrated human-centered approaches to both creating representative datasets and developing sexual risk detection machine learning models to …

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 …

A Comparison Of Deep Learning Algorithms On Image Data For Detecting Floodwater On Roadways, Sarp Salih, Kuzlu Murat, Zhao Yanxiao, Cetin Mecit

Engineering Technology Faculty Publications

Object detection and segmentation algorithms evolved significantly in the last decade. Simultaneous object detection and segmentation paved the way for real-time applications such as autonomous driving. Detection and segmentation of (partially) flooded roadways are essential inputs for vehicle routing and traffic management systems. This paper proposes an automatic floodwater detection and segmentation method utilizing the Mask Region-Based Convolutional Neural Networks (Mask-R-CNN) and Generative Adversarial Networks (GAN) algorithms. To train the model, manually labeled images with urban, suburban, and natural settings are used. The performances of the algorithms are assessed in accurately detecting the floodwater captured in images. The results show …

On Discovering Motifs And Frequent Patterns In Spatial Trajectories With Discrete Fréchet Distance, Bo Tang, Man Lung Yiu, Kyriakos Mouratidis, Jiahao Zhang, Kai Wang

Research Collection School Of Computing and Information Systems

The discrete Fréchet distance (DFD) captures perceptual and geographical similarity between two trajectories. It has been successfully adopted in a multitude of applications, such as signature and handwriting recognition, computer graphics, as well as geographic applications. Spatial applications, e.g., sports analysis, traffic analysis, etc. require discovering similar subtrajectories within a single trajectory or across multiple trajectories. In this paper, we adopt DFD as the similarity measure, and study two representative trajectory analysis problems, namely, motif discovery and frequent pattern discovery. Due to the time complexity of DFD, these tasks are computationally challenging. We address that challenge with a suite of …