Computer Sciences Commons^™

The Computational Complexity Of Some Games And Puzzles With Theoretical Applications, Vasiliki Despoina Mitsou

Dissertations, Theses, and Capstone Projects

The subject of this thesis is the algorithmic properties of one- and two-player

games people enjoy playing, such as Sudoku or Chess. Questions asked about puzzles

and games in this context are of the following type: can we design efficient computer

programs that play optimally given any opponent (for a two-player game), or solve

any instance of the puzzle in question?

We examine four games and puzzles and show algorithmic as well as intractability

results. First, we study the wolf-goat-cabbage puzzle, where a man wants to transport

a wolf, a goat, and a cabbage across a river by using a …

Comparison Of Sequence Alignment Algorithms, Tejas Gandhi

Journal of Undergraduate Research at Minnesota State University, Mankato

The fact that biological sequences can be represented as strings belonging to a finite alphabet (A, C, G, and T for DNA) plays an important role in connecting biology to computer science. String representation allows researchers to apply various string comparison techniques available in computer science. As a result, various applications have been developed that facilitate the task of sequence alignment. The problem of finding sequence alignments consists of finding the best match between two biological sequences. A best match can infer an evolutionary relationship and functional similarity. However, there is a lack of research on how reliable and efficient …

Improved Storm Data Processing Through Parallel Computing Approaches, Shauna Smith

Journal of Undergraduate Research at Minnesota State University, Mankato

A previous research study conducted at Michigan Technological University by Dr. Deborah Nykanen and her colleague Dr. Daniel Harris analyzed storm data in order to develop algorithms that will allow coarse resolution rainfall forecasted by weather models to be optimally used in high resolution hydrology models with the goal of improving stream flow predictions and early detection algorithms that can be used to warn communities about potential flash floods. This research was performed by analyzing a series of independent radar images derived from Weather Surveillance Radar-1988 Doppler (WSR-88D) data obtained from Dr. James A. Smith at Princeton University using a …

Verification Of Costless Merge Pairing Heaps, Joshua Vander Hook

Journal of Undergraduate Research at Minnesota State University, Mankato

Most algorithms’ performance is limited by the data structures they use. Internal algorithms then decide the performance of the data structure. This cycle continues until fundamental results, verified by analysis and experiment, prevent further improvement. In this paper I examine one specific example of this. The focus of this work is primarily on a new variant of the pairing heap. I will review the new implementation, compare its theoretical performance, and discuss my original contribution: the first preliminary data on its experimental performance. It is instructive to provide some background information, followed by a formal definition of heaps in 1.1. …

Placing Videos On A Semantic Hierarchy For Search Result Navigation, Song Tan, Yu-Gang Jiang, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

Organizing video search results in a list view is widely adopted by current commercial search engines, which cannot support efficient browsing for complex search topics that have multiple semantic facets. In this article, we propose to organize video search results in a highly structured way. Specifically, videos are placed on a semantic hierarchy that accurately organizes various facets of a given search topic. To pick the most suitable videos for each node of the hierarchy, we define and utilize three important criteria: relevance, uniqueness, and diversity. Extensive evaluations on a large YouTube video dataset demonstrate the effectiveness of our approach.

Global Immutable Region Computation, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Research Collection School Of Computing and Information Systems

A top-k query shortlists the k records in a dataset that best match the user's preferences. To indicate her preferences, the user typically determines a numeric weight for each data dimension (i.e., attribute). We refer to these weights collectively as the query vector. Based on this vector, each data record is implicitly mapped to a score value (via a weighted sum function). The records with the k largest scores are reported as the result. In this paper we propose an auxiliary feature to standard top-k query processing. Specifically, we compute the maximal locus within which the query vector incurs no …

Decaf: A New Event Detection Logic For The Purpose Of Fusing Delineated-Continuous Spatial Information, Kerry Q. Hart

School of Computing: Dissertations, Theses, and Student Research

Geospatial information fusion is the process of synthesizing information from complementary data sources located at different points in space and time. Spatial phenomena are often measured at discrete locations by sensor networks, technicians, and volunteers; yet decisions often require information about locations where direct measurements do not exist. Traditional methods assume the spatial phenomena to be either discrete or continuous, an assumption that underlies and informs all subsequent analysis. Yet certain phenomena defy this dichotomy, alternating as they move across spatial and temporal scales. Precipitation, for example, appears continuous at large scales, but it can be temporally decomposed into discrete …

On Finding The Point Where There Is No Return: Turning Point Mining On Game Data, Wei Gong, Ee Peng Lim, Feida Zhu, Achananuparp Palakorn, David Lo

Research Collection School Of Computing and Information Systems

Gaming expertise is usually accumulated through playing or watching many game instances, and identifying critical moments in these game instances called turning points. Turning point rules (shorten as TPRs) are game patterns that almost always lead to some irreversible outcomes. In this paper, we formulate the notion of irreversible outcome property which can be combined with pattern mining so as to automatically extract TPRs from any given game datasets. We specifically extend the well-known PrefixSpan sequence mining algorithm by incorporating the irreversible outcome property. To show the usefulness of TPRs, we apply them to Tetris, a popular game. We mine …

A Hamming Embedding Kernel With Informative Bag-Of-Visual Words For Video Semantic Indexing, Feng Wang, Wen-Lei Zhao, Chong-Wah Ngo, Bernard Merialdo

Research Collection School Of Computing and Information Systems

In this article, we propose a novel Hamming embedding kernel with informative bag-of-visual words to address two main problems existing in traditional BoW approaches for video semantic indexing. First, Hamming embedding is employed to alleviate the information loss caused by SIFT quantization. The Hamming distances between keypoints in the same cell are calculated and integrated into the SVM kernel to better discriminate different image samples. Second, to highlight the concept-specific visual information, we propose to weight the visual words according to their informativeness for detecting specific concepts. We show that our proposed kernels can significantly improve the performance of concept …

Algorithmic Accountability, Tamara Kneese

Media Studies

Accountability is fundamentally about checks and balances to power. In theory, both government and corporations are kept accountable through social, economic, and political mechanisms. Journalism and public advocates serve as an additional tool to hold powerful institutions and individuals accountable. But in a world of data and algorithms, accountability is often murky. Beyond questions about whether the market is sufficient or governmental regulation is necessary, how should algorithms be held accountable? For example what is the role of the fourth estate in holding data-oriented practices accountable?

L-Opacity: Linkage-Aware Graph Anonymization, Sadegh Nobari, Panagiotis Karras, Hwee Hwa Pang, Stephane Bressan

Research Collection School Of Computing and Information Systems

The wealth of information contained in online social networks has created a demand for the publication of such data as graphs. Yet, publication, even after identities have been removed, poses a privacy threat. Past research has suggested ways to publish graph data in a way that prevents the re-identification of nodes. However, even when identities are effectively hidden, an adversary may still be able to infer linkage between individuals with sufficiently high confidence. In this paper, we focus on the privacy threat arising from such link disclosure. We suggest L-opacity, a sufficiently strong privacy model that aims to control an …

Scheduling And Resource Allocation In Wireless Sensor Networks, Yosef Alayev

Dissertations, Theses, and Capstone Projects

In computer science and telecommunications, wireless sensor networks are an active research area. Each sensor in a wireless sensor network has some pre-defined or on demand tasks such as collecting or disseminating data. Network resources, such as broadcast channels, number of sensors, power, battery life, etc., are limited. Hence, a schedule is required to optimally allocate network resources so as to maximize some profit or minimize some cost. This thesis focuses on scheduling problems in the wireless sensor networks environment. In particular, we study three scheduling problems in the wireless sensor networks: broadcast scheduling, sensor scheduling for area monitoring, and …

Data Mining Based Hybridization Of Meta-Raps, Fatemah Al-Duoli, Ghaith Rabadi

Engineering Management & Systems Engineering Faculty Publications

Though metaheuristics have been frequently employed to improve the performance of data mining algorithms, the opposite is not true. This paper discusses the process of employing a data mining algorithm to improve the performance of a metaheuristic algorithm. The targeted algorithms to be hybridized are the Meta-heuristic for Randomized Priority Search (Meta-RaPS) and an algorithm used to create an Inductive Decision Tree. This hybridization focuses on using a decision tree to perform on-line tuning of the parameters in Meta-RaPS. The process makes use of the information collected during the iterative construction and improvement phases Meta-RaPS performs. The data mining algorithm …

Algorithms And Tools For Computational Analysis Of Human Transcriptome Using Rna-Seq, Nan Deng

Wayne State University Dissertations

Alternative splicing plays a key role in regulating gene expression, and more than 90% of human genes are alternatively spliced through different types of alternative splicing. Dysregulated alternative splicing events have been linked to a number of human diseases. Recently, high-throughput RNA-Seq technologies have provided unprecedented opportunities to better characterize and understand transcriptomes, in particular useful for the detection of splicing variants between healthy and diseased human transcriptomes.

We have developed two novel algorithms and tools and a computational workflow to interrogate human transcriptomes between healthy and diseased conditions. The first is a read count-based Expectation-Maximization (EM) algorithm and tool, …

Colormoo: An Algorithmic Approach To Generating Color Palettes, Joshua Rael

CMC Senior Theses

Selecting one color can be done with relative ease, but this task becomes more difficult with each subsequent color. Colormoo is an online tool aimed at solving this problem. We implement three algorithms for generating color palettes based off of a starting color. Data is collected for each palette that is generated. Our analysis reveals two of the algorithms are preferred, but under different circumstances. Furthermore, we find that users prefer palettes containing colors that are compatible, but not too similar. With refined heuristics, we believe these techniques can be extended and applied beyond the field of graphic design alone.

Using Micro-Reviews To Select An Efficient Set Of Reviews, Thanh-Son Nguyen, Hady W. Lauw, Panayiotis Tsaparas

Research Collection School Of Computing and Information Systems

Online reviews are an invaluable resource for web users trying to make decisions regarding products or services. However, the abundance of review content, as well as the unstructured, lengthy, and verbose nature of reviews make it hard for users to locate the appropriate reviews, and distill the useful information. With the recent growth of social networking and micro-blogging services, we observe the emergence of a new type of online review content, consisting of bite-sized, 140 character-long reviews often posted reactively on the spot via mobile devices. These micro-reviews are short, concise, and focused, nicely complementing the lengthy, elaborate, and verbose …

Approximation Algorithms For Factory Optimization In Parallel Manufacturing, David West, Dr. Sean Warnick

Journal of Undergraduate Research

Many industrial companies, especially ones that produce chemicals, use a batch manufacturing process to make their product. In a batch manufacturing process, a sequence of machines take “batches” of material and progressively perform actions until the final product is produced. One goal of managers of these companies is to schedule these batches on the machines such that the production line is most efficiently utilized. To solve for this exactly is computationally hard in the average case. My project was to formulate a new mathematical model that would allow for computationally tractable optimizations to this problem.

Computing The Grounded Semantics In All The Subgraphs Of An Argumentation Framework: An Empirical Evaluation, Pierpaolo Dondio

Articles

Given an argumentation framework – with a finite set of arguments and the attack relation identifying the graph – we study how the grounded labelling of a generic argument a varies in all the subgraphs of . Since this is an intractable problem of above-polynomial complexity, we present two non-naïve algorithms to find the set of all the subgraphs where the grounded semantic assigns to argument a specific label . We report the results of a series of empirical tests over graphs of increasing complexity. The value of researching the above problem is two-fold. First, knowing how an argument behaves …

Algorithms In Abstract Dna Self Assembly, Xingsi Zhong

Theses and Dissertations - UTB/UTPA

For the past two years, I have always been working on the topic of Abstract DNA Tiles Self-Assembly. This is a very new area, driven by the interest of DNA molecules. The feature that the system composed by DNA molecules can be a highly parallelized system, make it much more powerful when comparing with the traditional methods. This thesis will introduce the concept of abstract DNA self-assembly models as well as some interesting problems and their solutions.

Stability Aware Delaunay Refinement, Bishal Acharya

UNLV Theses, Dissertations, Professional Papers, and Capstones

Good quality meshes are extensively used for finding approximate solutions for partial differential equations for fluid flow in two dimensional surfaces. We present an overview of existing algorithms for refinement and generation of triangular meshes. We introduce the concept of node stability in the refinement of Delaunay triangulation. We present two algorithms for generating stable refinement of Delaunay triangulation. We also present an experimental investigation of a triangulation refinement algorithm based on the location of the center of gravity and the location of the center of circumcircle. The results show that the center of gravity based refinement is more effective …

3d Virtual Worlds And The Metaverse: Current Status And Future Possibilities, John David N. Dionisio, William G. Burns Iii, Richard Gilbert

Computer Science Faculty Works

Moving from a set of independent virtual worlds to an integrated network of 3D virtual worlds or Metaverse rests on progress in four areas: immersive realism, ubiquity of access and identity, interoperability, and scalability. For each area, the current status and needed developments in order to achieve a functional Metaverse are described. Factors that support the formation of a viable Metaverse, such as institutional and popular interest and ongoing improvements in hardware performance, and factors that constrain the achievement of this goal, including limits in computational methods and unrealized collaboration among virtual world stakeholders and developers, are also considered.

Spring­11: Pdc In Cs1/2 And A Mobile/Cloud Intermediate Mobile/Cloud Intermediate Software Design Course, Joseph P. Kaylor, Konstantin Läufer, Chandra N. Sekharan, George K. Thiruvathukal

Computer Science: Faculty Publications and Other Works

Recent changes in the environment of Loyola University Chicago’s Department of Computer Science include a better differentiation of our four undergraduate majors, growing interest in computing among science majors, and an increased demand for graduates with mobile and cloud skills. In our continued effort to incorporate parallel and distributed computing topics into the undergraduate curriculum, we are focusing on these three existing courses:

CS1: In response to a request from the physics department, we started to offer a CS1 section aimed at majors in physics and other hard sciences this spring semester. This section includes some material on numerical methods …

Novel Algorithms And Software For Biological Sequence Analysis, William Casey Bullock

Boise State University Theses and Dissertations

Bioinformatics is a broad realm of research in which Computer Science has much to offer. Collecting, sorting, and analyzing statistical information for DNA and protein sequences is difficult due to the sheer amount of available data. Tools have been created to do this, but they have generally been limited by speed or robustness.

In addition to analyzing the statistical properties of biological sequences, it is also important to model and understand their chemical and physical properties. A number of valuable software tools are available for modeling and predicting the properties of biological sequences in Computational Chemistry, including molecular docking, and …

Tesla: An Energy-Saving Agent That Leverages Schedule Flexibility, Jun Young Kwak, Pradeep Varakantham, Rajiv Maheswaran, Burcin Becerik-Gerber, Milind Tambe

Research Collection School Of Computing and Information Systems

This innovative application paper presents TESLA, an agent-based application for optimizing the energy use in commercial buildings. TESLA’s key insight is that adding flexibility to event/meeting schedules can lead to significant energy savings. TESLA provides three key contributions: (i) three online scheduling algorithms that consider flexibility of people’s preferences for energyefficient scheduling of incrementally/dynamically arriving meetings and events; (ii) an algorithm to effectively identify key meetings that lead to significant energy savings by adjusting their flexibility; and (iii) surveys of real users that indicate that TESLA’s assumptions exist in practice. TESLA was evaluated on data of over 110,000 meetings held …

Direct Eit Reconstructions Of Complex Admittivities On A Chest-Shaped Domain In 2-D, Sarah J. Hamilton, Jennifer L. Mueller

Mathematics, Statistics and Computer Science Faculty Research and Publications

Electrical impedance tomography (EIT) is a medical imaging technique in which current is applied on electrodes on the surface of the body, the resulting voltage is measured, and an inverse problem is solved to recover the conductivity and/or permittivity in the interior. Images are then formed from the reconstructed conductivity and permittivity distributions. In the 2-D geometry, EIT is clinically useful for chest imaging. In this work, an implementation of a D-bar method for complex admittivities on a general 2-D domain is presented. In particular, reconstructions are computed on a chest-shaped domain for several realistic phantoms including a simulated pneumothorax, …

Roundtriprank: Graph-Based Proximity With Importance And Specificity, Yuan Fang, Kevin Chen-Chuan Chang, Hady W. Lauw

Research Collection School Of Computing and Information Systems

Graph-based proximity has many applications with different ranking needs. However, most previous works only stress the sense of importance by finding "popular” results for a query. Often times important results are overly general without being well-tailored to the query, lacking a sense of specificity— which only emerges recently. Even then, the two senses are treated independently, and only combined empirically. In this paper, we generalize the well-studied importance-based random walk into a round trip and develop RoundTripRank, seamlessly integrating specificity and importance in one coherent process. We also recognize the need for a flexible trade-off between the two senses, and …

Security Games With Interval Uncertainty, Christopher Kiekintveld, Towhidul Islam, Vladik Kreinovich

Departmental Technical Reports (CS)

Security games provide a framework for allocating limited security resources in adversarial domains, and are currently used in applications including security at the LAX airport, scheduling for the Federal Air Marshals, and patrolling strategies for the U.S. Coast Guard. One of the major challenges in security games is finding solutions that are robust to uncertainty about the game model. Bayesian game models have been developed to model uncertainty, but algorithms for these games do not scale well enough for many applications, and the problem is NP-hard.

We take an alternative approach based on using intervals to model uncertainty in security …

Modeling And Verifying Hierarchical Real-Time Systems Using Stateful Timed Csp, Jun Sun, Yang Liu, Jin Song Dong, Yan Liu, Ling Shi, Étienne André

Research Collection School Of Computing and Information Systems

Modeling and verifying complex real-time systems are challenging research problems. The de facto approach is based on Timed Automata, which are finite state automata equipped with clock variables. Timed Automata are deficient in modeling hierarchical complex systems. In this work, we propose a language called Stateful Timed CSP and an automated approach for verifying Stateful Timed CSP models. Stateful Timed CSP is based on Timed CSP and is capable of specifying hierarchical real-time systems. Through dynamic zone abstraction, finite-state zone graphs can be generated automatically from Stateful Timed CSP models, which are subject to model checking. Like Timed Automata, Stateful …

Exploratory Coverage In Limited Mobility Sensor Networks, Mark Snyder, Sriram Chellappan, Mayur Thakur

Computer Science Faculty Research & Creative Works

Autonomous drones are employed with ever-increasing frequency in applications ranging from search and rescue, detection of forest fires, and battlefield/civilian surveillance. In this paper, we study the effects of limited mobility in such mobile sensor platforms, from the perspective of the effect limited mobility has on coverage effectiveness. We define a problem that we call Exploratory Coverage in Limited Mobility Sensor Networks, wherein the objective is to move a number of mobile sensors to fully explore (and hence, sense every point in) a target area in order to detect any critical event that has already occurred in the area. Further, …

Computational Methods For Comparative Non-Coding Rna Analysis: From Structural Motif Identification To Genome-Wide Functional Classification, Cuncong Zhong

Electronic Theses and Dissertations

Recent advances in biological research point out that many ribonucleic acids (RNAs) are transcribed from the genome to perform a variety of cellular functions, rather than merely acting as information carriers for protein synthesis. These RNAs are usually referred to as the non-coding RNAs (ncRNAs). The versatile regulation mechanisms and functionalities of the ncRNAs contribute to the amazing complexity of the biological system. The ncRNAs perform their biological functions by folding into specific structures. In this case, the comparative study of the ncRNA structures is key to the inference of their molecular and cellular functions. We are especially interested in …