Theory and Algorithms Commons^™

Two Algorithms In Search Of A Type System, Norman Danner, James Royer

Norman Danner

The authors’ ATR programming formalism is a version of call-by-value PCF under a complexity-theoretically motivated type system. ATR programs run in type-2 polynomial-time and all standard type-2 basic feasible functionals are ATR -definable ( ATR types are confined to levels 0, 1, and 2). A limitation of the original version of ATR is that the only directly expressible recursions are tail-recursions. Here we extend ATR so that a broad range of affine recursions are directly expressible. In particular, the revised ATR can fairly naturally express the classic insertion- and selection-sort algorithms, thus overcoming a sticking point of most prior implicit-complexity-based …

Wildfire Assessment Using Farsite Fire Modeling: A Case Study In The Chihuahua Desert Of Mexico, John Brakeall

FIU Electronic Theses and Dissertations

The Chihuahua desert is one of the most biologically diverse ecosystems in the world, but suffers serious degradation because of changes in fire regimes resulting in large catastrophic fires. My study was conducted in the Sierra La Mojonera (SLM) natural protected area in Mexico. The purpose of this study was to implement the use of FARSITE fire modeling as a fire management tool to develop an integrated fire management plan at SLM.

Firebreaks proved to detain 100% of wildfire outbreaks. The rosetophilous scrub experienced the fastest rate of fire spread and lowland creosote bush scrub experienced the slowest rate of …

Guidance In Feature Extraction To Resolve Uncertainty, Boris Kovalerchuk, Michael Kovalerchuk, Simon Streltsov, Matthew Best

Computer Science Faculty Scholarship

Automated Feature Extraction (AFE) plays a critical role in image understanding. Often the imagery analysts extract features better than AFE algorithms do, because analysts use additional information. The extraction and processing of this information can be more complex than the original AFE task, and that leads to the “complexity trap”. This can happen when the shadow from the buildings guides the extraction of buildings and roads. This work proposes an AFE algorithm to extract roads and trails by using the GMTI/GPS tracking information and older inaccurate maps of roads and trails as AFE guides.

Protocases, Christopher M. Polis

Computer Engineering

Design and implementation of a 3D printing web application.

Integrated Collision Avoidance System Sensor Evaluation Final Design Project, Alex F. Graebe, Bridgette S. Kimball, Drew T. Lavoise

Mechanical Engineering

Following the development of Aircraft Collision Avoidance Technology (ACAT) by the National Aeronautics and Space Administration (NASA), a need arose to transition the life-saving technology to aid the general aviation community. Considering the realistic cost of implementation, it was decided that the technology should be adapted to function on any smartphone, using that device as an end-to-end solution to sense, process, and alert the pilot to imminent threats. In September of 2012, the SAS (Sense and Survive) Senior Project Team at California Polytechnic University (Cal Poly), San Luis Obispo was assigned the task of using smartphone technology to accurately sense …

Understanding Sequential Decisions Via Inverse Reinforcement Learning, Siyuan Liu, Miguel Araujo, Emma Brunskill, Rosaldo Rossetti, Joao Barros, Ramayya Krishnan

Research Collection School Of Computing and Information Systems

The execution of an agent's complex activities, comprising sequences of simpler actions, sometimes leads to the clash of conflicting functions that must be optimized. These functions represent satisfaction, short-term as well as long-term objectives, costs and individual preferences. The way that these functions are weighted is usually unknown even to the decision maker. But if we were able to understand the individual motivations and compare such motivations among individuals, then we would be able to actively change the environment so as to increase satisfaction and/or improve performance. In this work, we approach the problem of providing highlevel and intelligible descriptions …

Visual Tracking Via Locality Sensitive Histograms, Shengfeng He, Qingxiong Yang, Rynson W.H. Lau, Jian Wang, Ming-Hsuan Yang

Research Collection School Of Computing and Information Systems

This paper presents a novel locality sensitive histogram algorithm for visual tracking. Unlike the conventional image histogram that counts the frequency of occurrences of each intensity value by adding ones to the corresponding bin, a locality sensitive histogram is computed at each pixel location and a floating-point value is added to the corresponding bin for each occurrence of an intensity value. The floating-point value declines exponentially with respect to the distance to the pixel location where the histogram is computed, thus every pixel is considered but those that are far away can be neglected due to the very small weights …

Notes On Equilibria In Symmetric Games, Shih-Fen Cheng, Daniel M. Reeves, Yevgeniy Vorobeychik, Michael P. Wellman

Shih-Fen CHENG

In a symmetric game, every player is identical with respect to the game rules. We show that a symmetric 2strategy game must have a pure-strategy Nash equilibrium. We also discuss Nash’s original paper and its generalized notion of symmetry in games. As a special case of Nash’s theorem, any finite symmetric game has a symmetric Nash equilibrium. Furthermore, symmetric infinite games with compact, convex strategy spaces and continuous, quasiconcave utility functions have symmetric pure-strategy Nash equilibria. Finally, we discuss how to exploit symmetry for more efficient methods of finding Nash equilibria.

Iterative Statistical Verification Of Probabilistic Plans, Colin M. Potts

Lawrence University Honors Projects

Artificial intelligence seeks to create intelligent agents. An agent can be anything: an autopilot, a self-driving car, a robot, a person, or even an anti-virus system. While the current state-of-the-art may not achieve intelligence (a rather dubious thing to quantify) it certainly achieves a sense of autonomy. A key aspect of an autonomous system is its ability to maintain and guarantee safety—defined as avoiding some set of undesired outcomes. The piece of software responsible for this is called a planner, which is essentially an automated problem solver. An advantage computer planners have over humans is their ability to consider and …

A Study Of Possible Optimizations For The Task Scheduler ‘Quark’ On The Shared Memory Architecture, Vijay Gopal Joshi

Masters Theses

Multicore processors are replacing most of the single core processors nowadays.

Current trends show that there will be increasing numbers of cores on a single chip in the coming future. However, programming multicore processors remains bug prone and less productive. Thus, making use of a runtime to schedule tasks on multicore processor hides most of the complexities of parallel programming to improve productivity. QUARK is one of the runtimes available for the multicore processors. This work looks at identifying and solving performance bottlenecks for QUARK on the shared memory architecture. The problem of finding bottlenecks is divided into two parts, …

Real Time Digital Night Vision Using Nonlinear Contrast Enhancement, Nishikar Sapkota

UNLV Theses, Dissertations, Professional Papers, and Capstones

This thesis describes a nonlinear contrast enhancement technique to implement night vision in digital video. It is based on the global histogram equalization algorithm. First, the effectiveness of global histogram equalization is examined for images taken in low illumination environments in terms of Peak signal to noise ratio (PSNR) and visual inspection of images. Our analysis establishes the existence of an optimum intensity for which histogram equalization yields the best results in terms of output image quality in the context of night vision. Based on this observation, an incremental approach to histogram equalization is developed which gives better results than …

Scheduling Jobs On Two Uniform Parallel Machines To Minimize The Makespan, Sandhya Kodimala

UNLV Theses, Dissertations, Professional Papers, and Capstones

The problem of scheduling n independent jobs on m uniform parallel machines such that the total completion time is minimized is a NP-Hard problem. We propose several heuristic-based online algorithms for machines with different speeds called Q₂||C_max. To show the efficiency of the proposed online algorithms, we compute the optimal solution for Q₂||C_max using pseudo-polynomial algorithms based on dynamic programming method. The pseudo-polynomial algorithm has time complexity O (n T²) and can be run on reasonable time for small number of jobs and small processing times. This optimal offline algorithm is …

Calibration Of Traffic Flow Models, Victor Molano

College of Engineering: Graduate Celebration Programs

This study proposes a methodology to calibrate microscopic traffic flow simulation models. A Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm searches for the set of model parameters that minimizes the difference between actual and simulated values

Fast Sobel Edge Detection Using Parallel Pipeline-Based Architecture On Fpga, Mohammad Shokrolah Shirazi, Brendan Morris

College of Engineering: Graduate Celebration Programs

Implementing image processing algorithms on FPGA has recently become more popular since it provides high speed in comparison with software-based approaches. In this paper, we have presented fast pipeline-based architecture for one of the most popular edge detection algorithms called Sobel edge detection. The objective of our work is to present two fast pipeline-based architectures for Sobel edge detection on FPGA benefiting one and two way parallelism. We used Verilog language to implement our designs and we synthesized each one for Cyclone IV FPGA. Experimental results show that our pipeline-based architectures perform edge detection process more than 379 and 751 …

On High-Performance Parallel Decimal Fixed-Point Multiplier Designs, Ming Zhu

College of Engineering: Graduate Celebration Programs

Decimal computations are required in finance, and etc.

• Precise representation for decimals (E.g. 0.2, 0.7… )
• Performance Requirements (Software simulations are very slow)

Mono-Sized Sphere Packing Algorithm Development Using Optimized Monte Carlo Technique, Karn Soontrapa, Yitung Chen

College of Engineering: Graduate Celebration Programs

In this research, fuel cell catalyst layer was developed using the optimized sphere packing algorithm. An optimization technique named adaptive random search technique (ARSET) was employed in this packing algorithm. The ARSET algorithm will generate the initial location of spheres and allow them to move in the random direction with the variable moving distance, randomly selected from the sampling range (a), based on the Lennard–Jones potential and Morse potential of the current and new configuration. The solid fraction values obtained from this developed algorithm are in the range of 0.610–0.624 while the actual processing time can significantly be reduced by …

Image Processing Algorithms For Improving Planetary Exploration And Understanding, Ali Pouryazdanpanah

College of Engineering: Graduate Celebration Programs

• To design a fully automated tool-set that allows to detect and extract the sky region in planetary images.

• To develop the new method for rock segmentation in planetary stereo images.
• To develop the new method for shadow detection in planetary images

Payload Processing Aboard An Open Source Software Cubesat, Jon Sand, Kyle Goehner, Christoffer Korvald, Josh Berk, Jeremy Straub

Jeremy Straub

The Open Prototype for Educational NanoSats (OPEN) is a system that focuses on reducing spacecraft mission costs. It provides a set of designs that is freely available to anyone online. The OpenOrbiter CubeSat provides designs to create a small satellite using economical materials available allowing a parts budget of under $5,000. One aspect of this design is CubeSat payload processing software. This is the process of taking a single image, or multiple images taken at the same time, and manipulate them. This manipulation an include compression, mosaicing, super resolution, or any combination thereof. The first step in this process is …

The Development Of Payload Software For A Small Spacecraft, Kyle Goehner, Christoffer Korvald, Jeremy Straub, Ronald Marsh

Jeremy Straub

The OpenOrbiter project is a multi-department effort to design and build a small spacecraft which will demonstrate the feasibility of the Open Prototype for Educational NanoSats (OPEN) framework. This framework will reduce cost of small spacecraft creation by providing design plans for free. The focus of the payload software group is to design and implement an onboard task processing and image processing service. Currently the project is in the development phase and most large design decisions have been made. This poster presents the major design decisions that have been made for the payload software and how they will affect the …

Nfa Reduction Via Hypergraph Vertex Cover Approximation, Timothy Ng

Electronic Thesis and Dissertation Repository

In this thesis, we study in minimum vertex cover problem on the class of k-partite k-uniform hypergraphs. This problem arises when reducing the size of nondeterministic finite automata (NFA) using preorders, as suggested by Champarnaud and Coulon. It has been shown that reducing NFAs using preorders is at least as hard as computing a minimal vertex cover on 3-partite 3-uniform hypergraphs, which is NP-hard. We present several classes of regular languages for which NFAs that recognize them can be optimally reduced via preorders. We introduce an algorithm for approximating vertex cover on k-partite k-uniform hypergraphs based on a theorem by …