Theory and Algorithms Commons^™

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 …

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 …

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 …

Combinatorics Using Computational Methods, Derrick Stolee

Department of Mathematics: Dissertations, Theses, and Student Research

Computational combinatorics involves combining pure mathematics, algorithms, and computational resources to solve problems in pure combinatorics. This thesis provides a theoretical framework for combinatorial search, which is then applied to several problems in combinatorics. Some results in space-bounded computational complexity are also presented.

Isomorph-Free Generation Of 2-Connected Graphs With Applications, Derrick Stolee

School of Computing: Technical Reports

Many interesting graph families contain only 2-connected graphs, which have ear decompositions. We develop a technique to generate families of unlabeled 2-connected graphs using ear augmentations and apply this technique to two problems. In the first application, we search for uniquely Kr-saturated graphs and find the list of uniquely K4-saturated graphs on at most 12 vertices, supporting current conjectures for this problem. In the second application, we verify the Edge Reconstruction Conjecture for all 2-connected graphs on at most 12 vertices. This technique can be easily extended to more problems concerning 2-connected graphs.

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.

Structure And Randomness Of The Discrete Lambert Map, Jingjing Chen, Mark Lotts

Mathematical Sciences Technical Reports (MSTR)

We investigate the structure and cryptographic applications of the Discrete Lambert Map (DLM). The mapping is closely related to the Discrete Log Problem, but has received far less attention since it is considered to be a more complicated map that is likely even harder to invert. However, this mapping is quite important because it underlies the security of the ElGamal Digital Signature Scheme. Using functional graphs induced by this mapping, we were able to find non-random properties that could potentially be used to exploit the ElGamal DSS.

The Square Discrete Exponentiation Map, A Wood

Mathematical Sciences Technical Reports (MSTR)

We will examine the square discrete exponentiation map and its properties. The square discrete exponentiation map is a variation on a commonly seen problem in cryptographic algorithms. This paper focuses on understanding the underlying structure of the functional graphs generated by this map. Specifically, this paper focuses on explaining the in-degree of graphs of safe primes, which are primes of the form p = 2q + 1, where q is also prime.

Algebraic Solutions To Overdefined Systems With Applications To Cryptanalysis, Eric Crockett

Mathematical Sciences Technical Reports (MSTR)

Cryptographic algorithms are based on a wide variety of difficult problems in mathematics. One of these problems is finding a solution to a system of multivariate quadratic equations (MQ). A generalization of this problem is to find a solution to a system of higher order non-linear equations. Both of these problems are NP-hard over any field. Many cryptosystems such as AES, Serpent, Toyocrypt, and others can be reduced to some form of the MQ problem. In this paper we analyze the relinearization and XL algorithms for solving overdetermined systems of non-linear equations, as well as two variations of the XL …

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.

Minimax And Maximin Fitting Of Geometric Objects To Sets Of Points, Yan B. Mayster

Electronic Theses and Dissertations

This thesis addresses several problems in the facility location sub-area of computational geometry. Let S be a set of n points in the plane. We derive algorithms for approximating S by a step function curve of size k < n, i.e., by an x-monotone orthogonal polyline ℜ with k < n horizontal segments. We use the vertical distance to measure the quality of the approximation, i.e., the maximum distance from a point in S to the horizontal segment directly above or below it. We consider two types of problems: min-ε, where the goal is to minimize the error for a …

Flipping The Winner Of A Poset Game, Adam O. Kalinich '12

Student Publications & Research

Partially-ordered set games, also called poset games, are a class of two-player combinatorial games. The playing field consists of a set of elements, some of which are greater than other elements. Two players take turns removing an element and all elements greater than it, and whoever takes the last element wins. Examples of poset games include Nim and Chomp. We investigate the complexity of computing which player of a poset game has a winning strategy. We give an inductive procedure that modifies poset games to change the nim-value which informally captures the winning strategies in the game. For a generic …

Economic Optimization Of Offshore Wind Farms Using The Geometric Algorithm, Mahidhar Nandigam

Electrical & Computer Engineering Theses & Dissertations

The research project related to this thesis focuses on the optimization of electrical systems for offshore wind farms for a given capacity. The optimal design and planning is a critical issue for developing cost effectively Offshore Wind Farms in energy systems. The Geometric Optimization Algorithms approach has been adopted to develop an optimization program, where the main components of the electrical system of an offshore wind farm and key technical specifications are used as parameters to be optimized for a minimum cost with necessary constraints. The effectiveness of the optimization program can be evaluated with real-time comparison between offshore wind …

Statistical Investigation Of Structure In The Discrete Logarithm, Andrew Hoffman

Mathematical Sciences Technical Reports (MSTR)

The absence of an efficient algorithm to solve the Discrete Logarithm Problem is often exploited in cryptography. While exponentiation with a modulus is extremely fast with a modern computer, the inverse is decidedly not. At the present time, the best algorithms assume that the inverse mapping is completely random. Yet there is at least some structure, and to uncover additional structure that may be useful in constructing or refining algorithms, statistical methods are employed to compare modular exponential mappings to random mappings. More concretely, structure will be defined by representing the mappings as functional graphs and using parameters from graph …

Reed-Solomon Codes Construction & Decoding, Samuel J. Parsons

Honors Capstones

Capstone submitted as a graduation requirement for the BSU Honors Program.

Srt Division Algorithms As Dynamical Systems, Mark Mccann, Nicholas Pippenger

All HMC Faculty Publications and Research

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able …

Vector Operations In Superscalar Architectures, Nathan Daniel Flinn

Electrical & Computer Engineering Theses & Dissertations

Vector calculations are very prevalent today. Though the vector-processing computer is quite an old concept, superscalar processors lack hardware support for vector operations. This thesis investigates whether an ordinary superscalar computer architecture can be designed to include hardware support for improved vector operations without drastically changing the existing superscalar design and behavior. A computer architecture design was created and implemented that included the vector multiply (dot product) operation. The design includes a Vector Operations Unit that captures incoming vector operations and generates the necessary set of machine instructions to complete the vector operation internally. It then delivers these instructions to …

On Strongly N-Regular And Strongly Regular Rings, Huey Voon Chen

Student Works (2000-2009)

Let R be an associative ring with identity 1 (not equal to) 0. An element x E R is said to be right (or left) regular if there exists yin R such that x² y = x (or y.x² = x). If x is both left and right regular, then it is said to be strongly regular. The ring R is said to be strongly regular if every element of R is strongly regular. We say that x is a left -π-regular element if there exist an integer n > 0 and an element y E R such that yx n+1 …

Maximally Disjoint Solutions Of The Set Covering Problem, David J. Rader, Peter L. Hammer

Mathematical Sciences Technical Reports (MSTR)

This paper is concerned with finding two solutions of a set covering problem that have a minimum number of variables in common. We show that this problem is NP­ complete, even in the case where we are only interested in completely disjoint solutions. We describe three heuristic methods based on the standard greedy algorithm for set covering problems. Two of these algorithms find the solutions sequentially, while the third finds them simultaneously. A local search method for reducing the overlap of the two given solutions is then described. This method involves the solution of a reduced set covering problem. Finally, …

Representations, Approximations, And Algorithms For Mathematical Speech Processing, Laura R. Suzuki

Theses and Dissertations

Representing speech signals such that specific characteristics of speech are included is essential in many Air Force and DoD signal processing applications. A mathematical construct called a frame is presented which captures the important time-varying characteristic of speech. Roughly speaking, frames generalize the idea of an orthogonal basis in a Hilbert space, Specific spaces applicable to speech are L₂(R) and the Hardy spaces H_p(D) for p> 1 where D is the unit disk in the complex plane. Results are given for representations in the Hardy spaces involving Carleson's inequalities (and its extensions), …

Tree-Based Multicasting In Wormhole-Routed Irregular Topologies, Ran Libeskind-Hadas, Dominic Mazzoni '99, Ranjith Rajagopalan '99

All HMC Faculty Publications and Research

A deadlock-free tree-based multicast routing algorithm is presented for all direct networks, regardless of interconnection topology. The algorithm delivers a message to any number of destinations using only a single startup phase. In contrast to existing tree-based schemes, this algorithm applies to all interconnection topologies, requires only fixed-sized input buffers that are independent of maximum message length, and uses a single asynchronous flit replication mechanism. The theoretical basis of the technique used here is sufficiently general to develop other tree-based multicasting algorithms for regular and irregular topologies. Simulation results demonstrate that this tree-based algorithm provides a very promising means of …

Resolution Of Local Inconsistency In Identification, Douglas Ray Anderson, Martin Zwick

Complex Systems Faculty Publications and Presentations

This paper reports an algorithm for the resolution of local inconsistency in information-theoretic identification. This problem was first pointed out by Klir as an important research area in reconstructability analysis. Local inconsistency commonly arises when an attempt is made to integrate multiple data sources, i.e., contingency tables, which have differing common margins. For example, if one ha)s an AB table and a BC table, the B margins obtained from the two tables may disagree. If the disagreement can be assigned to sampling error, then one can arrive at a compromise B margin, adjust the original AB and BC tables to …

Indifference Graphs And The Single Row Routing Problem, Peter J. Looges

Computer Science Theses & Dissertations

This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.

A Root Finding Algorithm For Parallel Architecture Machines, Stuti Moitra

Computer Science Theses & Dissertations

In this thesis a parallel algorithm for determining the zeros of any given analytic function is described. Parallelism is achieved by modifying the traditional bisection algorithm for architecture machines.

Given any user supplied function f(X), continuous on the interval A_o ≤ x ≤ B₀, and the tolerance of accuracy an algorithm of determining up to ten roots, with error of approximation less than or equal to tolerance, on parallel systems like Distributed Array Processor (OAP) and N-cube is considered.

A variation of the bisection method has been adapted for this purpose. At each level of iteration a …

Wide-Sense Nonblocking Networks, Paul Feldman, Joel Friedman, Nicholas Pippenger

All HMC Faculty Publications and Research

A new method for constructing wide-sense nonblocking networks is presented. Application of this method yields (among other things) wide-sense nonblocking generalized connectors with n inputs and outputs and size O( n log n ), and with depth k and size O( n^{1 + 1/k} ( log n )^{1 - 1/k} ).

On Monotone Formulae With Restricted Depth, Maria M. Klawe, Wolfgang J. Paul, Nicholas J. Pippenger, Mihalis Yannakakis

All HMC Faculty Publications and Research

We prove a hierarchy theorem for the representation of monotone Boolean functions by monotone Boolean functions by monotone formulae with restricted depth. Specifically, we show that there are functions with Π_k-formulae of size n for which every Σ_k-formula has size exp Ω(n^1/(k-1)). A similar lower bound applies to concrete functions such as transitive closure and clique. We also show that any function with a formula of size n (and any depth) has a Σ_k-formula of size exp O(n^1/(k-1)). Thus our hierarchy theorem is the best possible.