Mathematics Commons^™

Computational Geometry Column 35, Joseph O'Rourke

Computer Science: Faculty Publications

The subquadratic algorithm of Kapoor for finding shortest paths on a polyhedron is described.

Locked And Unlocked Polygonal Chains In 3d, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark Overmars, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides

Computer Science: Faculty Publications

In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a …

Codes, Correlations And Power Control In Ofdm, James A. Davis, Jonathan Jedwab, Kenneth G. Paterson

Department of Math & Statistics Faculty Publications

Practical communications engineering is continually producing problems of interest to the coding theory community. A recent example is the power-control problem in Orthogonal Frequency Division Multiplexing (OFDM). We report recent work which gives a mathematical framework for generating solutions to this notorious problem that are suited to low-cost wireless applications. The key result is a connection between Golay complementary sequences and Reed-Muller codes. The former are almost ideal for OFDM transmissions because they have a very low peak-to-mean envelope power ratio (PMEPR), while the latter have efficient encoding and decoding algorithms and good error correction capability. This result is then …

(Ω, Ξ)-Logic: On The Algebraic Extension Of Coalgebraic Specifications, Rolf Hennicker, Alexander Kurz

Engineering Faculty Articles and Research

We present an extension of standard coalgebraic specification techniques for statebased systems which allows us to integrate constants and n-ary operations in a smooth way and, moreover, leads to a simplification of the coalgebraic structure of the models of a specification. The framework of (Ω,Ξ)-logic can be considered as the result of a translation of concepts of observational logic (cf. [9]) into the coalgebraic world. As a particular outcome we obtain the notion of an (Ω, Ξ)- structure and a sound and complete proof system for (first-order) observational properties of specifications.

Fan-Type Conditions For Collapsible Graphs, Zhi-Hong Chen

Scholarship and Professional Work - LAS

No abstract provided.

Octary Codewords With Power Envelopes Of 3∗2M, Katherine M. Nieswand, Kara N. Wagner

Department of Math & Statistics Technical Report Series

This paper examines codewords of length 2^m in Z₈ with envelope power maxima of 3 ∗ 2^m. Using the general form for Golay pairs as a base, a general form is derived for the set of coset leaders that generate these codewords. From this general form it will be proven that there exists at least one element in the coset that achieves a power of 3 ∗ 2^m for each m-even and m-odd case.

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, …

Coupled Electrodynamic-Monte Carlo Simulations Of Nanoscale Gaas Terahertz Optical Mixers, Jiang Li

Electrical & Computer Engineering Theses & Dissertations

The concept of mixing or heterodyning has traditionally been used for microwaves and for radio frequency communications. However, the concept can easily be extended into the optical frequency regime. By doing so, the photomixing process can serve as a very versatile tool for both the generation of ultrahigh frequency (terahertz) and the detection of weak optical signals.

The aim of this thesis is to perform a theoretical study of the photomixing process inside GaAs devices as the non-linear elements. A coupled approach which combines the Monte Carlo simulation scheme for the carrier transport, with Maxwell's equation for the electrodynamics, has …

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), …

Computational Geometry Column 33, Joseph O'Rourke

Computer Science: Faculty Publications

Several recent SIGGRAPH papers on surface simplification are described.

The Dirichlet Problem And Its Physical Motivations, Andrew E. Pitts

Honors Theses

In this work, we explore the basics of harmonic function theory and its relationship to problems in the theory of heat diffusion. In particular, we will focus on the classical Dirichlet problem.

Problems In Harmonic Function Theory, Ronald A. Walker

Honors Theses

Harmonic Function Theory is a field of differential mathematics that has both many theoretical constructs and physical connections, as well as its store of classical problems.

One such problem is the Dirichlet Problem. While the proof of the existence of a solution is well-founded on basic theory, and general methods for polynomial solutions have been well studied, much ground is still yet to be overturned. In this paper we focus on the examination, properties and computation methods and limitations, of solutions for rational boundary functions.

Another area that we shall study is the properties and generalizations of the zero sets …

Average-Case Lower Bounds For Noisy Boolean Decision Trees, William Evans, Nicholas Pippenger

All HMC Faculty Publications and Research

We present a new method for deriving lower bounds to the expected number of queries made by noisy decision trees computing Boolean functions. The new method has the feature that expectations are taken with respect to a uniformly distributed random input, as well as with respect to the random noise, thus yielding stronger lower bounds. It also applies to many more functions than do previous results. The method yields a simple proof of the result (previously established by Reischuk and Schmeltz) that almost all Boolean functions of n arguments require $\Me(n \log n)$ queries, and strengthens this bound from the …

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 …

Computational Geometry Column 34, Pankaj K. Agarwal, Joseph O'Rourke

Computer Science: Faculty Publications

Problems presented at the open-problem session of the 14th Annual ACM Symposium on Computational Geometry are listed.

On Circulant Weighing Matrices, K. T. Arasu, Jennifer Seberry

Mathematics and Statistics Faculty Publications

Algebraic techniques are employed to obtain necessary conditions for the existence of certain circulant weighing matrices. As an application we rule out the existence of many circulant weighing matrices. We study orders n = 82 +8+1, for 10 ~ 8 ~ 25. These orders correspond to the number of points in a projective plane of order 8.

[Introduction To] Schaum's Outlines Fundamentals Of Computing With C++, John R. Hubbard

Bookshelf

This book is intended to be used primarily for self study, preferably in conjunction with a regular course in the fundamentals of computer science using the new ANSI/ISO Standard C++. The book covers topics from the fundamental units of the 1991 A.C.M. computing curricula.

Computational Geometry Column 32, Joseph O'Rourke

Computer Science: Faculty Publications

The proof of Dey's new k-set bound is illustrated.

Complexity And Decomposability Of Relations, Martin Zwick

Complex Systems Faculty Publications and Presentations

A discrete multivariate relation, defined set-theoretically, is a subset of a cartesian product of sets which specify the possible values of a number of variables. Where three or more variables are involved, the highest order relation, namely the relation between all the variables, may or may not be decomposable without loss into sets of lower order relations which involve subsets of the variables. In a completely parallel manner, the highest order relation defined information-theoretically, namely the joint probability distribution involving all the variables, may or may not be decomposed without loss into lower-order distributions involving subsets of the variables. Decomposability …

Using The Quantum Computer To Break Elliptic Curve Cryptosystems, Jodie Eicher, Yaw Opoku

Department of Math & Statistics Technical Report Series

This article gives an introduction to Elliptic Curve Cryptography and Quantum Computing. It includes an analysis of Peter Shor’s algorithm for the quantum computer breakdown of Discrete Log Cryptosystems and an analog to Shor’s algorithm for Elliptic Curve Cryptosystems. An extended example is included which illustrates how this modified Shor’s algorithm will work.

Solomon's Sea And The Biblical Π, Andrew Simoson

ACMS Conference Proceedings 1997

From I Kings 7:23, the apparent diameter and circumference of a circular ring are given as 10 and 30 cubits which suggests that the Biblical value of π is 3 rather a number closer to π. However we recount seven different somewhat whimsical explanations as to why this conclusion is overly-hasty.

Mathematics And Values: Can Philosophy Guide Projects?, Michael H. Veatch

ACMS Conference Proceedings 1997

The philosophy of mathematics has provided insight on questions of foundations and mathematical truth; however, it has not been very fruitful in guiding the practice of mathematics. This paper attempts to find points of contact between a Christian worldview and the choice of mathematical projects and methods. Three areas are considered: (i) dubitability in current research, (ii) the intrinsic value of contemporary mathematics to contemporary society, and (iii) the affirmation of human value in the use of mathematics. Finally, a framework for valuing mathematics is proposed as an encouragement to think more deeply about how a Christian might choose a …

An Investigation Of The Behavior Of Calculus Students Working Collaboratively In An Interactive Software Environment, Angela Hare

ACMS Conference Proceedings 1997

Recent work in the area of cognitive research in mathematics education focuses on detailed examinations of the learning process of students and how this process is affected by current innovations in the classroom, including collaborative learning and the use of computers and interactive software. Much of this work is supported by the learning framework of constructivism, a school of thought which is based on the work and writings of Jean Piaget. Piaget, a French psychologist in the mid-twentieth century, observed the learning behavior of children and concluded that individuals construct their own knowledge by creating mental structures which explain their …

Mathematics At Chartres Cathedral, Richard Stout

ACMS Conference Proceedings 1997

Having had several opportunities to travel to France, often with groups of students, our trips have usually included a visit to Chartres, especially to visit the magnificent Gothic cathedral that dominates the town. On a recent visit I was again struck by the beauty, majesty and awe that the cathedral inspires. The building not only does a remarkable job of telling Biblical stories and of enclosing a space conducive to worship, it directs one's eyes and one's spirits upward. This is achieved not only by the beautiful stained glass windows and the striking sculptures, but also by the overall design …

Digital Filtering And Smoothing: A Student Simulation Project, Eric Gossett

ACMS Conference Proceedings 1997

A bug tracking problem is used to introduce students to filtering and smoothing real-time data. A predictor-corrector filter/smoother algorithm is developed and a simulation platform is provided so that students can program and test implementations of the filter/smoother. The platform includes the ability to animate the simulation.

The tracking problem: A small computer bug is traveling around the $x-y$ plane trying to avoid detection. We can eliminate the bug if we can produce a reasonably accurate approximation to its trajectory.

We have a bug detecting device which can be pointed at the plane. It can measure the $x$ and $y$ …

The Role Of Mathematics In Culture, W. James Bradley

ACMS Conference Proceedings 1997

This paper examines theories of the role of mathematics in culture and seeks to understand how a Christian should view the role of mathematics.

The Mathematical Sciences And The Mediator Of Creation, W. David Laverell

ACMS Conference Proceedings 1997

This article stems from a conviction that while the development of a theistic view of the mathematical sciences is a laudable goal and much to be encouraged, it is incumbent upon us to explore every avenue that might lead to a distinctively Christian perspective. This leads naturally to a consideration of the unique role played by Christ in Creation, and a convenient framework is provided by seeing Christ as Mediator of Creation. We shall discuss the term itself, examine the biblical passages that seem to present the concept, consider the ways these passages have been understood by theologians, and …

Fractal Geometry And Chaos Theory: From Old Problems To New Models And Methods, Terence H. Perciante

ACMS Conference Proceedings 1997

Fractal geometry and chaos theory are deeply rooted in significant problems in the history of mathematics and science. While mathematicians have geometrical descriptions of space with its properties, scientists have attempted to characterize the physical properties of fundamental entities present in space and time. The separate investigations frequently influenced each other and led to profound theories, answers, and models. However, at the same time new problems repeatedly arose internal to mathematics and externally in the applications to which mathematics was applied. Fractal geometry issues from these antecedents in response to features and processes in nature not easily represented by historical …

Teaching Generalization And Reduction Through An Elementary Probability Problem, Erian Wheeler

ACMS Conference Proceedings 1997

No abstract provided.

On Binary Quadratic Forms, Alain Togbe

ACMS Conference Proceedings 1997

No abstract provided.