Theory and Algorithms Commons^™

Extensions Of The Morse-Hedlund Theorem, Eben Blaisdell

Honors Theses

Bi-infinite words are sequences of characters that are infinite forwards and backwards; for example "...ababababab...". The Morse-Hedlund theorem says that a bi-infinite word f repeats itself, in at most n letters, if and only if the number of distinct subwords of length n is at most n. Using the example, "...ababababab...", there are 2 subwords of length 3, namely "aba" and "bab". Since 2 is less than 3, we must have that "...ababababab..." repeats itself after at most 3 letters. In fact it does repeat itself every two letters. …

Bi-Objective Optimization Of Kidney Exchanges, Siyao Xu

Theses and Dissertations--Computer Science

Matching people to their preferences is an algorithmic topic with real world applications. One such application is the kidney exchange. The best "cure" for patients whose kidneys are failing is to replace it with a healthy one. Unfortunately, biological factors (e.g., blood type) constrain the number of possible replacements. Kidney exchanges seek to alleviate some of this pressure by allowing donors to give their kidney to a patient besides the one they most care about and in turn the donor for that patient gives her kidney to the patient that this first donor most cares about. Roth et al.~first discussed …

Ultra-Fast And Memory-Efficient Lookups For Cloud, Networked Systems, And Massive Data Management, Ye Yu

Theses and Dissertations--Computer Science

Systems that process big data (e.g., high-traffic networks and large-scale storage) prefer data structures and algorithms with small memory and fast processing speed. Efficient and fast algorithms play an essential role in system design, despite the improvement of hardware. This dissertation is organized around a novel algorithm called Othello Hashing. Othello Hashing supports ultra-fast and memory-efficient key-value lookup, and it fits the requirements of the core algorithms of many large-scale systems and big data applications. Using Othello hashing, combined with domain expertise in cloud, computer networks, big data, and bioinformatics, I developed the following applications that resolve several major …

Implementing Write Compression In Flash Memory Using Zeckendorf Two-Round Rewriting Codes, Vincent T. Druschke

Dissertations, Master's Theses and Master's Reports

Flash memory has become increasingly popular as the underlying storage technology for high-performance nonvolatile storage devices. However, while flash offers several benefits over alternative storage media, a number of limitations still exist within the current technology. One such limitation is that programming (altering a bit from its default value) and erasing (returning a bit to its default value) are asymmetric operations in flash memory devices: a flash memory can be programmed arbitrarily, but can only be erased in relatively large batches of storage bits called blocks, with block sizes ranging from 512K up to several megabytes. This creates a situation …

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.

Applying Machine Learning To Advance Cyber Security: Network Based Intrusion Detection Systems, Hassan Hadi Latheeth Al-Maksousy

Computer Science Theses & Dissertations

Many new devices, such as phones and tablets as well as traditional computer systems, rely on wireless connections to the Internet and are susceptible to attacks. Two important types of attacks are the use of malware and exploiting Internet protocol vulnerabilities in devices and network systems. These attacks form a threat on many levels and therefore any approach to dealing with these nefarious attacks will take several methods to counter. In this research, we utilize machine learning to detect and classify malware, visualize, detect and classify worms, as well as detect deauthentication attacks, a form of Denial of Service (DoS). …

Fast Identification Of High Utility Itemsets From Candidates, Jun-Feng Qu, Mengchi Liu, Chunsheng Xin, Zhongbo Wu

Electrical & Computer Engineering Faculty Publications

High utility itemsets (HUIs) are sets of items with high utility, like profit, in a database. Efficient mining of high utility itemsets is an important problem in the data mining area. Many mining algorithms adopt a two-phase framework. They first generate a set of candidate itemsets by roughly overestimating the utilities of all itemsets in a database, and subsequently compute the exact utility of each candidate to identify HUIs. Therefore, the major costs in these algorithms come from candidate generation and utility computation. Previous works mainly focus on how to reduce the number of candidates, without dedicating much attention to …

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 …

Intersection Of Art And Science Ii, Petronio Bendito, Tim Korb

Lawson Building Exhibitions on the Intersection of Art and Science

The Intersection of Art and Science exhibition is an interdisciplinary educational project that examines a wide range of expressive approaches explored by international artists working at the intersection of art, mathematics, computer science, and technology. It is a joint collaboration between the Department of Computer Science and the Patti and Rusty Rueff School of Visual and Performing Arts at Purdue University. Featured artists: Manuel Baez, Sarah Berube, Robert Bosch, Sage Jenson, Jean-Marc Castera, Marc Chamberland, Marion Chamberland, Laura De Decker, Bathsheba Grossman, Colin Liotta, Vincent J. Matsko, Kerry Mitchell, Janna Schimka, Rolf Schmuck, and Markus Schwehm. The exhibition was curated …

Evaluating A Cluster Of Low-Power Arm64 Single-Board Computers With Mapreduce, Daniel Mcdermott

EWU Masters Thesis Collection

With the meteoric rise of enormous data collection in science, industry, and the cloud, methods for processing massive datasets have become more crucial than ever. MapReduce is a restricted programing model for expressing parallel computations as simple serial functions, and an execution framework for distributing those computations over large datasets residing on clusters of commodity hardware. MapReduce abstracts away the challenging low-level synchronization and scalability details which parallel and distributed computing often necessitate, reducing the concept burden on programmers and scientists who require data processing at-scale. Typically, MapReduce clusters are implemented using inexpensive commodity hardware, emphasizing quantity over quality due …

Smartphone User Privacy Preserving Through Crowdsourcing, Bahman Rashidi

Theses and Dissertations

In current Android architecture, users have to decide whether an app is safe to use or not. Expert users can make savvy decisions to avoid unnecessary private data breach. However, the majority of regular users are not technically capable or do not care to consider privacy implications to make safe decisions. To assist the technically incapable crowd, we propose a permission control framework based on crowdsourcing. At its core, our framework runs new apps under probation mode without granting their permission requests up-front. It provides recommendations on whether to accept or not the permission requests based on decisions from peer …

High-Order Integral Equation Methods For Quasi-Magnetostatic And Corrosion-Related Field Analysis With Maritime Applications, Robert Pfeiffer

Theses and Dissertations--Electrical and Computer Engineering

This dissertation presents techniques for high-order simulation of electromagnetic fields, particularly for problems involving ships with ferromagnetic hulls and active corrosion-protection systems.

A set of numerically constrained hexahedral basis functions for volume integral equation discretization is presented in a method-of-moments context. Test simulations demonstrate the accuracy achievable with these functions as well as the improvement brought about in system conditioning when compared to other basis sets.

A general method for converting between a locally-corrected Nyström discretization of an integral equation and a method-of-moments discretization is presented next. Several problems involving conducting and magnetic-conducting materials are solved to verify the accuracy …

Mechanism Design, Matching Theory And The Stable Roommates Problem, Yashaswi Mohanty

Honors Theses

This thesis consists of two independent albeit related chapters. The first chapter introduces concepts from mechanism design and matching theory, and discusses potential applications of this theory, particularly in relation to dorm allocations in colleges. The second chapter investigates a subset of the dorm allocation problem, namely that of matching roommates. In particular, the paper looks at the probability of solvability of random instances of the stable roommates game under the condition that preferences are not completely random and exogenous but endogenously determined through a dependence on room choice. These probabilities are estimated using Monte-Carlo simulations and then compared with …

Gpu Accelerated Risk Quantification, Forrest L. Ireland

EWU Masters Thesis Collection

Factor Analysis of Information Risk (FAIR) is a standard model for quantitatively estimating cybersecurity risks and has been implemented as a sequential Monte Carlo simulation in the RiskLens and FAIR-U applications. Monte Carlo simulations employ random sampling techniques to model certain systems through the course of many iterations. Due to their sequential nature, FAIR simulations in these applications are limited in the number of iterations they can perform in a reasonable amount of time. One method that has been extensively used to speed up Monte Carlo simulations is to implement them to take advantage of the massive parallelization available when …

Dynamic Output Feedback Invariants Of Full Relative Degree Nonlinear Siso Systems, W. Steven Gray, Luis A. Duffaut Espinosa

Electrical & Computer Engineering Faculty Publications

The goal of this paper is to explicitly describe invariants of a plant described by a Chen--Fliess series under a class of dynamic output feedback laws using earlier work by the authors on feedback transformation groups. The main result requires the rather strong assumption that the plant has a generating series with both finite Lie rank and full relative degree. In which case, there is no loss of generality in working with state space realizations of the plant. An additional genericness assumption regarding the normal form of the plant is also required, but as shown by the examples, this condition …

Resource Optimization In Wireless Sensor Networks For An Improved Field Coverage And Cooperative Target Tracking, Husam Sweidan

Dissertations, Master's Theses and Master's Reports

There are various challenges that face a wireless sensor network (WSN) that mainly originate from the limited resources a sensor node usually has. A sensor node often relies on a battery as a power supply which, due to its limited capacity, tends to shorten the life-time of the node and the network as a whole. Other challenges arise from the limited capabilities of the sensors/actuators a node is equipped with, leading to complication like a poor coverage of the event, or limited mobility in the environment. This dissertation deals with the coverage problem as well as the limited power and …

Offline And Online Density Estimation For Large High-Dimensional Data, Aref Majdara

Dissertations, Master's Theses and Master's Reports

Density estimation has wide applications in machine learning and data analysis techniques including clustering, classification, multimodality analysis, bump hunting and anomaly detection. In high-dimensional space, sparsity of data in local neighborhood makes many of parametric and nonparametric density estimation methods mostly inefficient.

This work presents development of computationally efficient algorithms for high-dimensional density estimation, based on Bayesian sequential partitioning (BSP). Copula transform is used to separate the estimation of marginal and joint densities, with the purpose of reducing the computational complexity and estimation error. Using this separation, a parallel implementation of the density estimation algorithm on a 4-core CPU is …

Code: Coherence Based Decision Boundaries For Feature Correspondence, Wen-Yan Lin, Fan Wang, Ming-Ming Cheng, Sai-Kit Yeung, Philip H. S. Torr, Jiangbo Lu

Research Collection School Of Computing and Information Systems

A key challenge in feature correspondence is the difficulty in differentiating true and false matches at a local descriptor level. This forces adoption of strict similarity thresholds that discard many true matches. However, if analyzed at a global level, false matches are usually randomly scattered while true matches tend to be coherent (clustered around a few dominant motions), thus creating a coherence based separability constraint. This paper proposes a non-linear regression technique that can discover such a coherence based separability constraint from highly noisy matches and embed it into a correspondence likelihood model. Once computed, the model can filter the …

Design And Implementation Of A Stand-Alone Tool For Metabolic Simulations, Milad Ghiasi Rad

School of Computing: Dissertations, Theses, and Student Research

In this thesis, we present the design and implementation of a stand-alone tool for metabolic simulations. This system is able to integrate custom-built SBML models along with external user’s input information and produces the estimation of any reactants participating in the chain of the reactions in the provided model, e.g., ATP, Glucose, Insulin, for the given duration using numerical analysis and simulations. This tool offers the food intake arguments in the calculations to consider the personalized metabolic characteristics in the simulations. The tool has also been generalized to take into consideration of temporal genomic information and be flexible for simulation …

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.