Digital Commons Network^™

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 …

Systematic Comparison Of Cross-Lingual Projection Techniques For Low-Density Nlp Under Strict Resource Constraints, Joshua Waxman

Dissertations, Theses, and Capstone Projects

The field of low-density NLP is often approached from an engineering perspective, and evaluations are typically haphazard - considering different architectures, given different languages, and different available resources - without a systematic comparison. The resulting architectures are then tested on the unique corpus and language for which this approach has been designed. This makes it difficult to truly evaluate which approach is truly the "best," or which approaches are best for a given language.

In this dissertation, several state-of-the-art architectures and approaches to low-density language Part-Of-Speech Tagging are reimplemented; all of these techniques exploit a relationship between a high-density (HD) …

Text Extraction From Natural Scene: Methodology And Application, Chucai Yi

Dissertations, Theses, and Capstone Projects

With the popularity of the Internet and the smart mobile device, there is an increasing demand for the techniques and applications of image/video-based analytics and information retrieval. Most of these applications can benefit from text information extraction in natural scene. However, scene text extraction is a challenging problem to be solved, due to cluttered background of natural scene and multiple patterns of scene text itself. To solve these problems, this dissertation proposes a framework of scene text extraction.

Scene text extraction in our framework is divided into two components, detection and recognition. Scene text detection is to find out the …

Randomized Search Of Graphs In Log Space And Probabilistic Computation, Wen-Ju Cheng

Dissertations, Theses, and Capstone Projects

Reingold has shown that L = SL, that s-t connectivity in a poly-mixing digraph is complete for promise-RL, and that s-t connectivity for a poly-mixing out-regular digraph with known stationary distribution is in L. Several properties that bound the mixing times of random walks on digraphs have been identified, including the digraph conductance and the digraph spectral expansion. However, rapidly mixing digraphs can still have exponential cover time, thus it is important to specifically identify structural properties of digraphs that effect cover times. We examine the complexity of random walks on a basic parameterized family of unbalanced digraphs called Strong …

Self-Referentiality In Constructive Semantics Of Intuitionistic And Modal Logics, Junhua Yu

Dissertations, Theses, and Capstone Projects

This thesis explores self-referentiality in the framework of justification logic. In this framework initialed by Artemov, the language has formulas of the form t:F, which means "the term t is a justification of the formula F." Moreover, terms can occur inside formulas and hence it is legal to have t:F(t), which means "the term t is a justification of the formula F about t itself." Expressions like this is not only interesting in the semantics of justification logic, but also, as we will see, necessary in applications of justification logic in formalizing constructive contents implicitly carried by modal and intuitionistic …

Quantum Crystallography Of Hydronium Cations, Sonjae Sycoria Wallace

Dissertations, Theses, and Capstone Projects

Cationic hydronium clusters of the form [HaOb]^c,(c>0), have been investigated. After investigating over 2000 crystal structures containing hydronium cations found in the Cambridge Structural Database. The hydronium cationic compounds that were most unusual, mischaracterized, or those of apparent aggregates, were investigated further by geometry optimization and in some cases with the Quantum Theory of Atoms in Molecules (QTAIM). The results of our investigations yielded the first reports of stable conformations of cyclic dihydronium cationic clusters. In a second investigation we reported the first theoretically confirmed transition state of a H7O3+conformer captured within a crystal. A third product from our …

Canvas: A Fast And Accurate Geometric Sentence Alignment System Using Lexical Cues Within Complex Misalignment Settings, Hussein M. Ghaly

Dissertations, Theses, and Capstone Projects

In this paper, we present a new sentence alignment system (Canvas), which is a Python implementation of a geometric approach to sentence alignment, based on lexical cues. Canvas system is designed mainly to handle parallel texts exhibiting complex misalignment patterns, namely within English-Arabic pairs for United Nations documents. The system relies heavily on pre-indexing words/tokens in the source and target texts, and it creates correspondences between the token indexes. From this point onward, the alignment problem is reduced to a geometric problem of finding the path that runs through the True Correspondence Points (TCPs). The likelihood of a point being …

Temporal Information Extraction And Knowledge Base Population, Taylor Cassidy

Dissertations, Theses, and Capstone Projects

Temporal Information Extraction (TIE) from text plays an important role in many Natural Language Processing and Database applications. Many features of the world are time-dependent, and rich temporal knowledge is required for a more complete and precise understanding of the world. In this thesis we address aspects of two core tasks in TIE. First, we provide a new corpus of labeled temporal relations between events and temporal expressions, dense enough to facilitate a change in research directions from relation classification to identification, and present a system designed to address corresponding new challenges. Second, we implement a novel approach for the …

Echolocation: Using Word-Burst Analysis To Rescore Keyword Search Candidates In Low-Resource Languages, Justin Richards

Dissertations, Theses, and Capstone Projects

State of the art technologies for speech recognition are very accurate for heavily studied languages like English. They perform poorly, though, for languages wherein the recorded archives of speech data available to researchers are relatively scant. In the context of these low-resource languages, the task of keyword search within recorded speech is formidable. We demonstrate a method that generates more accurate keyword search results on low-resource languages by studying a pattern not exploited by the speech recognizer. The word-burst, or burstiness, pattern is the tendency for word utterances to appear together in bursts as conversational topics fluctuate. We give evidence …

Automated Classification Of Argument Stance In Student Essays: A Linguistically Motivated Approach With An Application For Supporting Argument Summarization, Adam Robert Faulkner

Dissertations, Theses, and Capstone Projects

This study describes a set of document- and sentence-level classification models designed to automate the task of determining the argument stance (for or against) of a student argumentative essay and the task of identifying any arguments in the essay that provide reasons in support of that stance. A suggested application utilizing these models is presented which involves the automated extraction of a single-sentence summary of an argumentative essay. This summary sentence indicates the overall argument stance of the essay from which the sentence was extracted and provides a representative argument in support of that stance.

A novel set …

The Lived Experience Of Young Adult Burn Survivors' Use Of Social Media, Marie S. Giordano

Dissertations, Theses, and Capstone Projects

The purpose of this phenomenological study was to illuminate the meaning of social media use by young adult burn survivors. Five females and four males, aged 20-25, who sustained burns > 25%, were interviewed. Van Manen's (1999) phenomenological methodology provided the framework for this study. The meaning of the context of the lived experience is described in the five essential themes of identity, connectivity, social support, making meaning, and privacy. These young adult burn survivors, having experienced the traumatic effects of a burn during adolescence, use social media as a way of expressing their identity, while being cautious about privacy. Part …

Bass In Your Face: A Case-Study Exploration Of Networked Culture, Samantha Phyllis Kretmar

Dissertations, Theses, and Capstone Projects

Using dubstep DJ Bassnectar as a case-study example, this thesis explores the impact of social networks and mobile connectivity. As evidenced by Bassnectar's digitally based approach to experiencing, distributing, and consuming music, these developments have contributed to the shift to a new model I describe as Networked Culture.

Figure 1 is a video highlighting the Bassnectar concert experience. Figure 2 is an audio clip illustrating the "drop" in dubstep. Figure 3 is another audio clip demonstrating the dubstep sound. Figure 4 is an image of an Ableton Live sound library. Figure 5 is an image of Ableton Live's functionality. Figure …

Phylogenetic Trees And Their Analysis, Eric Ford

Dissertations, Theses, and Capstone Projects

Determining the best possible evolutionary history, the lowest-cost phylogenetic tree, to fit a given set of taxa and character sequences using maximum parsimony is an active area of research due to its underlying importance in understanding biological processes. As several steps in this process are NP-Hard when using popular, biologically-motivated optimality criteria, significant amounts of resources are dedicated to both both heuristics and to making exact methods more computationally tractable. We examine both phylogenetic data and the structure of the search space in order to suggest methods to reduce the number of possible trees that must be examined to find …

Lean, Green, And Lifetime Maximizing Sensor Deployment On A Barrier, Peter Michael Terlecky

Dissertations, Theses, and Capstone Projects

Mobile sensors are located on a barrier represented by a line segment, and each sensor has a single energy source that can be used for both moving and sensing. Sensors may move once to their desired destinations and then coverage/communication is commenced. The sensors are collectively required to cover the barrier or in the communication scenario set up a chain of communication from endpoint to endpoint. A sensor consumes energy in movement in proportion to distance traveled, and it expends energy per time unit for sensing in direct proportion to its radius raised to a constant exponent.

The first focus …

Analysis Of Dna Motifs In The Human Genome, Yupu Liang

Dissertations, Theses, and Capstone Projects

DNA motifs include repeat elements, promoter elements and gene regulator elements, and play a critical role in the human genome. This thesis describes a genome-wide computational study on two groups of motifs: tandem repeats and core promoter elements.

Tandem repeats in DNA sequences are extremely relevant in biological phenomena and diagnostic tools. Computational programs that discover tandem repeats generate a huge volume of data, which can be difficult to decipher without further organization. A new method is presented here to organize and rank detected tandem repeats through clustering and classification. Our work presents multiple ways of expressing tandem repeats using …

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 …

Automated Learner Classification Through Interface Event Stream And Summary Statistics Analysis, Edgar E. Troudt

Dissertations, Theses, and Capstone Projects

Reading comprehension is predominately measured through multiple choice examinations. Yet, as we will discuss in this thesis, such exams are often criticized for their inaccuracies. With the advent of "big data" and the rise of ITS (Intelligent Tutoring Systems), increasing focus will be placed on finding dynamic, automated ways of measuring students' aptitude and progress.

This work takes the first step towards automated learner classification based on the application of graphic organizers. We address the following specific problem experimentally: How effectively can we measure task comprehension via human translation of written text into a visual representation on a computer? Can …

Data-Driven Synthesis Of Animations Of Spatially Inflected American Sign Language Verbs Using Human Data, Pengfei Lu

Dissertations, Theses, and Capstone Projects

Techniques for producing realistic and understandable animations of American Sign Language (ASL) have accessibility benefits for signers with lower levels of written language literacy. Previous research in sign language animation didn’t address the specific linguistic issue of space use and verb inflection, due to a lack of sufficiently detailed and linguistically annotated ASL corpora, which is necessary for modern data-driven approaches. In this dissertation, a high-quality ASL motion capture corpus with ASL-specific linguistic structures is collected, annotated, and evaluated using carefully designed protocols and well-calibrated motion capture equipment. In addition, ASL animations are modeled, synthesized, and evaluated based on samples …

A Parametrization-Based Surface Reconstruction System For Triangular Mesh Simplification With Application To Large Scale Scenes, Adriana Wise

Dissertations, Theses, and Capstone Projects

The laser scanner is nowadays widely used to capture the geometry of art, animation maquettes, or large architectural, industrial, and land form models. It thus poses specific problems depending on the model scale. This thesis provides a solution for simplification of triangulated data and for surface reconstruction of large data sets, where feature edges provide an obvious segmentation structure. It also explores a new method for model segmentation, with the goal of applying multiresolution techniques to data sets characterized by curvy areas and the lack of clear demarcation features. The preliminary stage of surface segmentation, which takes as input single …

Discovering Regularity In Point Clouds Of Urban Scenes, Sam Friedman

Dissertations, Theses, and Capstone Projects

Despite the apparent chaos of the urban environment, cities are actually replete with regularity. From the grid of streets laid out over the earth, to the lattice of windows thrown up into the sky, periodic regularity abounds in the urban scene. Just as salient, though less uniform, are the self-similar branching patterns of trees and vegetation that line streets and fill parks. We propose novel methods for discovering these regularities in 3D range scans acquired by a time-of-flight laser sensor. The applications of this regularity information are broad, and we present two original algorithms. The first exploits the efficiency of …