Theory and Algorithms Commons^™

Improved Algorithms For Ear-Clipping Triangulation, Bartosz Kajak

UNLV Theses, Dissertations, Professional Papers, and Capstones

We consider the problem of improving ear-slicing algorithm for triangulating a simple polygon. We propose two variations of ear-slicing technique for generating “good-quality” triangulation. The first approach is based on searching for the best triangle along the boundary. The second approach considers polygon partitioning on a pre-process before applying the ear-slicing. Experimental investigation reveals that both approaches yield better quality triangulation than the standard ear-slicing method.

Shop Problems In Scheduling, James Andro-Vasko

UNLV Theses, Dissertations, Professional Papers, and Capstones

The shop problems in scheduling will be discussed in this thesis. The ones I'll be discussing will be the flow shop, open shop, and job shop. The general idea of shop problems is that you're given a set of jobs and a set of machines. Each job is predeterminely broken into parts and there are rules to how each part is executed on a machine. In this thesis, several shop problems and their algorithms will be introduced that I have researched. There are several examples and counter examples that I have constructed. Also I will discuss how an arbitrary problem …

Sharp Feature Identification In A Polygon, Joseph P. Scanlan

UNLV Theses, Dissertations, Professional Papers, and Capstones

This thesis presents an efficient algorithm for recognizing and extracting sharp-features from polygonal shapes. As used here, a sharp-feature is a distinct portion of a polygon that is long and skinny. The algorithm executes in O(n^2) time, where n is the number of vertices in the polygon. Experimental results from a Java implementation of the algorithm are also presented.

Finding Acronyms And Their Definitions Using Hmm, Lakshmi Vyas

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis, we report on design and implementation of a Hidden Markov Model (HMM) to extract acronyms and their expansions. We also report on the training of this HMM with Maximum Likelihood Estimation (MLE) algorithm using a set of examples.

Finally, we report on our testing using standard recall and precision. The HMM achieves a recall and precision of 98% and 92% respectively.

Implementation Of Hidden Semi-Markov Models, Nagendra Abhinav Dasu

UNLV Theses, Dissertations, Professional Papers, and Capstones

One of the most frequently used concepts applied to a variety of engineering and scientific studies over the recent years is that of a Hidden Markov Model (HMM). The Hidden semi-Markov model (HsMM) is contrived in such a way that it does not make any premise of constant or geometric distributions of a state duration. In other words, it allows the stochastic process to be a semi-Markov chain. Each state can have a collection of observations and the duration of each state is a variable. This allows the HsMM to be used extensively over a range of applications. Some of …

Implementation Of Numerically Stable Hidden Markov Model, Usha Ramya Tatavarty

UNLV Theses, Dissertations, Professional Papers, and Capstones

A Hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process with unobserved (hidden) states. HMM is an extremely flexible tool and has been successfully applied to a wide variety of stochastic modeling tasks. One of the first applications of HMM is speech recognition. Later they came to be known for their applicability in handwriting recognition, part-of-speech tagging and bio-informatics.

In this thesis, we will explain the mathematics involved in HMMs and how to efficiently perform HMM computations using dynamic programming (DP) which makes it easy to implement …

Topic Detection And Tracking Using Hidden Markov Models, Aditya S. Tatavarty

UNLV Theses, Dissertations, Professional Papers, and Capstones

There is a continuous progress in automatic recording of broadcast speech using speech recognition. With the increasing use of this technology, a new source of data is added to the pool of information available over web. This has increased the need to categorize the resulting text, based on their topic for the purpose of information retrieval.

In this thesis we present an approach to automatically assign a topic or track a change of topic in a stream of input data. Our approach is based on the use of Hidden Markov Models and language processing techniques. We consider input text as …

Using Smoothing Techniques To Improve The Performance Of Hidden Markov’S Model, Sweatha Boodidhi

UNLV Theses, Dissertations, Professional Papers, and Capstones

The result of training a HMM using supervised training is estimated probabilities for emissions and transitions. There are two difficulties with this approach Firstly, sparse training data causes poor probability estimates. Secondly, unseen probabilities have emission probability of zero. In this thesis, we report on different smoothing techniques and their implementations. We further report on our experimental results using standard precision and recall for various smoothing techniques.

Information Extraction In An Optical Character Recognition Context, Ramon Pereda

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this dissertation, we investigate the effectiveness of information extraction in the presence of Optical Character Recognition (OCR). It is well known that the OCR errors have no effects on general retrieval tasks. This is mainly due to the redundancy of information in textual documents. Our work shows that information extraction task is significantly influenced by OCR errors. Intuitively, this is due to the fact that extraction algorithms rely on a small window of text surrounding the objects to be extracted.

We show that extraction methodologies based on the Hidden Markov Models are not robust enough to deal with extraction …

Dynamic Decision Making And Race Games, Shipra De

Calvert Undergraduate Research Awards

Frequent criticism in dynamic decision making research pertains to the overly complex nature of the decision tasks used in experimentation. To address such concerns we study dynamic decision making with respect to the simple race game Hog, which has a computable optimal decision strategy. In the two-player game of Hog, individuals compete to be the first to reach a designated threshold of points. Players alternate rolling a desired quantity of dice. If the number one appears on any of the dice, the player receives no points for his turn; otherwise, the sum of the numbers appearing on the dice is …

Detours Admitting Short Paths, Reshma Koganti

UNLV Theses, Dissertations, Professional Papers, and Capstones

Finding shortest paths between two vertices in a weighted graph is a well explored problem and several efficient algorithms for solving it have been reported. We propose a new variation of this problem which we call the Detour Admitting Shortest Path Problem (DASPP).We present an efficient algorithm for solving DASPP. This is the first algorithm that constructs a shortest path such that each edge of the shortest path admits a detour with no more than k−hops. This algorithm has important applications in transportation networks. We also present implementation issues for the detour admitting shortest path algorithm.

Cloud Storage And Online Bin Packing, Swathi Venigella

UNLV Theses, Dissertations, Professional Papers, and Capstones

Cloud storage is the service provided by some corporations (such as Mozy and Carbonite) to store and backup computer files. We study the problem of allocating memory of servers in a data center based on online requests for storage. Over-the-net data backup has become increasingly easy and cheap due to cloud storage. Given an online sequence of storage requests and a cost associated with serving the request by allocating space on a certain server one seeks to select the minimum number of servers as to minimize total cost. We use two different algorithms and propose a third algorithm; we show …

Design Of A Software Framework Prototype For Scientific Model Interoperability, Eric Fritzinger, Sohei Okamoto

2010 Annual Nevada NSF EPSCoR Climate Change Conference

19 PowerPoint slides Session 2: Infrastructure Convener: Sergiu Dascalu, UNR Abstract: -What are models? -Mathematical models used to describe a system -E.g. Atmospheric, Oceanic, Ecological, etc… -Algorithmic calculations which take input and produce estimated results -Weather forecasting, global warming predictions, sea level estimations, etc… -Models are invaluable

A Study Of Relevance Feedback In Vector Space Model, Deepthi Katta

UNLV Theses, Dissertations, Professional Papers, and Capstones

Information Retrieval is the science of searching for information or documents based on information need from a huge set of documents. It has been an active field of research since early 19^th century and different models of retrieval came in to existence to cater the information need.

This thesis starts with understanding some of the basic information retrieval models, followed by implementation of one of the most popular statistical retrieval model known as Vector Space Model. This model ranks the documents in the collection based on the similarity measure calculated between the query and the respective document. The user …

Turn Constrained Path Planning Problems, Victor M. Roman

UNLV Theses, Dissertations, Professional Papers, and Capstones

We consider the problem of constructing multiple disjoint paths connecting a source point s to a target point t in a geometric graph. We require that the paths do not have any sharp turn angles. We present a review of turn constrained path planning algorithms and also algorithms for constructing disjoint paths. We then combine these techniques and present an O(nlogn) time algorithm for constructing a pair of edge disjoint turn constrained paths connecting two nodes in a planar geometric graph. We also consider the development of a turn constrained shortest path map in the presence of …

A Survey Of Monge Properties, Swetha Sethumadhavan

UNLV Theses, Dissertations, Professional Papers, and Capstones

Monge properties play an important role in theoretical computer science. Many greedy algorithms are based on such properties, as is speedup in dynamic programming. Monge properties are simple monotonicity properties which are observed and used in various settings such as resource optimization, computational geometry, statistical sampling, computational biology and coding.

Efficient Scheduling For Sdmg Cioq Switches, Mei Yang, S. Q. Zheng

Electrical & Computer Engineering Faculty Research

Combined input and output queuing (CIOQ) switches are being considered as high-performance switch architectures due to their ability to achieve 100% throughput and perfectly emulate output queuing (OQ) switch performance with a small speedup factor S. To realize a speedup factor S, a conventional CIOQ switch requires the switching fabric and memories to operate S times faster than the line rate. In this paper, we propose to use a CIOQ switch with space-division multiplexing expansion and grouped input/output ports (SDMG CIOQ switch for short) to realize speedup while only requiring the switching fabric and memories to operate at the line …

A Fast And Simple Algorithm For Computing M Shortest Paths In Stage Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

A Fast And Simple Algorithm For Computing M-Shortest Paths In State Graph, M. Sherwood, Laxmi P. Gewali, Henry Selvaraj, Venkatesan Muthukumar

Electrical & Computer Engineering Faculty Research

We consider the problem of computing m shortest paths between a source node s and a target node t in a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk reduced multiple k-legged trajectories for aerial vehicles.

Real-Time Travel Time Estimation Using Macroscopic Traffic Flow Models, Pushkin Kachroo, Kaan Ozbay, Antoine G. Hobeika

Electrical & Computer Engineering Faculty Research

This paper presents the estimation of travel time on highways based on macroscopic modelling. The focus is on real-time values as compared to average or static values. The macroscopic models are used for distributed and time/space lumped settings and corresponding travel time estimation functions and algorithms are developed. The implications of these algorithms for the implementation of various incident management and traffic control strategies are also discussed.

Isolated Ramp Metering Feedback Control Utilizing Mixed Sensitivity For Desired Mainline Density And The Ramp Queues, Pushkin Kachroo, Kaan Ozbay, Donald E. Grove

Electrical & Computer Engineering Faculty Research

This paper presents a feedback control design for isolated ramp metering control. This feedback control design, unlike the existing isolated feedback ramp controllers, also takes into account the ramp queue length. Using a nonlinear H∞ control design methodology, we formulate the problem in the desired setting to be able to utilize the results of the methodology.

Investigating The Use Of Kalman Filtering Approaches For Dynamic Origin-Destination Trip Table Estimation, Pushkin Kachroo, Kaan Ozbay, Arvind Narayanan

Electrical & Computer Engineering Faculty Research

This paper studies the applicability of Kalman filtering approaches for network wide traveler origin-destination estimation from link traffic volumes. The paper evaluates the modeling assumptions of the Kalman filters and examines the implications of such assumptions.

Feedback Control Solutions To Network Level User-Equilibrium Real-Time Dynamic Traffic Assignment Problems, Pushkin Kachroo, Kaan Ozbay

Electrical & Computer Engineering Faculty Research

A new method for performing dynamic traffic assignment (DTA) is presented which is applicable in real time, since the solution is based on feedback control. This method employs the design of nonlinear H∞ feedback control systems which is robust to certain class of uncertainties in the system. The solution aims at achieving user equilibrium on alternate routes in a network setting.