Computer Sciences Commons^™

Partitioning Regular Polygons Into Circular Pieces Ii: Nonconvex Partitions, Mirela Damian, Joseph O'Rourke

Computer Science: Faculty Publications

We explore optimal circular nonconvex partitions of regular k-gons. The circularity of a polygon is measured by its aspect ratio: the ratio of the radii of the smallest circumscribing circle to the largest inscribed disk. An optimal circular partition minimizes the maximum ratio over all pieces in the partition. We show that the equilateral triangle has an optimal 4-piece nonconvex partition, the square an optimal 13-piece nonconvex partition, and the pentagon has an optimal nonconvex partition with more than 20 thousand pieces. For hexagons and beyond, we provide a general algorithm that approaches optimality, but does not achieve it.

Unfolding Smooth Prismatoids, Nadia Benbernou, Patricia Cahn, Joseph O'Rourke

Computer Science: Faculty Publications

We define a notion for unfolding smooth, ruled surfaces, and prove that every smooth prismatoid (the convex hull of two smooth curves lying in parallel planes), has a nonoverlapping “volcano unfolding.” These unfoldings keep the base intact, unfold the sides outward, splayed around the base, and attach the top to the tip of some side rib. Our result answers a question for smooth prismatoids whose analog for polyhedral prismatoids remains unsolved.

Computational Approaches To The Design And Analysis Of Stability Of Polypeptide Multilayer Thin Films, Bin Zheng

Doctoral Dissertations

The focus of this research is the development of computational approaches to understanding the physical basis of layer-by-layer assembly (LBL), a key methodology of nanomanufacturing. The results provided detailed information on structure which cannot be obtained directly by experiments.

The model systems chosen for study are polypeptide chains. Reasons for this are that polypeptides are no less polyelectrolytes than the more usual polyions, and one can control the primary structure of a polypeptide on a residue-by-residue basis using modern synthetic methods. Moreover, as peptides constitute one of the four major classes of biological macromolecules, research in this direction is expected …

Modulation Of Airway Inflammation By Immunostimulatory Cpg Oligodeoxynucleotides In A Murine Model Of Allergic Aspergillosis, Banani Banerjee, Kevin J. Kelly, Jordan N. Fink, James D. Henderson Jr., Naveen K. Bansal, Viswanath P. Kurup

Mathematics, Statistics and Computer Science Faculty Research and Publications

Allergic aspergillosis is a Th2 T-lymphocyte-mediated pulmonary complication in patients with atopic asthma and cystic fibrosis. Therefore, any therapeutic strategy that selectively inhibits Th2 T-cell activation may be useful in downregulating allergic lung inflammation in asthma. In the present study, we developed a CpG oligodeoxynucleotide (ODN)-based immune intervention of allergic inflammation in a mouse model of allergic aspergillosis. Four different groups of mice were used in a short-term immunization protocol. Three experimental groups of animals (groups 1 to 3) were sensitized with Aspergillus fumigatus antigens. Animals in group 1 were immunized with A. fumigatus antigen alone, while those in group …

Deadline Analysis Of Interrupt-Driven Software, Dennis Brylow, Jens Palsberg

Mathematics, Statistics and Computer Science Faculty Research and Publications

Real-time, reactive, and embedded systems are increasingly used throughout society (e.g., flight control, railway signaling, vehicle management, medical devices, and many others). For real-time, interrupt-driven software, timely interrupt handling is part of correctness. It is vital for software verification in such systems to check that all specified deadlines for interrupt handling are met. Such verification is a daunting task because of the large number of different possible interrupt arrival scenarios. For example, for a Z86-based microcontroller, there can be up to six interrupt sources and each interrupt can arrive during any clock cycle. Verification of such systems has traditionally relied …

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 …

Enhancements To Crisp Possibilistic Reconstructability Analysis, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified Reconstructibility Analysis (MRA), a novel decomposition within the framework of set-theoretic (crisp possibilistic) Reconstructibility Analysis, is presented. It is shown that in some cases while 3-variable NPN-classified Boolean functions are not decomposable using Conventional Reconstructibility Analysis (CRA), they are decomposable using Modified Reconstructibility Analysis (MRA). Also, it is shown that whenever a decomposition of 3-variable NPN-classified Boolean functions exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. A comparison of the corresponding complexities for Ashenhurst-Curtis decompositions, and Modified Reconstructibility Analysis (MRA) is also presented. While both AC and MRA decompose some but …

Factorization Of Polynomials And Real Analytic Function, Radoslaw L. Stefanski

Honors Theses

In this project, we address the question: When can a polynomial p(x, y) of two variables be factored as p(x, y) = f(x)g(y), where f and g are polynomials of one variable. We answer this question, using linear algebra, and create a Mathematica program which carries out this factorization. For example,

3+3x-5x^3+y+xy-5/3x^3y+y^2+xy^2-5/3x^3y^2 = (1+x-5/3x^3)(3+y+y^2)

We then generalize this concept and ask: When can p(x,y) can be written as

p(x,y) = f1(x)g2(y)+f2(x)g2(y)+...+fr(x)gr(y)

where fj,gj are polynomials. This can certainly be done (for large enough r). Which is the minimum such r? Again, we have a Mathematica program which carries out this …

Discovering The Potential For Advancements In Intrusion Detection Systems, Kenneth J. Buonforte

Honors Theses

An intrusion detection system (IDS) is a collection of monitors strategically placed on a network or individual host in order to detect anomalous behavior. Since James Anderson introduced one of the first frameworks for an intrusion detection system in [1]. researchers have extended the capabilities of these systems. IDSs take many forms, from systems as basic as command line audit logs to those that emulate the defense mechanisms of the human immune system. However, as intrusion detection has evolved, scientists and administrators alike are beginning to question the need for this technology due to its lack of quantifiable performance and …

Securing Distributed Computations : In Search Of Reliable Large-Scale Compute Power And Refreshed Redundancy, Edward P. Kenney

Honors Theses

The Internet may be the single largest technological advance or significant societal change in the last century. Not only does it allow access to more information than any human could ever hope to digest, but it produces the potential of having millions of computers combining their computational forces for the betterment of a single cause .. Tl is is the fundamental goal of distributed computing. A distributed system is defined to be a network of machines with some degree of centralized direction. In a distributed computational system each machine will accept computational tasks from a supervisor in a master-slave relationship. …

Pokémon® Cards And The Shortest Common Superstring, Mark Stamp, Austin Stamp

Faculty Publications, Computer Science

Evidence is presented that certain sequences of Pokémon cards are determined by selecting consecutive elements from a longer sequence. We then consider the problem of recovering the shortest common superstring (SCS), i.e., the shortest string that contains each of the Pokémon card sequences as a consecutive substring. The SCS problem arises in many applications, most notably in DNA sequencing.

Coalgebras And Modal Expansions Of Logics, Alexander Kurz, Alessandra Palmigiano

Engineering Faculty Articles and Research

In this paper we construct a setting in which the question of when a logic supports a classical modal expansion can be made precise. Given a fully selfextensional logic S, we find sufficient conditions under which the Vietoris endofunctor V on S-referential algebras can be defined and we propose to define the modal expansions of S as the logic that arises from the V-coalgebras. As an example, we also show how the Vietoris endofunctor on referential algebras extends the Vietoris endofunctor on Stone spaces. From another point of view, we examine when a category of ‘spaces’ (X,A), ie sets X …

A Comparison Of Modified Reconstructability Analysis And Ashenhurst‐Curtis Decomposition Of Boolean Functions, Anas Al-Rabadi, Marek Perkowski, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified reconstructability analysis (MRA), a novel decomposition technique within the framework of set‐theoretic (crisp possibilistic) reconstructability analysis, is applied to three‐variable NPN‐classified Boolean functions. MRA is superior to conventional reconstructability analysis, i.e. it decomposes more NPN functions. MRA is compared to Ashenhurst‐Curtis (AC) decomposition using two different complexity measures: log‐functionality, a measure suitable for machine learning, and the count of the total number of two‐input gates, a measure suitable for circuit design. MRA is superior to AC using the first of these measures, and is comparable to, but different from AC, using the second.

State-Based Reconstructability Analysis, Martin Zwick, Michael S. Johnson

Complex Systems Faculty Publications and Presentations

Reconstructability analysis (RA) is a method for detecting and analyzing the structure of multivariate categorical data. While Jones and his colleagues extended the original variable‐based formulation of RA to encompass models defined in terms of system states, their focus was the analysis and approximation of real‐valued functions. In this paper, we separate two ideas that Jones had merged together: the “g to k” transformation and state‐based modeling. We relate the idea of state‐based modeling to established variable‐based RA concepts and methods, including structure lattices, search strategies, metrics of model quality, and the statistical evaluation of model fit for analyses based …

A 2-Chain Can Interlock With A K-Chain, Julie Glass, Stefan Langerman, Joseph O'Rourke, Jack Snoeyink, Jianyuan K. Zhong

Computer Science: Faculty Publications

One of the open problems posed in [3] is: what is the minimal number k such that an open, flexible k-chain can interlock with a flexible 2-chain? In this paper, we establish the assumption behind this problem, that there is indeed some k that achieves interlocking. We prove that a flexible 2-chain can interlock with a flexible, open 16-chain.

[Introduction To] Data Structures With Java, John R. Hubbard, Anita Huray

Bookshelf

For a freshman/sophomore-level course in Data Structures in Computer Science. This text teaches the use of direct source code implementations and the use of the Java libraries; it helps students prepare for later work on larger Java software solutions by adhering to software engineering principles and techniques such as the UML and the Java Collections Framework (JCF). Using the spiral approach to cover such topics as linked structures, recursion, and algorithm analysis, this text also provides revealing illustrations, summaries, review questions, and specialized reference sections.

[Introduction To] Schaum's Outline Of Programming With Java, John R. Hubbard

Bookshelf

Tough Test Questions? Missed Lectures? Not Enough Time?

Fortunately for you, there's Schaum's Outlines. More than 40 million students have trusted Schaum's to help them succeed in the classroom and on exams. Schaum's is the key to faster learning and higher grades in every subject. Each Outline presents all the essential course information in an easy-to-follow, topic-by-topic format. You also get hundreds of examples, solved problems, and practice exercises to test your skills.

This Schaum's Outline gives you

• Practice problems with full explanations that reinforce knowledge
• Coverage of the most up-to-date developments in your course field
• In-depth review of practices …

Reversible Modified Reconstructability Analysis Of Boolean Circuits And Its Quantum Computation, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

Modified Reconstructability Analysis (MRA) can be realized reversibly by utilizing Boolean reversible (3,3) logic gates that are universal in two arguments. The quantum computation of the reversible MRA circuits is also introduced. The reversible MRA transformations are given a quantum form by using the normal matrix representation of such gates. The MRA-based quantum decomposition may play an important role in the synthesis of logic structures using future technologies that consume less power and occupy less space.

Modified Reconstructability Analysis For Many-Valued Functions And Relations, Anas Al-Rabadi, Martin Zwick

Complex Systems Faculty Publications and Presentations

A novel many-valued decomposition within the framework of lossless Reconstructability Analysis is presented. In previous work, Modified Recontructability Analysis (MRA) was applied to Boolean functions, where it was shown that most Boolean functions not decomposable using conventional Reconstructability Analysis (CRA) are decomposable using MRA. Also, it was previously shown that whenever decomposition exists in both MRA and CRA, MRA yields simpler or equal complexity decompositions. In this paper, MRA is extended to many-valued logic functions, and logic structures that correspond to such decomposition are developed. It is shown that many-valued MRA can decompose many-valued functions when CRA fails to do …

Computational Geometry Column 45, Joseph O'Rourke

Computer Science: Faculty Publications

The algorithm of Edelsbrunner for surface reconstruction by "wrapping" a set of points in R³ is described.

Gamma-Set Domination Graphs. I: Complete Biorientations Of Q-Extended Stars And Wounded Spider Graphs, Kim A. S. Factor

Mathematics, Statistics and Computer Science Faculty Research and Publications

The domination number of a graph G, γ(G), and the domination graph of a digraph D, dom(D) are integrated in this paper. The γ-set domination graph of the complete biorientation of a graph G, dom_γ(G) is created. All γ-sets of specific trees T are found, and dom-_γ(T) is characterized for those classes.

Algebraic Semantics For Coalgebraic Logics, Clemens Kupke, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

With coalgebras usually being defined in terms of an endofunctor T on sets, this paper shows that modal logics for T-coalgebras can be naturally described as functors L on boolean algebras. Building on this idea, we study soundness, completeness and expressiveness of coalgebraic logics from the perspective of duality theory. That is, given a logic L for coalgebras of an endofunctor T, we construct an endofunctor L such that L-algebras provide a sound and complete (algebraic) semantics of the logic. We show that if L is dual to T, then soundness and completeness of the algebraic semantics immediately yield the …

Preface, Thomas Hildebrandt, Alexander Kurz

Engineering Faculty Articles and Research

No abstract provided.

Modeling Of The Inverse Heat -Conduction Problem With Application To Laser Chemical Vapor Deposition And Bioheat Transfer, Peng Zhen

Doctoral Dissertations

This dissertation consists of two parts. Part one deals with three-dimensional laser induced chemical vapor deposition (3D-LCVD), whereas part two deals with a Pennes model of a 3D skin structure. LCVD is an important technique in manufacturing complex micro-structures with high aspect ratio. In part one, a numerical model was developed for simulating kinetically-limited growth of an axisymmetric cylindrical rod by pre-specifying the surface temperature distribution required for growing the rod and then by obtaining optimized laser power that gives rise to the pre-specified temperature distribution. The temperature distribution at the surface of the rod was assumed to be at …

Using Reconstructability Analysis To Select Input Variables For Artificial Neural Networks, Stephen Shervais, Martin Zwick

Complex Systems Faculty Publications and Presentations

We demonstrate the use of Reconstructability Analysis to reduce the number of input variables for a neural network. Using the heart disease dataset we reduce the number of independent variables from 13 to two, while providing results that are statistically indistinguishable from those of NNs using the full variable set. We also demonstrate that rule lookup tables obtained directly from the data for the RA models are almost as effective as NNs trained on model variables.

Open Problems From Cccg 2002, Erik D. Demaine, Joseph O'Rourke

Computer Science: Faculty Publications

No abstract provided.

Flow And Pressure Distributions In Vascular Networks Consisting Of Distensible Vessels, Gary S. Krenz, Christopher A. Dawson

Mathematics, Statistics and Computer Science Faculty Research and Publications

We examine the influence of vessel distensibility on the fraction of the total network flow passing through each vessel of a model vascular network. An exact computational methodology is developed yielding an analytic proof. For a class of structurally heterogeneous asymmetric vascular networks, if all the individual vessels share a common distensibility relation when the total network flow is changed, this methodology proves that each vessel will continue to receive the same fraction of the total network flow. This constant flow partitioning occurs despite a redistribution of pressures, which may result in a decrease in the diameter of one and …

Sos Checks And Career Management, Russell W. Howell

ACMS Conference Proceedings 2003

This paper compares the careers of King Saul and King David in the Bible and how they inform the career management methods of a Christian.

A Christian Appraisal Of Stephan Wolfram's A New Kind Of Science, Gene B. Chase

ACMS Conference Proceedings 2003

Wolfram exposes some ideas about informatics that relate to Christian Scholarship: Does Wolfram's definition of free will permit God to have free will? Will human souls resurrected to a new body–as described by St. Paul and Aquinas–by like software that is moved to new hardware? Jesus' incarnation as in-form-ation in the Aristotelian sense.

Linear Regression As A 1-Variable Optimization Exercise, Ken Constantine

ACMS Conference Proceedings 2003

Derivation of the least squares line for a set of bivariate data entails minimizing a function of two variables, say the line's slope and intercept. Imposing the requirement that the line pass through the mean point for the data reduces this problem to a 1-variable problem easily solved as a single-variable Calculus exercise. The solution to this problem is, in fact, the solution to the more general problem. We illustrate with a dataset involving charitable donations.