Theory and Algorithms Commons^™

Criticality Assessments For Improving Algorithmic Robustness, Thomas B. Jones

Computer Science ETDs

Though computational models typically assume all program steps execute flawlessly, that does not imply all steps are equally important if a failure should occur. In the "Constrained Reliability Allocation" problem, sufficient resources are guaranteed for operations that prompt eventual program termination on failure, but those operations that only cause output errors are given a limited budget of some vital resource, insufficient to ensure correct operation for each of them.

In this dissertation, I present a novel representation of failures based on a combination of their timing and location combined with criticality assessments---a method used to predict the behavior of systems …

Using Finite-State Models For Log Differencing, Hen Amar, Lingfeng Bao, Nimrod Busany, David Lo, Shahar Maoz

Research Collection School Of Computing and Information Systems

Much work has been published on extracting various kinds of models from logs that document the execution of running systems. In many cases, however, for example in the context of evolution, testing, or malware analysis, engineers are interested not only in a single log but in a set of several logs, each of which originated from a different set of runs of the system at hand. Then, the difference between the logs is the main target of interest. In this work we investigate the use of finite-state models for log differencing. Rather than comparing the logs directly, we generate concise …

On The Sequential Massart Algorithm For Statistical Model Checking, Cyrille Jegourel, Jun Sun, Jin Song Dong

Research Collection School Of Computing and Information Systems

Several schemes have been provided in Statistical Model Checking (SMC) for the estimation of property occurrence based on predefined confidence and absolute or relative error. Simulations might be however costly if many samples are required and the usual algorithms implemented in statistical model checkers tend to be conservative. Bayesian and rare event techniques can be used to reduce the sample size but they can not be applied without prerequisite or knowledge about the system under scrutiny. Recently, sequential algorithms based on Monte Carlo estimations and Massart bounds have been proposed to reduce the sample size while providing guarantees on error …

List, Sample, And Count, Ali Assarpour

Dissertations, Theses, and Capstone Projects

Counting plays a fundamental role in many scientific fields including chemistry, physics, mathematics, and computer science. There are two approaches for counting, the first relies on analytical tools to drive closed form expression, while the second takes advantage of the combinatorial nature of the problem to construct an algorithm whose output is the number of structures. There are many algorithmic techniques for counting, they cover the explicit approach of counting by listing to the approximate approach of counting by sampling.

This thesis looks at counting three sets of objects. First, we consider a subclass of boolean functions that are monotone. …

An Algorithmic Approach To Creating Effective Study Groups Using A Smart Phone App, Kelvin J. Rosado-Ayala

Honors College Theses

For many students entering college, meeting new people and studying are a common struggle. Study groups are generally recommended, especially if the groups are comprised of members with complementary personality traits. But the challenge still remains, how do freshmen or transfer students find and form these heterogeneous study groups. In order to help alleviate this issue, an Android application was developed to automatically create study groups for students. Using basic information provided by students upon registration, the algorithm is able to automatically find matching group members. The application was designed using an agile life cycle model over the course of …

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.

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 …

Understanding Natural Keyboard Typing Using Convolutional Neural Networks On Mobile Sensor Data, Travis Siems

Computer Science and Engineering Theses and Dissertations

Mobile phones and other devices with embedded sensors are becoming increasingly ubiquitous. Audio and motion sensor data may be able to detect information that we did not think possible. Some researchers have created models that can predict computer keyboard typing from a nearby mobile device; however, certain limitations to their experiment setup and methods compelled us to be skeptical of the models’ realistic prediction capability. We investigate the possibility of understanding natural keyboard typing from mobile phones by performing a well-designed data collection experiment that encourages natural typing and interactions. This data collection helps capture realistic vulnerabilities of the security …

Cora: Commingled Remains And Analytics – An Open Community Ecosystem, Nicole Mcelroy, Ryan Ernst

UNO Student Research and Creative Activity Fair

Anthropologists at organizations such as the DPAA (Defense POW/MIA Accounting Agency) have the tough job of sorting through commingled remains of fallen soldiers. Under the direction of Professor Pawaskar at the College of IS&T, Ryan Ernst and I are currently developing a web application for the DPAA that will help them inventory the bones and record all the appropriate associations. After the inventory web application is built we will begin the analysis process using graph theory and other mathematical algorithms. This will ultimately help organizations like the DPAA get closer to the end goal of identifying fallen soldiers from commingled …

Cross-Language Learning For Program Classification Using Bilateral Tree-Based Convolutional Neural Networks, Duy Quoc Nghi Bui, Lingxiao Jiang, Yijun Yu

Research Collection School Of Computing and Information Systems

Towards the vision of translating code that implements an algorithm from one programming language into another, this paper proposes an approach for automated program classification using bilateral tree-based convolutional neural networks (BiTBCNNs). It is layered on top of two tree-based convolutional neural networks (TBCNNs), each of which recognizes the algorithm of code written in an individual programming language. The combination layer of the networks recognizes the similarities and differences among code in different programming languages. The BiTBCNNs are trained using the source code in different languages but known to implement the same algorithms and/or functionalities. For a preliminary evaluation, we …

An Iterated Local Search Algorithm For The Team Orienteering Problem With Variable Profits, Aldy Gunawan, Kien Ming Ng, Graham Kendall, Junhan Lai

Research Collection School Of Computing and Information Systems

The orienteering problem (OP) is a routing problem that has numerous applications in various domains such as logistics and tourism. The objective is to determine a subset of vertices to visit for a vehicle so that the total collected score is maximized and a given time budget is not exceeded. The extensive application of the OP has led to many different variants, including the team orienteering problem (TOP) and the team orienteering problem with time windows. The TOP extends the OP by considering multiple vehicles. In this article, the team orienteering problem with variable profits (TOPVP) is studied. The main …

Logic -> Proof -> Rest, Maxwell Taylor

Senior Independent Study Theses

REST is a common architecture for networked applications. Applications that adhere to the REST constraints enjoy significant scaling advantages over other architectures. But REST is not a panacea for the task of building correct software. Algebraic models of computation, particularly CSP, prove useful to describe the composition of applications using REST. CSP enables us to describe and verify the behavior of RESTful systems. The descriptions of each component can be used independently to verify that a system behaves as expected. This thesis demonstrates and develops CSP methodology to verify the behavior of RESTful applications.