Theory and Algorithms Commons^™

Implementing The Cms+ Sports Rankings Algorithm In A Javafx Environment, Luke Welch

Industrial Engineering Undergraduate Honors Theses

Every year, sports teams and athletes get cut from championship opportunities because of their rank. While this reality is easier to swallow if a team or athlete is distant from the cut, it is much harder when they are right on the edge. Many times, it leaves fans and athletes wondering, “Why wasn’t I ranked higher? What factors when into the ranking? Are the rankings based on opinion alone?” These are fair questions that deserve an answer. Many times, sports rankings are derived from opinion polls. Other times, they are derived from a combination of opinion polls and measured performance. …

Risk Gameplay Analysis Using Stochastic Beam Search, Jacob Gillenwater

Electronic Theses and Dissertations

Hasbro’s RISK, first published in 1959, is a complex multiplayer strategy game that has received little attention from the scientific community. Training artificial intelligence (AI) agents using stochastic beam search gives insight into effective strategy when playing RISK. A comprehensive analysis of the systems of play challenges preconceptions about good strategy in some areas of the game while reinforcing those preconceptions in others. This study applies stochastic beam search to discover optimal strategies in RISK. Results of the search show both support for and challenges to traditionally held positions about RISK gameplay. While stochastic beam search competently investigates gameplay on …

The Executive’S Guide To Getting Ai Wrong, Jerrold Soh

Asian Management Insights

This article explores how we see AI and argues that we mostly get it wrong. In the process, it explains the reasons backed by social science research on why we tend to get AI wrong and illustrates the dangers of doing so from a managerial and law-making perspective. Some readers may also find the article useful as a guide on how and when to manipulate portrayals of AI in your favour.

Undiscounted Recursive Path Choice Models: Convergence Properties And Algorithms, Tien Mai, Emma Frejinger

Research Collection School Of Computing and Information Systems

Traffic flow predictions are central to a wealth of problems in transportation. Path choice models can be used for this purpose, and in state-of-the-art models—so-called recursive path choice (RPC) models—the choice of a path is formulated as a sequential arc choice process using undiscounted Markov decision process (MDP) with an absorbing state. The MDP has a utility maximization objective with unknown parameters that are estimated based on data. The estimation and prediction using RPC models require repeatedly solving value functions that are solutions to the Bellman equation. Although there are several examples of successful applications of RPC models in the …

A Machine-Verified Proof Of Linearizability For A Queue Algorithm, Ugur Yavuz

Dartmouth College Master’s Theses

Proofs of linearizability are typically intricate and lengthy, and readers may find it difficult to verify their correctness. We present a unique technique for producing proofs of linearizability that are fully verifiable by a mechanical proof system, thereby eliminating the need for any manual verification. Specifically, we reduce the burden of proving linearizable object implementations correct to the proof of a particular invariant whose correctness can be shown inductively. Noting that the latter is a task that many proof systems (such as the TLA+ Proof System we chose to work with) are well-suited to handle, this technique allows us to …

Tiktok As A Digital Activism Space: Social Justice Under Algorithmic Control, Brittany Haslem

Institute for the Humanities Theses

TikTok, a video sharing application, has become the center of viral internet culture. The app has risen in popularity so quickly that scholarly literature investigating its vast societal impact is still nascent. TikTok is not only used to discuss popular culture topics and create trends, but also being utilized as a tool for social justice activism in the United States in the wake of a tumultuous year with major events such as the coronavirus pandemic, a resurgence of the Black Lives Matter movement, and the 2020 presidential election. TikTok activism is not without critiques, ranging from concerns of foreign government …

Simulating Polistes Dominulus Nest-Building Heuristics With Deterministic And Markovian Properties, Benjamin Pottinger

Undergraduate Honors Theses

European Paper Wasps (Polistes dominula) are social insects that build round, symmetrical nests. Current models indicate that these wasps develop colonies by following simple heuristics based on nest stimuli. Computer simulations can model wasp behavior to imitate natural nest building. This research investigated various building heuristics through a novel Markov-based simulation. The simulation used a hexagonal grid to build cells based on the building rule supplied to the agent. Nest data was compared with natural data and through visual inspection. Larger nests were found to be less compact for the rules simulated.

Optimized Damage Assessment And Recovery Through Data Categorization In Critical Infrastructure System., Shruthi Ramakrishnan

Graduate Theses and Dissertations

Critical infrastructures (CI) play a vital role in majority of the fields and sectors worldwide. It contributes a lot towards the economy of nations and towards the wellbeing of the society. They are highly coupled, interconnected and their interdependencies make them more complex systems. Thus, when a damage occurs in a CI system, its complex interdependencies make it get subjected to cascading effects which propagates faster from one infrastructure to another resulting in wide service degradations which in turn causes economic and societal effects. The propagation of cascading effects of disruptive events could be handled efficiently if the assessment and …

Robust And Fair Machine Learning Under Distribution Shift, Wei Du

Graduate Theses and Dissertations

Machine learning algorithms have been widely used in real world applications. The development of these techniques has brought huge benefits for many AI-related tasks, such as natural language processing, image classification, video analysis, and so forth. In traditional machine learning algorithms, we usually assume that the training data and test data are independently and identically distributed (iid), indicating that the model learned from the training data can be well applied to the test data with good prediction performance. However, this assumption is quite restrictive because the distribution shift can exist from the training data to the test data in many …

A Novel Data Lineage Model For Critical Infrastructure And A Solution To A Special Case Of The Temporal Graph Reachability Problem, Ian Moncur

Graduate Theses and Dissertations

Rapid and accurate damage assessment is crucial to minimize downtime in critical infrastructure. Dependency on modern technology requires fast and consistent techniques to prevent damage from spreading while also minimizing the impact of damage on system users. One technique to assist in assessment is data lineage, which involves tracing a history of dependencies for data items. The goal of this thesis is to present one novel model and an algorithm that uses data lineage with the goal of being fast and accurate. In function this model operates as a directed graph, with the vertices being data items and edges representing …

Sanitizable Access Control System For Secure Cloud Storage Against Malicious Data Publishers, Willy Susilo, Peng Jiang, Jianchang Lai, Fuchun Guo, Guomin Yang, Robert H. Deng

Research Collection School Of Computing and Information Systems

Cloud computing is considered as one of the most prominent paradigms in the information technology industry, since it can significantly reduce the costs of hardware and software resources in computing infrastructure. This convenience has enabled corporations to efficiently use the cloud storage as a mechanism to share data among their employees. At the first sight, by merely storing the shared data as plaintext in the cloud storage and protect them using an appropriate access control would be a nice solution. This is assuming that the cloud is fully trusted for not leaking any information, which is impractical as the cloud …

Learning Transferable Perturbations For Image Captioning, Hanjie Wu, Yongtuo Liu, Hongmin Cai, Shengfeng He

Research Collection School Of Computing and Information Systems

Present studies have discovered that state-of-the-art deep learning models can be attacked by small but well-designed perturbations. Existing attack algorithms for the image captioning task is time-consuming, and their generated adversarial examples cannot transfer well to other models. To generate adversarial examples faster and stronger, we propose to learn the perturbations by a generative model that is governed by three novel loss functions. Image feature distortion loss is designed to maximize the encoded image feature distance between original images and the corresponding adversarial examples at the image domain, and local-global mismatching loss is introduced to separate the mapping encoding representation …

Neighborhood Cooperative Multiagent Reinforcement Learning For Adaptive Traffic Signal Control In Epidemic Regions, Chengwei Zhang, Yu Tian, Zhibin Zhang, Wanli Xue, Xiaofei Xie, Tianpei Yang, Xin Ge, Rong Chen

Research Collection School Of Computing and Information Systems

Nowadays, multiagent reinforcement learning (MARL) have shared significant advances in the adaptive traffic signal control (ATSC) problems. For most of the researches, agents are all isomorphic, which disregards the situation in which isomerous intersections cooperative together in a real ATSC scenario, especially in epidemic regions where different intersections have quite different levels of importance. To this end, this paper models the ATSC problem as a networked Markov game (NMG), in which agents take into account information, including traffic conditions of it and its connected neighbors. A cooperative MARL framework named neighborhood cooperative hysteretic DQN (NC-HDQN) is proposed. Specifically, for each …

Performance Improvements In Inner Product Encryption, Serena Riback

Honors Scholar Theses

Consider a database that contains thousands of entries of the iris biometric. Each entry identifies an individual, so it is especially important that it remains secure. However, searching for entries among an encrypted database proves to be a security problem - how should one search encrypted data without leaking any information to a potential attacker? The proximity searchable encryption scheme, as discussed in the work by Cachet et al., uses the notions of inner product encryption developed by Kim et al.. In this paper, we will focus on the efficiency of these schemes. Specifically, how the symmetry of the bilinear …

Computer Simulation Of Raman Spectra And Mode Assignment: Application To Methane, Oluwaseun Omodemi, Ciara Tyler, Martina Kaledin

Symposium of Student Scholars

This work uses driven molecular dynamics (DMD) method, in conjunction with an analytic PES calculated using MP2/aug-cc-pVDZ energies to identify and assign Raman vibrational modes of methane. Recently, a new linearized approach was proposed for the Polarizability Tensor Surfaces (PTS) that yields a unique solution to the least-squares fitting problem and provides a competitive level of accuracy compared to the non-linear PTS model. We used the previously reported B3LYP/6-31+G(d) molecular geometries for CH₄ and generated a new PTS at the MP2/aug-cc-pVDZ level of theory. The performance of the linearly parametrized functional form for the CH₄ PTS is examined. …

Applications Of Parallel Discrete Event Simulation, Erik J. Jensen

Modeling, Simulation and Visualization Student Capstone Conference

This work presents three applications of parallel discrete event simulation (PDES), which describe the motivation for and the benefits of using PDES, the kinds of synchronization algorithms that are used, and scaling behavior with these different synchronization algorithms.

Practical Considerations And Applications For Autonomous Robot Swarms, Rory Alan Hector

LSU Doctoral Dissertations

In recent years, the study of autonomous entities such as unmanned vehicles has begun to revolutionize both military and civilian devices. One important research focus of autonomous entities has been coordination problems for autonomous robot swarms. Traditionally, robot models are used for algorithms that account for the minimum specifications needed to operate the swarm. However, these theoretical models also gloss over important practical details. Some of these details, such as time, have been considered before (as epochs of execution). In this dissertation, we examine these details in the context of several problems and introduce new performance measures to capture practical …

Ubjective Information And Survival In A Simulated Biological System, Tyler S. Barker, Massimiliano Pierobon, Peter J. Thomas

School of Computing: Faculty Publications

Information transmission and storage have gained traction as unifying concepts to characterize biological systems and their chances of survival and evolution at multiple scales. Despite the potential for an information-based mathematical framework to offer new insights into life processes and ways to interact with and control them, the main legacy is that of Shannon’s, where a purely syntactic characterization of information scores systems on the basis of their maximum information efficiency. The latter metrics seem not entirely suitable for biological systems, where transmission and storage of different pieces of information (carrying different semantics) can result in different chances of survival. …

Engr 692 Section 66: Randomized Algorithms, Yixin Chen

GMAS Course Syllabi

No abstract provided.

A Super Fast Algorithm For Estimating Sample Entropy, Weifeng Liu, Ying Jiang, Yuesheng Xu

Mathematics & Statistics Faculty Publications

: Sample entropy, an approximation of the Kolmogorov entropy, was proposed to characterize complexity of a time series, which is essentially defined as − log(B/A), where B denotes the number of matched template pairs with length m and A denotes the number of matched template pairs with m + 1, for a predetermined positive integer m. It has been widely used to analyze physiological signals. As computing sample entropy is time consuming, the box-assisted, bucket-assisted, x-sort, assisted sliding box, and kd-tree-based algorithms were proposed to accelerate its computation. These algorithms require O(N²) or …

Algorithm Selection For The Team Orienteering Problem, Mustafa Misir, Aldy Gunawan, Pieter Vansteenwegen

Research Collection School Of Computing and Information Systems

This work utilizes Algorithm Selection for solving the Team Orienteering Problem (TOP). The TOP is an NP-hard combinatorial optimization problem in the routing domain. This problem has been modelled with various extensions to address different real-world problems like tourist trip planning. The complexity of the problem motivated to devise new algorithms. However, none of the existing algorithms came with the best performance across all the widely used benchmark instances. This fact suggests that there is a performance gap to fill. This gap can be targeted by developing more new algorithms as attempted by many researchers before. An alternative strategy is …

Understanding The Mechanism Of Deep Learning Frameworks In Lesion Detection For Pathological Images With Breast Cancer, Wei-Wen Hsu, Chung-Hao Chen, Chang Hao, Yu-Ling Hou, Xiang Gao, Yun Shao, Xueli Zhang, Jingjing Wang, Tao He, Yanhong Tai

Electrical & Computer Engineering Faculty Publications

With the advances of scanning sensors and deep learning algorithms, computational pathology has drawn much attention in recent years and started to play an important role in the clinical workflow. Computer-aided detection (CADe) systems have been developed to assist pathologists in slide assessment, increasing diagnosis efficiency and reducing misdetections. In this study, we conducted four experiments to demonstrate that the features learned by deep learning models are interpretable from a pathological perspective. In addition, classifiers such as the support vector machine (SVM) and random forests (RF) were used in experiments to replace the fully connected layers and decompose the end-to-end …

Assessing Photogrammetry Artificial Intelligence In Monumental Buildings’ Crack Digital Detection, Said Maroun, Mostafa Khalifa, Nabil Mohareb

Architecture and Planning Journal (APJ)

Natural and human-made disasters have significant impacts on monumental buildings, threatening them from being deteriorated. If no rapid consolidations took into consideration traumatic accidents would endanger the existence of precious sites. In this context, Beirut's enormous 4th of August 2020 explosion damaged an estimated 640 historical monuments, many volunteers assess damages for more than a year to prevent the more crucial risk of demolitions. This research aims to assist the collaboration ability among photogrammetry science, Artificial Intelligence Model (AIM) and Architectural Coding to optimize the process for better coverage and scientific approach of data specific to the crack disorders to …

The Global Rise Of Online Devices, Cyber Crime And Cyber Defense: Enhancing Ethical Actions, Counter Measures, Cyber Strategy, And Approaches, Naresh Kshetri

Dissertations

The rise of online devices, online users, online shopping, online gaming, and online teaching has ultimately given rise to online attacks and online crimes. As cases of COVID-19 seem to increase day by day, so do online crimes and attacks (as many sectors and organizations went 100% online). Technological advancements and cyber warfare already generated many ethical issues, as internet users increasingly need ethical cyber defense strategies.

Individual internet users have challenges on their end; and on the other end, nation states (some secretly, some openly), are investing in robot weapons and autonomous weapons systems (AWS). New technologies have combined …

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 …

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 …