Theory and Algorithms Commons^™

Algorithms And Variations On The Positional Burrows-Wheeler Transform And Their Applications, Ahsan Sanaullah

Electronic Theses and Dissertations, 2020-2023

In this dissertation, we develop algorithms and variations on the Positional Burrows-Wheeler Transform (PBWT). The PBWT is a data structure that stores M binary strings of length N while allowing efficient search. We develop the dynamic-PBWT (d-PBWT). The d-PBWT is a variation of the PBWT that allows its relevant algorithms to run with unchanged time complexity, but also allows efficient insertion and deletion of haplotypes. We provide insertion and deletion algorithms on the PBWT with average case O(N) time complexity. We also improve upon the query algorithms for the PBWT. Durbin described a set maximal match query algorithm on the …

Ant Colony-Based Approach For Solving An Unmanned Aerial Vehicle Routing Problem, Youssef Harrath Dr., Jihene Kaabi Dr.

Research & Publications

Waste management issues are affecting the economic and environmental aspects of modern societies. Thus, growing the interest of academic and industrial research and development in optimizing the process of waste management. As these issues greatly impact human health and environmental aspects and impose a threat, hazardous waste management requires even much more attention. The problem studied in this research is a variant of the vehicle routing problem using an unmanned aerial vehicle (UAV). The focus of this research is on planning the routes for waste collection and disposal using a UAV. The aim is to collect all the waste as …

An Empirical Analysis Of Approximation Algorithms For The Unweighted Tree Augmentation Problem, Jacob Thomas Restanio

Graduate Theses, Dissertations, and Problem Reports (ETD)

In this thesis, we perform an experimental study of approximation algorithms for the tree augmentation problem (TAP). TAP is a fundamental problem in network design. The goal of TAP is to add the minimum number of edges from a given edge set to a tree so that it becomes 2-edge connected. Formally, given a tree T = (V, E), where V denotes the set of vertices and E denotes the set of edges in the tree, and a set of edges (or links) L ⊆ V × V disjoint from E, the objective is to find a set of edges …

Properties Of (Claw, 4k₁, Bridge)-Free Graphs, Taite Lagrange

Theses and Dissertations (Comprehensive)

Given a set H of graphs, a graph G is H-free if it does not contain any graph in H as an induced subgraph. The complexity of the colouring problem is known when H is a set of graphs on four vertices, with three exceptions. One of those exceptions is the case of {claw, 4K₁}-free graphs, for which our classes of {claw, 4K₁, bridge}-free and {claw, 4K₁, bridge,C₄-twin}-free graphs are subclasses.

The original goal of this work was to prove that {claw, 4K₁, …

Improving Connectivity For Remote Cancer Patient Symptom Monitoring And Reporting In Rural Medically Underserved Regions, Esther Max-Onakpoya

Theses and Dissertations--Computer Science

Rural residents are often faced with many disparities when compared to their urban counterparts. Two key areas where these disparities are apparent are access to health and Internet services. Improved access to healthcare services has the potential to increase residents' quality of life and life expectancy. Additionally, improved access to Internet services can create significant social returns in increasing job and educational opportunities, and improving access to healthcare. Therefore, this dissertation focuses on the intersection between access to Internet and healthcare services in rural areas. More specifically, it attempts to analyze systems that can be used to improve Internet access …

Small Approximate Pareto Sets With Quality Bounds, William Bailey

Theses and Dissertations--Computer Science

We present and empirically characterize a general, parallel, heuristic algorithm for computing small ε-Pareto sets. The algorithm can be used as part of a decision support tool for settings in which computing points in objective space is computationally expensive. We use the graph clearing problem, a formalization of indirect organ exchange markets, as a prototypical example setting. We characterize the performance of the algorithm through ε-Pareto set size, ε value provided, and parallel speedup achieved. Our results show that the algorithm's combination of parallel speedup and small ε-Pareto sets is sufficient to be appealing in settings requiring manual review (i.e., …

The Basil Technique: Bias Adaptive Statistical Inference Learning Agents For Learning From Human Feedback, Jonathan Indigo Watson

Theses and Dissertations--Computer Science

We introduce a novel approach for learning behaviors using human-provided feedback that is subject to systematic bias. Our method, known as BASIL, models the feedback signal as a combination of a heuristic evaluation of an action's utility and a probabilistically-drawn bias value, characterized by unknown parameters. We present both the general framework for our technique and specific algorithms for biases drawn from a normal distribution. We evaluate our approach across various environments and tasks, comparing it to interactive and non-interactive machine learning methods, including deep learning techniques, using human trainers and a synthetic oracle with feedback distorted to varying degrees. …

Architectural Design Of A Blockchain-Enabled, Federated Learning Platform For Algorithmic Fairness In Predictive Health Care: Design Science Study, Xueping Liang, Juan Zhao, Yan Chen, Eranga Bandara, Sachin Shetty

VMASC Publications

Background: Developing effective and generalizable predictive models is critical for disease prediction and clinical decision-making, often requiring diverse samples to mitigate population bias and address algorithmic fairness. However, a major challenge is to retrieve learning models across multiple institutions without bringing in local biases and inequity, while preserving individual patients' privacy at each site.

Objective: This study aims to understand the issues of bias and fairness in the machine learning process used in the predictive health care domain. We proposed a software architecture that integrates federated learning and blockchain to improve fairness, while maintaining acceptable prediction accuracy and minimizing overhead …

Peer-To-Peer Energy Trading In Smart Residential Environment With User Behavioral Modeling, Ashutosh Timilsina

Theses and Dissertations--Computer Science

Electric power systems are transforming from a centralized unidirectional market to a decentralized open market. With this shift, the end-users have the possibility to actively participate in local energy exchanges, with or without the involvement of the main grid. Rapidly reducing prices for Renewable Energy Technologies (RETs), supported by their ease of installation and operation, with the facilitation of Electric Vehicles (EV) and Smart Grid (SG) technologies to make bidirectional flow of energy possible, has contributed to this changing landscape in the distribution side of the traditional power grid.

Trading energy among users in a decentralized fashion has been referred …

Crosshair Optimizer, Jason Torrence

All Master's Theses

Metaheuristic optimization algorithms are heuristics that are capable of creating a "good enough'' solution to a computationally complex problem. Algorithms in this area of study are focused on the process of exploration and exploitation: exploration of the solution space and exploitation of the results that have been found during that exploration, with most resources going toward the former half of the process. The novel Crosshair optimizer developed in this thesis seeks to take advantage of the latter, exploiting the best possible result as much as possible by directly searching the area around that best result with a stochastic approach. This …

Clusters, Curves, And Centroids: Stellar Flare Morphology In The Ultraviolet, Vera Berger

Pomona Senior Theses

With a novel sample of 495 high-cadence light curves for stellar flares in the near-ultraviolet, I explore similarity measures, clustering algorithms, averaging methods, and curve fitting techniques for time series. This work seeks to provide insight into whether stellar flares are similar across stars, if we can identify physically meaningful patterns in their light curves, and how to construct a comprehensive model for flares. I construct the first empirical template for flare light curves in the ultraviolet, and compute ``average elements" of flares displaying complex features such as quasi-periodic oscillations and multipeak structures. Developing accurate models for flares in the …

An Empirical Analysis Of Algorithms For Simple Stochastic Games, Cody William Klingler

Graduate Theses, Dissertations, and Problem Reports (ETD)

This thesis presents the findings of a computational study on algorithms for Simple Stochastic Games (SSG). Simple Stochastic Games are a restriction of the Shapley stochastic model motivated by their applications in AI planning, logic synthesis, and theoretical computer science. This thesis seeks to empirically assess the performance of these algorithms to compensate for their lack of strong complexity results. Where applicable, we include both variations of algorithms where stable strategies are computed by a linear-programming and naive approach. These algorithms are evaluated on random inputs, in addition to specific difficult cases that were identified experimentally. We are interested in …

A Hierarchical Approach To Improve The Ant Colony Optimization Algorithm, Bryan J. Fischer

EWU Masters Thesis Collection

The ant colony optimization algorithm (ACO) is a fast heuristic-based method for finding favorable solutions to the traveling salesman problem (TSP). When the data set reaches larger values however, the ACO runtime increases dramatically. As a result, clustering nodes into groups is an effective way to reduce the size of the problem while leveraging the advantages of the ACO algorithm. The method for recombining groups of nodes is explored by treating the graph as a hierarchy of clusters, and modifying the original ACO heuristic to operate on a hypergraph. This method of using hierarchical clustering is significantly faster than the …

Liquid Tab, Nathan Hulet

Williams Honors College, Honors Research Projects

Guitar transcription is a complex task requiring significant time, skill, and musical knowledge to achieve accurate results. Since most music is recorded and processed digitally, it would seem like many tools to digitally analyze and transcribe the audio would be available. However, the problem of automatic transcription presents many more difficulties than are initially evident. There are multiple ways to play a guitar, many diverse styles of playing, and every guitar sounds different. These problems become even more difficult considering the varying qualities of recordings and levels of background noise.

Machine learning has proven itself to be a flexible tool …

Comparative Analysis Of Fullstack Development Technologies: Frontend, Backend And Database, Qozeem Odeniran

College of Graduate Studies: Theses & Dissertations

Accessing websites with various devices has brought changes in the field of application development. The choice of cross-platform, reusable frameworks is very crucial in this era. This thesis embarks in the evaluation of front-end, back-end, and database technologies to address the status quo. Study-a explores front-end development, focusing on angular.js and react.js. Using these frameworks, comparative web applications were created and evaluated locally. Important insights were obtained through benchmark tests, lighthouse metrics, and architectural evaluations. React.js proves to be a performance leader in spite of the possible influence of a virtual machine, opening the door for additional research. Study b …

Face Anti-Spoofing And Deep Learning Based Unsupervised Image Recognition Systems, Enoch Solomon

Theses and Dissertations

One of the main problems of a supervised deep learning approach is that it requires large amounts of labeled training data, which are not always easily available. This PhD dissertation addresses the above-mentioned problem by using a novel unsupervised deep learning face verification system called UFace, that does not require labeled training data as it automatically, in an unsupervised way, generates training data from even a relatively small size of data. The method starts by selecting, in unsupervised way, k-most similar and k-most dissimilar images for a given face image. Moreover, this PhD dissertation proposes a new loss function to …

Influence Maximization Based On Community Detection And Dominating Sets, Ameya Marathe

Master's Projects

An online platform where various people come together to share information and communicate is called a social network. These platforms are set apart from other means of communication mostly because you can follow and interact also with different people even some you never met, comment on their posts, and re-sharing their posts. Companies such as Amazon and Walmart use these platforms daily for marketing purposes, like spreading information regarding new products and services they offer. They carefully select a subset of users, called influencers, who are usually the ones with high influence over the rest of the users. Influencers receive …

Dynamic Function Learning Through Control Of Ensemble Systems, Wei Zhang, Vignesh Narayanan, Jr-Shin Li

Publications

Learning tasks involving function approximation are preva- lent in numerous domains of science and engineering. The underlying idea is to design a learning algorithm that gener- ates a sequence of functions converging to the desired target function with arbitrary accuracy by using the available data samples. In this paper, we present a novel interpretation of iterative function learning through the lens of ensemble dy- namical systems, with an emphasis on establishing the equiv- alence between convergence of function learning algorithms and asymptotic behavior of ensemble systems. In particular, given a set of observation data in a function learning task, we …

Cooperative Deep Q -Learning Framework For Environments Providing Image Feedback, Krishnan Raghavan, Vignesh Narayanan, Sarangapani Jagannathan

Publications

In this article, we address two key challenges in deep reinforcement learning (DRL) setting, sample inefficiency, and slow learning, with a dual-neural network (NN)-driven learning approach. In the proposed approach, we use two deep NNs with independent initialization to robustly approximate the action-value function in the presence of image inputs. In particular, we develop a temporal difference (TD) error-driven learning (EDL) approach, where we introduce a set of linear transformations of the TD error to directly update the parameters of each layer in the deep NN. We demonstrate theoretically that the cost minimized by the EDL regime is an approximation …

A Structure-Aware Generative Adversarial Network For Bilingual Lexicon Induction, Bocheng Han, Qian Tao, Lusi Li, Zhihao Xiong

Computer Science Faculty Publications

Bilingual lexicon induction (BLI) is the task of inducing word translations with a learned mapping function that aligns monolingual word embedding spaces in two different languages. However, most previous methods treat word embeddings as isolated entities and fail to jointly consider both the intra-space and inter-space topological relations between words. This limitation makes it challenging to align words from embedding spaces with distinct topological structures, especially when the assumption of isomorphism may not hold. To this end, we propose a novel approach called the Structure-Aware Generative Adversarial Network (SA-GAN) model to explicitly capture multiple topological structure information to achieve accurate …