Open Access. Powered by Scholars. Published by Universities.®

Theory and Algorithms Commons™

Open Access. Powered by Scholars. Published by Universities.®

2012

Discipline
Institution
Keyword
Publication
Publication Type
File Type

Articles 1 - 30 of 90

Full-Text Articles in Theory and Algorithms

Connotational Subtyping And Runtime Class Mutability In Ruby, Ian S. Dillon Dec 2012

Connotational Subtyping And Runtime Class Mutability In Ruby, Ian S. Dillon

Electronic Theses and Dissertations

Connotational subtyping is an approach to typing that allows an object's type to change dynamically, following changes to the object's internal state. This allows for a more precise representation of a problem domain with logical objects that have variable behavior. Two approaches to supporting connotational subtyping in the Ruby programming language were implemented: a language-level implementation using pure Ruby and a modification to the Ruby 1.8.7 interpreter. While neither implementation was wholly successful the language level implementation created complications with reflective language features like self and super and, while Ruby 1.8.7 has been obsoleted by Ruby 1.9 (YARV), the results …

Go to article

Application Of Digital Forensic Science To Electronic Discovery In Civil Litigation, Brian Roux Dec 2012

Application Of Digital Forensic Science To Electronic Discovery In Civil Litigation, Brian Roux

University of New Orleans Theses and Dissertations

Following changes to the Federal Rules of Civil Procedure in 2006 dealing with the role of Electronically Stored Information, digital forensics is becoming necessary to the discovery process in civil litigation. The development of case law interpreting the rule changes since their enactment defines how digital forensics can be applied to the discovery process, the scope of discovery, and the duties imposed on parties. Herein, pertinent cases are examined to determine what trends exist and how they effect the field. These observations buttress case studies involving discovery failures in large corporate contexts along with insights on the technical reasons those …

Go to article

Hardware-Software Co-Design, Acceleration And Prototyping Of Control Algorithms On Reconfigurable Platforms, Desta Kumsa Edosa Dec 2012

Hardware-Software Co-Design, Acceleration And Prototyping Of Control Algorithms On Reconfigurable Platforms, Desta Kumsa Edosa

UNLV Theses, Dissertations, Professional Papers, and Capstones

Differential equations play a significant role in many disciplines of science and engineering. Solving and implementing Ordinary Differential Equations (ODEs) and partial Differential Equations (PDEs) effectively are very essential as most complex dynamic systems are modeled based on these equations. High Performance Computing (HPC) methodologies are required to compute and implement complex and data intensive applications modeled by differential equations at higher speed. There are, however, some challenges and limitations in implementing dynamic system, modeled by non-linear ordinary differential equations, on digital hardware. Modeling an integrator involves data approximation which results in accuracy error if data values are not considered …

Go to article

Contour Extraction Of Drosophila Embryos Using Active Contours In Scale Space, Soujanya Siddavaram Ananta Dec 2012

Contour Extraction Of Drosophila Embryos Using Active Contours In Scale Space, Soujanya Siddavaram Ananta

Masters Theses & Specialist Projects

Contour extraction of Drosophila embryos is an important step to build a computational system for pattern matching of embryonic images which aids in the discovery of genes. Automatic contour extraction of embryos is challenging due to several image variations such as size, shape, orientation and neigh- boring embryos such as touching and non-touching embryos. In this thesis, we introduce a framework for contour extraction based on the connected components in the gaussian scale space of an embryonic image. The active contour model is applied on the images to refine embryo contours. Data cleaning methods are applied to smooth the jaggy …

Go to article

Snap-And-Ask: Answering Multimodal Question By Naming Visual Instance, Wei Zhang, Lei Pang, Chong-Wah Ngo Nov 2012

Snap-And-Ask: Answering Multimodal Question By Naming Visual Instance, Wei Zhang, Lei Pang, Chong-Wah Ngo

Research Collection School Of Computing and Information Systems

In real-life, it is easier to provide a visual cue when asking a question about a possibly unfamiliar topic, for example, asking the question, “Where was this crop circle found?”. Providing an image of the instance is far more convenient than texting a verbose description of the visual properties, especially when the name of the query instance is not known. Nevertheless, having to identify the visual instance before processing the question and eventually returning the answer makes multimodal question-answering technically challenging. This paper addresses the problem of visual-totext naming through the paradigm of answering-by-search in a two-stage computational framework, which …

Go to article

Microblog Search And Filtering With Time Sensitive Feedback And Thresholding Based On Bm25, Wei Gao, Zhongyu Wei, Kam-Fai Wong Nov 2012

Microblog Search And Filtering With Time Sensitive Feedback And Thresholding Based On Bm25, Wei Gao, Zhongyu Wei, Kam-Fai Wong

Research Collection School Of Computing and Information Systems

Microblogs such as Twitter are considered faster first-hand sources of information with many real-time fashions. We report our work in the real-time adhoc search and filtering tasks of TREC 2012 microblog track. Our system is built based on the traditional BM25 relevance model, in which specific techniques are tried out to respond to the ne.ed of frnding relevant tweets, ln thc real-time adhoc task, we applied a peak detection algorithm for the process of blind feedback, We also tried to automatically combine the search results of multiple retrieval techniques. In the real-time filtering pilot task, we examine the effectiveness of …

Go to article

Retrieval Of Sub-Pixel-Based Fire Intensity And Its Application For Characterizing Smoke Injection Heights And Fire Weather In North America, David Peterson Sep 2012

Retrieval Of Sub-Pixel-Based Fire Intensity And Its Application For Characterizing Smoke Injection Heights And Fire Weather In North America, David Peterson

Department of Earth and Atmospheric Sciences: Dissertations, Theses, and Student Research

For over two decades, satellite sensors have provided the locations of global fire activity with ever-increasing accuracy. However, the ability to measure fire intensity, know as fire radiative power (FRP), and its potential relationships to meteorology and smoke plume injection heights, are currently limited by the pixel resolution. This dissertation describes the development of a new, sub-pixel-based FRP calculation (FRPf) for fire pixels detected by the MODerate Resolution Imaging Spectroradiometer (MODIS) fire detection algorithm (Collection 5), which is subsequently applied to several large wildfire events in North America. The methodology inherits an earlier bi-spectral algorithm for retrieving sub-pixel …

Go to article

Verifying Total Correctness Of Graph Programs, Christopher M. Poskitt, Detlef Plump Sep 2012

Verifying Total Correctness Of Graph Programs, Christopher M. Poskitt, Detlef Plump

Research Collection School Of Computing and Information Systems

GP 2 is an experimental nondeterministic programming language based on graph transformation rules, allowing for visual programming and the solving of graph problems at a high-level of abstraction. In previous work we demonstrated how to verify graph programs using a Hoare-style proof calculus, but only partial correctness was considered. In this paper, we add new proof rules and termination functions, which allow for proofs to additionally guarantee that program executions always terminate (weak total correctness), or that programs always terminate and do so without failure (total correctness). We show that the new proof rules are sound with respect to the …

Go to article

Verification Of Graph Programs, Christopher M. Poskitt Sep 2012

Verification Of Graph Programs, Christopher M. Poskitt

Research Collection School Of Computing and Information Systems

GP (for Graph Programs) is an experimental nondeterministic programming language which allows for the manipulation of graphs at a high level of abstraction. The program states of GP are directed labelled graphs. These are manipulated directly via the application of (conditional) rule schemata, which generalise double-pushout rules with expressions over labels and relabelling. In contrast with graph grammars, the application of these rule schemata is directed by a number of simple control constructs including sequential composition, conditionals, and as-long-as-possible iteration. GP shields programmers at all times from low-level implementation issues (e.g. graph representation), and with its nondeterministic semantics, allows one …

Go to article

Theoretical Approaches To The Characterization Of Water, Aqueous Interfaces, And Improved Sampling Of Protein Conformational Changes, Alexis J. Lee Aug 2012

Theoretical Approaches To The Characterization Of Water, Aqueous Interfaces, And Improved Sampling Of Protein Conformational Changes, Alexis J. Lee

University of New Orleans Theses and Dissertations

Methods to advance the understanding of water and other aqueous systems are devel- oped. This work falls into three areas: The creation of better interaction potentials for water, improved methods for sampling configurational space, and the applications of these methods to understand systems of interest. Charge transfer has been shown by ab initio methods to be important in the water–water and water–ion interactions. A model for treating charge transfer in liquid water and aqueous systems is presented in this manuscript. The model is called Discrete Charge Transfer (DCT) and is based on the commonly-used TIP4P/2005 model, which represents the charge …

Go to article

Sketchmate: A Computer-Aided Sketching And Simulation Tool For Teaching Graph Algorithms, Kristy Sue Van Hornweder Aug 2012

Sketchmate: A Computer-Aided Sketching And Simulation Tool For Teaching Graph Algorithms, Kristy Sue Van Hornweder

Doctoral Dissertations

In this dissertation, we developed and tested a sketching, visualization, and simulation tool called Sketchmate for demonstrating graph algorithms commonly taught in undergraduate computer science courses. For this research, we chose to focus on shortest path and network flow algorithms. Two versions of this tool have been implemented: 1) an instructor tool that supports computer-aided manual simulations of algorithms that augment traditional whiteboard presentations, allowing lectures to be more dynamic and interactive, and 2) a student tool that supports computer-aided manual practice of algorithms that enables students to work through homework problems more quickly while providing detailed incremental feedback about …

Go to article

Degree Constrained Triangulation, Roshan Gyawali Aug 2012

Degree Constrained Triangulation, Roshan Gyawali

UNLV Theses, Dissertations, Professional Papers, and Capstones

Triangulation of simple polygons or sets of points in two dimensions is a widely investigated problem in computational geometry. Some researchers have considered variations of triangulation problems that include minimum weight triangulation, de-launay triangulation and triangulation refinement. In this thesis we consider a constrained version of the triangulation problem that asks for triangulating a given domain (polygon or point sites) so that the resulting triangulation has an increased number of even degree vertices. This problem is called Degree Constrained Triangulation (DCT). We propose four algorithms to solve DCT problems. We also present experimental results based on the implementation of the …

Go to article

Measurement-Driven Performance Analysis Of Indoor Femtocellular Networks, Trung-Tuan Luong, Vigneshwaran Subbaraju, Archan Misra, Srinivasan Seshan Aug 2012

Measurement-Driven Performance Analysis Of Indoor Femtocellular Networks, Trung-Tuan Luong, Vigneshwaran Subbaraju, Archan Misra, Srinivasan Seshan

Research Collection School Of Computing and Information Systems

This paper describes initial empirical studies, performed on a 6-node 3G indoor femtocellular testbed, that investigate the impact of pedestrian mobility on network parameters, such as handoff behavior and data throughput. The studies establish that, owing to the small radii of cells, even modest changes in movement speed can have disproportionately large impact on handoff patterns and network throughput. By also revealing a strong temporal dependency effect, the studies motivate the need for algorithms to accurately predict RF signal strength distributions in dynamic indoor environments. We present such an RF prediction algorithm, based on crowd-sourced signal strength readings, and show …

Go to article

Message Passing Algorithm For Different Problems Sum, Mean, Guide And Sorting In A Rooted Tree Network., Sabaresh Nageswara Rao Maddula Aug 2012

Message Passing Algorithm For Different Problems Sum, Mean, Guide And Sorting In A Rooted Tree Network., Sabaresh Nageswara Rao Maddula

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis, we give message passing algorithms in distributed environment for five different problems of a rooted tree having n nodes. In the first algorithm, every node has a value; the root calculates the sum of those values, and sends it to all the nodes in the network. In the second algorithm, the root computes the value of mean of values of all the nodes, and sends it to all nodes of the network. The third algorithm calculates the guide pairs. Guide pair of a node x is an ordered pair (pre_index(x), post_index(x)), where pre_index(x) and post_index(x) are the …

Go to article

Identifying High-Dimension Subspace Subcodes Of Reed-Solomon Codes, Sarah Adams Jul 2012

Identifying High-Dimension Subspace Subcodes Of Reed-Solomon Codes, Sarah Adams

Sarah Spence Adams

Subspace subcodes of Reed-Solomon (SSRS) codes were introduced by Hattori, McEliece, Solomo, and Lin in the mid-1990s. These authors found a complicated dimension formula and a simple, tight lower bound on thedimension of SSRS codes over F2m. We prove a conjecture of Hattori concerning how to identify subspaces that can be used to build SSRS codes whose dimension exceeds this lower bound.

Go to article

The Minimum Decoding Delay Of Maximum Rate Complex Orthogonal Space–Time Block Codes, Sarah Adams, Nathaniel Karst, Jonathan Pollack Jul 2012

The Minimum Decoding Delay Of Maximum Rate Complex Orthogonal Space–Time Block Codes, Sarah Adams, Nathaniel Karst, Jonathan Pollack

Sarah Spence Adams

The growing demand for efficient wireless transmissions over fading channels motivated the development ofspace-time block codes. Space-time block codes built from generalized complex orthogonal designs are particularly attractive because the orthogonality permits a simple decoupled maximum-likelihood decodingalgorithm while achieving full transmit diversity. The two main research problems for these complex orthogonalspace-time block codes (COSTBCs) have been to determine for any number of antennas the maximum rate andthe minimum decoding delay for a maximum rate code. The maximum rate for COSTBCs was determined by Liang in 2003. This paper addresses the second fundamental problem by providing a tight lower bound on …

Go to article

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang Jul 2012

Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …

Go to article

On The Issue Of Decoupled Decoding Of Codes Derived From Quaternion Orthogonal Designs, Tadeusz Wysocki, Beata Wysocki, Sarah Spence Adams Jul 2012

On The Issue Of Decoupled Decoding Of Codes Derived From Quaternion Orthogonal Designs, Tadeusz Wysocki, Beata Wysocki, Sarah Spence Adams

Sarah Spence Adams

Quaternion orthogonal designs (QODs) have been previously introduced as a basis for orthogonal space-time polarization block codes (OSTPBCs). This note will serve to correct statements concerning the optimality of a decoupled maximum-likelihood (ML) decoding algorithm. It will be shown that when compared to coupled decoding, the decoupled decoding is only optimal in certain cases. This raises several open problems concerning the decoding of OSTPBCs.

Go to article

A Parameterized Stereo Vision Core For Fpgas, Mark Chang, Stephen Longfield Jul 2012

A Parameterized Stereo Vision Core For Fpgas, Mark Chang, Stephen Longfield

Mark L. Chang

We present a parameterized stereo vision core suitable for a wide range of FPGA targets and stereo vision applications. By enabling easy tuning of algorithm parameters, our system allows for rapid exploration of the design space and simpler implementation of high-performance stereo vision systems. This implementation utilizes the census transform algorithm to calculate depth information from a pair of images delivered from a simulated stereo camera pair. This work advances our previous work through implementation improvements, a stereo camera pair simulation framework, and a scalable stereo vision core.

Go to article

Precis: A Design-Time Precision Analysis Tool, Mark L. Chang, Scott Hauck Jul 2012

Precis: A Design-Time Precision Analysis Tool, Mark L. Chang, Scott Hauck

Mark L. Chang

Currently, few tools exist to aid the FPGA developer in translating an algorithm designed for a general-purpose-processor into one that is precision-optimized for FPGAs. This task requires extensive knowledge of both the algorithm and the target hardware. We present a design-time tool, Precis, which assists the developer in analyzing the precision requirements of algorithms specified in MATLAB. Through the combined use of simulation, user input, and program analysis, we demonstrate a methodology for precision analysis that can aid the developer in focusing their manual precision optimization efforts.

Go to article

Precis: A Usercentric Word-Length Optimization Tool, Mark Chang, Scott Hauck Jul 2012

Precis: A Usercentric Word-Length Optimization Tool, Mark Chang, Scott Hauck

Mark L. Chang

Translating an algorithm designed for a general-purpose processor into an algorithm optimized for custom logic requires extensive knowledge of the algorithm and the target hardware. Precis lets designers analyze the precision requirements of algorithms specified in Matlab. The design time tool combines simulation, user input, and program analysis to help designers focus their manual precision optimization efforts.

Go to article

Low-Cost Stereo Vision On An Fpga, Chris A. Murphy, Daniel Lindquist, Ann Marie Rynning, Thomas Cecil, Sarah Leavitt, Mark L. Chang Jul 2012

Low-Cost Stereo Vision On An Fpga, Chris A. Murphy, Daniel Lindquist, Ann Marie Rynning, Thomas Cecil, Sarah Leavitt, Mark L. Chang

Mark L. Chang

We present a low-cost stereo vision implementation suitable for use in autonomous vehicle applications and designed with agricultural applications in mind. This implementation utilizes the Census transform algorithm to calculate depth maps from a stereo pair of automotive-grade CMOS cameras. The final prototype utilizes commodity hardware, including a Xilinx Spartan-3 FPGA, to process 320times240 pixel images at greater than 150 frames per second and deliver them via a USB 2.0 interface.

Go to article

Interactionless Calendar-Based Training For 802.11 Localization, Mark Chang, Andrew J. Barry, Noah L. Tye Jul 2012

Interactionless Calendar-Based Training For 802.11 Localization, Mark Chang, Andrew J. Barry, Noah L. Tye

Mark L. Chang

This paper presents our work in solving one of the weakest links in 802.11-based indoor-localization: the training of ground-truth received signal strength data. While crowdsourcing this information has been demonstrated to be a viable alternative to the time consuming and accuracy-limited process of manual training, one of the chief drawbacks is the rate at which a system can be trained. We demonstrate an approach that utilizes users' calendar and appointment information to perform interactionless training of an 802.11-based indoor localization system. Our system automatically determines if a user attended a calendar event, resulting in accuracy comparable to our previously published …

Go to article

On-Line Portfolio Selection With Moving Average Reversion, Bin Li, Steven C. H. Hoi Jul 2012

On-Line Portfolio Selection With Moving Average Reversion, Bin Li, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

On-line portfolio selection has attracted increasing interests in machine learning and AI communities recently. Empirical evidences show that stock's high and low prices are temporary and stock price relatives are likely to follow the mean reversion phenomenon. While the existing mean reversion strategies are shown to achieve good empirical performance on many real datasets, they often make the single-period mean reversion assumption, which is not always satisfied in some real datasets, leading to poor performance when the assumption does not hold. To overcome the limitation, this article proposes a multiple-period mean reversion, or so-called Moving Average Reversion (MAR), and a …

Go to article

Exact Soft Confidence-Weighted Learning, Jialei Wang, Steven C. H. Hoi Jul 2012

Exact Soft Confidence-Weighted Learning, Jialei Wang, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

In this paper, we propose a new Soft Confidence-Weighted (SCW) online learning scheme, which enables the conventional confidence-weighted learning method to handle non-separable cases. Unlike the previous confidence-weighted learning algorithms, the proposed soft confidence-weighted learning method enjoys all the four salient properties: (i) large margin training, (ii) confidence weighting, (iii) capability to handle non-separable data, and (iv) adaptive margin. Our experimental results show that the proposed SCW algorithms significantly outperform the original CW algorithm. When comparing with a variety of state-of-the art algorithms (including AROW, NAROW and NHERD), we found that SCW generally achieves better or at least comparable predictive …

Go to article

Fast Bounded Online Gradient Descent Algorithms For Scalable Kernel-Based Online Learning, Peilin Zhao, Jialei Wang, Pengcheng Wu, Rong Jin, Steven C. H. Hoi Jul 2012

Fast Bounded Online Gradient Descent Algorithms For Scalable Kernel-Based Online Learning, Peilin Zhao, Jialei Wang, Pengcheng Wu, Rong Jin, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Kernel-based online learning has often shown state-of-the-art performance for many online learning tasks. It, however, suffers from a major shortcoming, that is, the unbounded number of support vectors, making it non-scalable and unsuitable for applications with large-scale datasets. In this work, we study the problem of bounded kernel-based online learning that aims to constrain the number of support vectors by a predefined budget. Although several algorithms have been proposed in literature, they are neither computationally efficient due to their intensive budget maintenance strategy nor effective due to the use of simple Perceptron algorithm. To overcome these limitations, we propose a …

Go to article

Online Kernel Selection: Algorithms And Evaluations, Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Jinfeng Yi, Steven C. H. Hoi Jul 2012

Online Kernel Selection: Algorithms And Evaluations, Tianbao Yang, Mehrdad Mahdavi, Rong Jin, Jinfeng Yi, Steven C. H. Hoi

Research Collection School Of Computing and Information Systems

Kernel methods have been successfully applied to many machine learning problems. Nevertheless, since the performance of kernel methods depends heavily on the type of kernels being used, identifying good kernels among a set of given kernels is important to the success of kernel methods. A straightforward approach to address this problem is cross-validation by training a separate classifier for each kernel and choosing the best kernel classifier out of them. Another approach is Multiple Kernel Learning (MKL), which aims to learn a single kernel classifier from an optimal combination of multiple kernels. However, both approaches suffer from a high computational …

Go to article

Targeted Maximum Likelihood Estimation For Dynamic Treatment Regimes In Sequential Randomized Controlled Trials, Paul Chaffee, Mark J. Van Der Laan Jun 2012

Targeted Maximum Likelihood Estimation For Dynamic Treatment Regimes In Sequential Randomized Controlled Trials, Paul Chaffee, Mark J. Van Der Laan

Paul H. Chaffee

Sequential Randomized Controlled Trials (SRCTs) are rapidly becoming essential tools in the search for optimized treatment regimes in ongoing treatment settings. Analyzing data for multiple time-point treatments with a view toward optimal treatment regimes is of interest in many types of afflictions: HIV infection, Attention Deficit Hyperactivity Disorder in children, leukemia, prostate cancer, renal failure, and many others. Methods for analyzing data from SRCTs exist but they are either inefficient or suffer from the drawbacks of estimating equation methodology. We describe an estimation procedure, targeted maximum likelihood estimation (TMLE), which has been fully developed and implemented in point treatment settings, …

Go to article

The Intersection Between Science And Computer Science Is Almost Empty, Dick Hamlet Jun 2012

The Intersection Between Science And Computer Science Is Almost Empty, Dick Hamlet

Systems Science Friday Noon Seminar Series

Traditionally, a science such as physics overlaps with mathematics and engineering in a way that has been astonishingly productive. The math provides precise expression for the science, which in turn supplies the engineering with the information it needs to exploit physical phenomena. Computer science naturally wishes to put itself in the center of the traditional picture as a science. Unfortunately, it won't wash. The `science' of programming is pure and simple mathematics, not science. The distinction is more than linguistic, since science and mathematics have quite distinct goals and methods. By making the wrong choice, computer science research has been …

Go to article

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoffrey J. Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Ajay Srinivasan Aravamudhan, Shih-Fen Cheng Jun 2012

Lagrangian Relaxation For Large-Scale Multi-Agent Planning, Geoffrey J. Gordon, Pradeep Varakantham, William Yeoh, Hoong Chuin Lau, Ajay Srinivasan Aravamudhan, Shih-Fen Cheng

LARC Research Publications

Multi-agent planning is a well-studied problem with applications in various areas. Due to computational constraints, existing research typically focuses either on unstructured domains with many agents, where we are content with heuristic solutions, or domains with small numbers of agents or special structure, where we can find provably near-optimal solutions. In contrast, here we focus on provably near-optimal solutions in domains with many agents, by exploiting influence limit. To that end, we make two key contributions: (a) an algorithm, based on Lagrangian relaxation and randomized rounding, for solving multi-agent planning problems represented as large mixed-integer programs; (b) a proof of …

Go to article

Next Last