Theory and Algorithms Commons^™

Efficient Estimation Of Cluster Population, Sanjeev K C

UNLV Theses, Dissertations, Professional Papers, and Capstones

Partitioning a given set of points into clusters is a well known problem in pattern recognition, data mining, and knowledge discovery. One of the well known methods for identifying clusters in Euclidean space is the K-mean algorithm. In using the K-mean clustering algorithm it is necessary to know the value of k (the number of clusters) in advance. We propose to develop algorithms for good estimation of k for points distributed in two dimensions. The techniques we pursue include a bucketing method, g-hop neighbors, and Voronoi diagrams. We also present experimental results for examining the performances of the bucketing method …

Spectral Decomposition Of The Scattered Light Due To Deposits On The Solar Panel Surface, And Cross Correlated To Power Loss, Suzanna Ho

UNLV Theses, Dissertations, Professional Papers, and Capstones

The electric energy generated by solar panels declines due to dust particulates, bird deposits, water spots, and other contaminants that inhibit sunlight absorption and promote light scattering. As part of our research, we use cameras to capture images of solar panels, and analyze the images to detect the amount of scattered light. The more scattered light there is, the less light there is to penetrate the solar panel glass and reach the part of the panel that converts incident light to electric energy; therefore, less energy is generated. In this paper, we discuss the classification algorithm we developed to classify …

Concurrent Localized Wait-Free Operations On A Red Black Tree, Vitaliy Kubushyn

UNLV Theses, Dissertations, Professional Papers, and Capstones

A red-black tree is a type of self-balancing binary search tree. Some wait-free algorithms have been proposed for concurrently accessing and modifying a red-black tree from multiple threads in shared memory systems. Most algorithms presented utilize the concept of a "window", and are entirely top-down implementations. Top-down algorithms like these have to operate on large portions of the tree, and operations on nodes that would otherwise not overlap at all still have to compete with and help one another.

A wait-free framework is proposed for obtaining ownership of small portions of the tree at a time in a bottom-up manner. …

A Characterization Of Open Shop Scheduling Problems Using The Hall Theorem And Network Flow, Arunasri Chitti

UNLV Theses, Dissertations, Professional Papers, and Capstones

Open shop scheduling problems are combinatorial problems where jobs with certain processing requirements on a number of different machines must be arranged in such a way that objectives related to completion time are optimized. Such problems have applications over a wide spectrum including such as communications, routing and manufacturing.

Many open shop problems are NP-hard but there are a number of special cases which possess polynomial solutions in the case of few machines or few jobs or when preemption of jobs is permitted. Many such solutions are based in the theory of matching or Hall's theorem, or more generally network …

Approaches For Generating 2d Shapes, Pratik Shankar Hada

UNLV Theses, Dissertations, Professional Papers, and Capstones

Constructing a two dimensional shape from given a set of point sites is a well known problem in computation geometry. We present a critical review of the existing algorithms for constructing polygonal shapes. We present a new approach calledinward dentingfor constructing simple polygons. We then extend the proposed approach for modeling polygons with holes. This is the

first known algorithm for modeling holes in the interior of 2d shapes. We also present experimental investigations of the quality of the solutions generated by the proposed algorithms.

For this we implemented the proposed algorithms in Java programming language. The prototype program can …

A Taxonomy Of Polynomially Solvable Shop Problems With Limited Number Of Machines Or Jobs, Megha Sairam Darapuneni

UNLV Theses, Dissertations, Professional Papers, and Capstones

Among shop scheduling problems, job shop and mixed shop are one of the most general models encompassing open shop and flow shop. Many job shop problems are NP hard, but there are numerous cases, which possess polynomial solutions when the number of jobs or the number of machines (or both) is limited.

This thesis gives an overview of methods and algorithms for solving - in polynomial time - such special shop problems, including open, flow, job shop and mixed shop. The tools used include Monge interchange, dynamic programming, greedy techniques and sweep line algorithms and the primary focus of this …

Object Detection Using Contrast Enhancement And Dynamic Noise Reduction, Justin Lee Baker

UNLV Theses, Dissertations, Professional Papers, and Capstones

Edge detection is one of the most important steps a computer must perform to gain understanding of an object in a digital image either from disk or from video feed. Edge detection allows for the computer to describe the shape of the objects in an image and create a pixel boundary defining what is considered part of an object, and what is not. Cannys edge detection algorithm is one of the most robust and accurate of these edge detection algorithms. However, as with many algorithms in image processing, there are many cases where the algorithm does not perform as well …

Application Of Ntru Cryptographic Algorithm For Securing Scada Communication, Amritha Puliadi Premnath

UNLV Theses, Dissertations, Professional Papers, and Capstones

Supervisory Control and Data Acquisition (SCADA) system is a control system which is widely used in Critical Infrastructure System to monitor and control industrial processes autonomously. Most of the SCADA communication protocols are vulnerable to various types of cyber-related attacks. The currently used security standards for SCADA communication specify the use of asymmetric cryptographic algorithms like RSA or ECC for securing SCADA communications. There are certain performance issues with cryptographic solutions of these specifications when applied to SCADA system with real-time constraints and hardware limitations. To overcome this issue, in this thesis we propose the use of a faster and …

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 …

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 …

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 …

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 …

Quantification Of Stochastic Uncertainty Propagation For Monte Carlo Depletion Methods In Reactor Analysis, Quentin Thomas Newell

UNLV Theses, Dissertations, Professional Papers, and Capstones

The Monte Carlo method provides powerful geometric modeling capabilities for large problem domains in 3-D; therefore, the Monte Carlo method is becoming popular for 3-D fuel depletion analyses to compute quantities of interest in spent nuclear fuel including isotopic compositions. The Monte Carlo approach has not been fully embraced due to unresolved issues concerning the effect of Monte Carlo uncertainties on the predicted results.

Use of the Monte Carlo method to solve the neutron transport equation introduces stochastic uncertainty in the computed fluxes. These fluxes are used to collapse cross sections, estimate power distributions, and deplete the fuel within depletion …

Identifying Effort Estimation Factors For Corrective Maintenance In Object-Oriented Systems, Michael J. Lee

UNLV Theses, Dissertations, Professional Papers, and Capstones

This research identifies factors that impact software maintenance effort by exploring the decision-making process of expert estimators of corrective maintenance projects by using qualitative methods to identify the factors that they use in deriving estimates. We implement a technique called causal mapping, which allows us to identify the cognitive links between the information that estimators use, and the estimates that they produce based on that information. Results suggest that a total of 17 factors may be relevant for corrective maintenance effort estimation, covering constructs related to developers, code, defects, and environment. When these factors are rank-ordered, they demonstrate that some …

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.

Roaming Region For Delaunay Triangulation, Romas James Hada

UNLV Theses, Dissertations, Professional Papers, and Capstones

Delaunay graphs have been used in CAD/CAM, sensor network and geographic information systems. We investigate the reliability properties of nodes in Delaunay graphs. For measuring the reliability we formulate the concept of roaming-region for nodes. A node v with large roaming-region r(v) such that v is positioned near the center of r(v) is identified as a reliable node. We develop algorithms for constructing roaming-regions and present an implementation of the proposed algorithm in the Java programming language.

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 …

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 …

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.

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 …

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 …

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 …

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.