Computer Sciences Commons^™

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.

Type 3 Diminimal Maps On The Torus, Adrian Riskin

Mathematics

A polyhedral map on the torus is diminimal if either shrinking or removing an edge yields a nonpolyhedral map. We show that all such maps on the torus fall into one of two classes, type 2 and type 3, and show that there are exactly two type 3 ones, which are given explicitly.

Selection Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies $n$ values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)

Supereuleriaun Graphs And The Petersen Graph, Zhi-Hong Chen

Scholarship and Professional Work - LAS

Using a contraction method, we find some best-possible sufficient condi­tions for 3-edge-connected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

Estimation In A Marked Poisson Error Recapture Model Of Software Reliability, Rajan Gupta

Mathematics & Statistics Theses & Dissertations

Nayak's (1988) model for the detection, removal, and recapture of the errors in a computer program is extended to a larger family of models in which the probabilities that the successive programs produce errors are described by the tail probabilities of discrete distribution on the positive integers. Confidence limits are derived for the probability that the final program produces errors. A comparison of the asymptotic variances of parameter estimates given by the error recapture and by the repetitive-run procedure of Nagel, Scholz, and Skrivan (1982) is made to determine which of these procedures efficiently uses the test time.

Shadow Casting Phenomena At Newgrange, Frank Prendergast

Articles

A digital model of the Newgrange passage tomb and surrounding ring of monoliths known as the Great Circle is used to investigate sunrise shadow casting phenomena at the monument. Diurnal variation in shadow directions and lengths are analysed for their potential use in the Bronze Age to indicate the passage of seasonal time. Computer-aided simulations are developed from a photogrammetric survey to accurately show how three of the largest monoliths, located closest to the tomb entrance and archaeologically coded GC1, GC-1 and GC-2, cast their shadows onto the vertical face of the entrance kerbstone, coded K1. The phenomena occur at …

Intelligent Structural Operators For The K-Way Graph Partitioning Problem, Gregor Von Laszewski

Northeast Parallel Architecture Center

A parallel genetic algorithm for the graph partitioning problem is presented, which combines general heuristic algorithms with techniques that are described in evolution theory. In the parallel genetic algorithm the selection of a mate is restricted to a local neighborhood. In addition, the parallel genetic algorithm executes an adaptation step after an individual is generated, with the genetic operators crossover and mutation. During the adaptation step the solution is improved by a common algorithm. Another selection step decides if the adapted descendant should replace the parent individual. Instead of using a uniform crossover operator a more intelligent crossover operator, which …

Notions Of Relative Ubiquity For Invariant Sets Of Relational Structures, Paul Bankston, Wim Ruitenburg

Mathematics, Statistics and Computer Science Faculty Research and Publications

Given a finite lexicon L of relational symbols and equality, one may view the collection of all L-structures on the set of natural numbers w as a space in several different ways. We consider it as: (i) the space of outcomes of certain infinite two-person games; (ii) a compact metric space; and (iii) a probability measure space. For each of these viewpoints, we can give a notion of relative ubiquity, or largeness, for invariant sets of structures on w. For example, in every sense of relative ubiquity considered here, the set of dense linear orderings on w is …

An Artificial Neural Approach To The Decomposition Problem, Chandrashekar L. Masti

Electrical & Computer Engineering Theses & Dissertations

The goal of this thesis is to develop an artificial neural approach toward addressing the intractability involved with the decomposition problem. The search for the lattice of substitution property (s. p.) partitions essential to decompositions is cast into the framework of constraint satisfaction. An artificial neural network is developed to provide solutions by performing optimization of a mathematically derived objective function over the problem space. The issue of transitivity is verified to belong to a class of problems beyond the scope of solvability for conventional quadratic-order constraint satisfaction neural networks. A theorem is stated and proved establishing that third-order correlations …

Taxonomies Of Model-Theoretically Defined Topological Properties, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

A topological classification scheme consists of two ingredients: (1) an abstract class K of topological spaces; and (2) a "taxonomy", i.e. a list of first order sentences, together with a way of assigning an abstract class of spaces to each sentence of the list so that logically equivalent sentences are assigned the same class.K, is then endowed with an equivalence relation, two spaces belonging to the same equivalence class if and only if they lie in the same classes prescribed by the taxonomy. A space X in K is characterized within the classification scheme if whenever Y _{E …}

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 …

Faster Circuits And Shorter Formulas For Multiple Addition, Multiplication And Symmetric Boolean Functions, Michael Paterson, Uri Zwick, Nicholas Pippenger

All HMC Faculty Publications and Research

A general theory is developed for constructing the shallowest possible circuits and the shortest possible formulas for the carry-save addition of n numbers using any given basic addition unit. More precisely, it is shown that if BA is a basic addition unit with occurrence matrix N, then the shortest multiple carry-save addition formulas that could be obtained by composing BA units are of size n1p+o(1)/, where p is the unique real number for which the Lp norm of the matrix N equals 1. An analogous result connects the delay matrix M of the basic addition unit BA and the minimal …

Simulated Annealing On Np-Complete Problems, Russell W. Howell

ACMS Conference Proceedings 1989

The Random House Dictionary defines anneal as " ... to free (glass, metals, etc.) from internal stress by heating and gradually cooling." In the physical world, impurities are annealed out of a substance by heating it to a high temperature. As it is cooled, its molecular structure gradually settles into a stable "low-energy" configuration. It is important to cool the substance slowly, especially at lower temperatures, so that impurities do not get "frozen" into place. With careful cooling, a low-energy state can eventually be reached. This state may not be the one with the lowest potential energy, where the spins …

The Mathematical Intelligencer, Dmitrii Egorov: Mathematics And Theology In Russia, Charles E. Ford

ACMS Conference Proceedings 1989

This paper tells the story of Russian mathematician Dmitri Egorov, recounting his faith and contributions to the field of mathematics.

A Course On Mathematics And The Christian Faith, W. David Laverell, Carl J. Sinke

ACMS Conference Proceedings 1989

The January interim term at Calvin College provides an opportunity for developing and teaching courses outside a normal major program. As a result faculty members are frequently given the interim off to provide time for research and development of new courses. In 1987 we were given such a leave in order to pursue the questions of the relationship between mathematics and the Christian Faith. One result was our presentation at the 1987 Association of Christians in the Mathematical Sciences conference. Immediately thereafter we began to develop a specific interim course based on our studies. We offered the course during the …

The Bisexual Galton-Watson Branching Process, David M. Hull

ACMS Conference Proceedings 1989

I would like to present the bisexual Galton-Watson branching process. The word "bisexual" indicates that we will be considering a population of two sexes--which will be designated as the usual male and female. Here is a brief overview of what I would like to cover.

1. The bisexual process motivated: why is it needed?
2. The standard Galton-Watson branching process.
3. The state of affairs regarding two-sex models.
4. The nuts and bolts of the bisexual Galton-Watson branching process (parameters defined and how it works).
5. A review of published bisexual results to date.
6. What is to come?

Newton And Saccheri: Case Studies In The Interplay Of Mathematics And Religion, Tommy Leavelle

ACMS Conference Proceedings 1989

In the course of this paper I will try to present to you the basic facts and some of the subsequent assessments of the life and work of two mathematicians for whom the interplay of mathematics and religion was influential: Issac Newton and Girolamo Saccheri.

Augustine's Mathematical Realism, Paul J. Zwier

ACMS Conference Proceedings 1989

After a review of Philip Kitcher's argument against Mathematical Realism, this paper presents the case for Mathematical Realism by looking at the life and writings of Saint Augustine.

Beauty In Mathematics: Some Theological Implications, David L. Neuhouser

ACMS Conference Proceedings 1989

It may come as a surprise to some that science or mathematics could be considered beautiful, but many prominent sciences and mathematicians from around the world have made such claims. Furthermore, the beauty of mathematics and order of the universe inspired some of the greatest developments in science and mathematics. This paper examines the beauty of mathematics and what scientists and other individuals have said about the subject.

Using Writing In The Mathematics Classroom, Dr. Barbara J. Rose

ACMS Conference Proceedings 1989

No abstract provided.

Mathematics Between The Lines Of Ecclesiates, Donald A. Joesphson

ACMS Conference Proceedings 1989

No abstract provided.

Writing Across The Curriculum Using Statistics, Carlos A. Pereira

ACMS Conference Proceedings 1989

No abstract provided.

Written Assignments In College Freshman And Sophomore Mathematics Courses, Jean Alliman

ACMS Conference Proceedings 1989

No abstract provided.

Mathematical Modeling In The Classroom, Jefferson Hartzler

ACMS Conference Proceedings 1989

No abstract provided.

The Fourth Dimension And The Theology Of Edwin Abbot Abbott, Thomas F. Banchoff

ACMS Conference Proceedings 1989

No abstract provided.

Schedule (1989), Association Of Christians In The Mathematical Sciences

ACMS Conference Proceedings 1989

A Seventh Conference on Mathematics from a Christian Perspective

Gene B. Chase, Editor

Introduction (1989), Gene B. Chase

ACMS Conference Proceedings 1989

A Seventh Conference on Mathematics from a Christian Perspective

Gene B. Chase, Editor

Table Of Contents (1989), Association Of Christians In The Mathematical Sciences

ACMS Conference Proceedings 1989

A Seventh Conference on Mathematics from a Christian Perspective

Gene B. Chase, Editor

The Fourth Dimension And The Theology Of Edwin Abbott Abbott, Thomas Banchoff

ACMS Conference Proceedings 1989

This paper is a brief biography of Edwin Abbott Abbott, author of Flatland, and a sketch of the main ideas in the book. It also incorporates some personal reflections.

Isometries Homotopic To The Identity, Douglas A. Norris

Mathematics and Computer Science

The types of surfaces which admit nontrivial isometries homotopic to the identity are classified up to diffeomorphism. In dimension three this is done for complete manifolds of constant negative curvature. Three-dimensional visibility manifolds that admit nontrivial isometries homotopic to the identity are shown to be diffeomorphic to a product L x RI.