Computer Sciences Commons^™

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 …

[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.

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.

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.

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.

Exploring Various Methods Of Interpolation, Mark Roberts

ACMS Conference Proceedings 1997

No abstract provided.

Hypothesis, Proof, And Censorship Or How Galileo Changed The Rules Of Science, Owen Gingerich

ACMS Conference Proceedings 1997

No abstract provided.

Hyperbolic Geometry With The Geometer's Sketchpad, Robert Frank

ACMS Conference Proceedings 1997

No abstract provided.

Using Java And Html For Linear Algebra Instruction, Jonathan R. Senning

ACMS Conference Proceedings 1997

This paper addresses some of the issues involved with using the HTML, JavaScript and Java to develop and serve a sequence of laboratory modules for use in teaching linear algebra. Attention is paid to the rationale for this approach as opposed to the more traditional approach of laboratory exercises executed using MATLAB or some similar computational tool. Several methods to display mathematics with HTML are described. Some implementation detail and a brief description of the HTML and Java based Linear Algebra Visualization Assistant (LAVA) is presented.

A Tale Of Two Transitions, David Klanderman, Sharon Robbert, Robert Wheeler

ACMS Conference Proceedings 1997

In this paper, we examine transitions to proof courses at two institutions. Bob Wheeler has taught the course at Northern Illinois University. Both Sharon Robbert and Dave Klanderman have taught a related course at Trinity Christian College. We analyze various features of these courses and offer suggestions for other colleges and universities.

History And Current Situation Of Russian Church, Ioann S. Goncharov, Gennadiy A. Kalyabin

ACMS Conference Proceedings 1997

This paper brief outlines the main periods in Russia's Orthodoxy including latest seven decades. In the Appendix a mathematical model is proposed for explaining the Divine Features such as Omniscience, Omnipotence, Predestination, and the free will of men.

A First Draft Of The History Of Acms, Robert Brabenec

ACMS Conference Proceedings 1997

This paper is a draft of the history of the Association of Christians in the Mathematical Sciences as told by Robert Brabenec.

Introduction (1997), Association Of Christians In The Mathematical Sciences

ACMS Conference Proceedings 1997

Eleventh ACMS Conference on Mathematics from a Christian Perspective

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

ACMS Conference Proceedings 1997

Eleventh ACMS Conference on Mathematics from a Christian Perspective

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

ACMS Conference Proceedings 1997

Eleventh ACMS Conference on Mathematics from a Christian Perspective

Celluloid Blackness : Race, Modernity, And The Conflicted Roots Of American Cinema (1915-1939), Lincoln Farr

Honors Theses

Introduction: "The Problem of the Twentieth Century" In a full page interview in the New York Times on May 29, 1912, the Swiss psychiatrist Dr. Carl G. Jung told the American people, "It seems to me that you are about to discover yourselves. You have discovered everything else-all the land of this continent; all the resources, all the hidden things of nature."Jung used the interview to address the American people, at a moment which he somehow recognized as crucial in the development of human civilization. America, the "tragic" country which he struggled to comprehend, would soon become the harbinger of …

On Some New Constructions Of Difference Sets, Sarah Agnes Spence

Honors Theses

Difference sets are mathematical structures which arise in algebra and combinatorics, with applications in coding theory. The fundamental question is when and how one can construct difference sets. This largely expository paper looks at standard construction methods and describes recent findings that resulted in new families of difference sets. This paper provides explicit examples of difference sets that arise from the recent constructions. By gaining a thorough understanding of these new techniques, it may be possible to generalize the results to find additional new families of difference sets. The paper also introduces partial and relative difference sets and discusses how …