Mathematics Commons^™

Rush Hour® And Dijkstra’S Algorithm, Mark Stamp, Brad Engel, Mcintosh Ewell, Victor Morrow

Faculty Publications, Computer Science

The game of Rush Hour® includes a 6 × 6 grid and game pieces representing cars and trucks. The object of the puzzle is to move a special car out of a gridlocked “traffic jam.” In this note we apply Dijkstra’s algorithm and a breadth-first search to solve any Rush Hour configuration.

Efficient Algorithms For Graphs With Few P-4’S, Luitpold Babel, Ton Kloks, Jan Kratochvíl, Dieter Kratsch, Kaiko Müller, Stephan Olariu

Computer Science Faculty Publications

We show that a large variety of NP-complete problems can be solved efficiently for graphs with 'few' P₄'s. We consider domination problems (domination, total domination, independent domination. connected domination and dominating clique), the Steiner tree problem, the vertex ranking problem, the pathwidth problem, the path cover number problem, the hamiltonian circuit problem, the list coloring problem and the precoloring extension problem. We show that all these problems can be solved in linear time for the class of (q,q - 4)-graphs, for every fixed q. These are graphs for which no set of at most q. vertices induces more …

Computational Geometry Column 40, Joseph O'Rourke

Computer Science: Faculty Publications

It has recently been established by Below, De Loera, and Richter-Gebert that finding a minimum size (or even just a small) triangulation of a convex polyhedron is NP-complete. Their 3SAT-reduction proof is discussed.

On Reconfiguring Tree Linkages: Trees Can Lock, Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Steve Robbins, Ileana Streinu, Godfried Toussaint, Sue Whitesides

Computer Science: Faculty Publications

It has recently been shown that any simple (i.e. nonintersecting) polygonal chain in the plane can be reconfigured to lie on a straight line, and any simple polygon can be reconfigured to be convex. This result cannot be extended to tree linkages: we show that there are trees with two simple configurations that are not connected by a motion that preserves simplicity throughout the motion. Indeed, we prove that an N-link tree can have 2^Ω(N) equivalence classes of configurations.

Pushpush And Push-1 Are Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke

Computer Science: Faculty Publications

We prove that two pushing-blocks puzzles are intractable in 2D. One of our constructions improves an earlier result that established intractability in 3D [OS99] for a puzzle inspired by the game PushPush. The second construction answers a question we raised in [DDO00] for a variant we call Push-1. Both puzzles consist of unit square blocks on an integer lattice; all blocks are movable. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover when a …

Computational Geometry Column 39, Joseph O'Rourke

Computer Science: Faculty Publications

The resolution of a decades-old open problem is described: polygonal chains cannot lock in the plane.

Examples, Counterexamples, And Enumeration Results For Foldings And Unfoldings Between Polygons And Polytopes, Erik D. Demaine, Martin L. Demaine, Anna Lubiw, Joseph O'Rourke

Computer Science: Faculty Publications

We investigate how to make the surface of a convex polyhedron (a polytope) by folding up a polygon and gluing its perimeter shut, and the reverse process of cutting open a polytope and unfolding it to a polygon. We explore basic enumeration questions in both directions: Given a polygon, how many foldings are there? Given a polytope, how many unfoldings are there to simple polygons? Throughout we give special attention to convex polygons, and to regular polygons. We show that every convex polygon folds to an infinite number of distinct polytopes, but that their number of combinatorially distinct gluings is …

Some Applications Of The Ultrapower Theorem To The Theory Of Compacta, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

The ultrapower theorem of Keisler and Shelah allows such model-theoretic notions as elementary equivalence, elementary embedding and existential embedding to be couched in the language of categories (limits, morphism diagrams). This in turn allows analogs of these (and related) notions to be transported into unusual settings, chiefly those of Banach spaces and of compacta. Our interest here is the enrichment of the theory of compacta, especially the theory of continua, brought about by the importation of model-theoretic ideas and techniques.

Computational Geometry Column 38, Joseph O'Rourke

Computer Science: Faculty Publications

Recent results on curve reconstruction are described.

An Object-Oriented Algorithmic Laboratory For Ordering Sparse Matrices, Gary Karl Kumfert

Computer Science Theses & Dissertations

We focus on two known NP-hard problems that have applications in sparse matrix computations: the envelope/wavefront reduction problem and the fill reduction problem. Envelope/wavefront reducing orderings have a wide range of applications including profile and frontal solvers, incomplete factorization preconditioning, graph reordering for cache performance, gene sequencing, and spatial databases. Fill reducing orderings are generally limited to—but an inextricable part of—sparse matrix factorization.

Our major contribution to this field is the design of new and improved heuristics for these NP-hard problems and their efficient implementation in a robust, cross-platform, object-oriented software package. In this body of research, we (1) examine …

Computational Geometry Column 37, Erik D. Demaine, Joseph O'Rourke

Computer Science: Faculty Publications

Open problems from the 15th Annual ACM Symposium on Computational Geometry.

Pushpush Is Np-Hard In 2d, Erik D. Demaine, Martin L. Demaine, Joseph O'Rourke

Computer Science: Faculty Publications

We prove that a particular pushing-blocks puzzle is intractable in 2D, improving an earlier result that established intractability in 3D [OS99]. The puzzle, inspired by the game *PushPush*, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 2D by reduction from SAT.

Design Early Considered Harmful: Graduated Exposure To Complexity And Structure Based On Levels Of Cognitive Development, Duane Buck, David J. Stucki

Mathematics Faculty Scholarship

We have recognized that the natural tendency to teach according to the structure of one’s own understanding runs contrary to established models of cognitive development. Bloom’s Taxonomy has provided a basis for establishing a more efficacious pedagogy. Emphasizing a hierarchical progression of skill sets and gradual learning through example, our approach advocates teaching software development from the inside/out rather than beginning with either console apps or monolithic designs.

A Primer For Applying Service Learning To Computer Science, Pete Sanderson, Kenneth Vollmar

Mathematics Faculty Scholarship

Service learning is an educational philosophy that promotes active learning through community service. We have recently applied this approach in our computer science curriculum, specifically to our software engineering course. In order that other computer science departments can benefit from our experience, we have developed a primer one can follow to establish a program for service learning in the computer sciences. We also describe and assess our experience after one year of applying service learning to software engineering.

Notes On Coalgebras, Cofibrations And Concurrency, Alexander Kurz, Dirk Pattinson

Engineering Faculty Articles and Research

We consider categories of coalgebras as (co)-fibred over a base category of parameters and analyse categorical constructions in the total category of deterministic and non-deterministic coalgebras.

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 …

[Introduction To] Mathematics Calculus Bc, John R. Hubbard, David R. Arterburn, Michael A. Perl

Bookshelf

This book gives you the tools to prepare effectively for the Advanced Placement Examination in Mathematics: Calculus BC. These tools include a concise topical review and six full-length practice tests. Our review succinctly covers areas considered most relevant to this exam. Following each of our tests is an answer key complete with detailed explanations designed to clarify the material for you.

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

Complex Systems Faculty Publications and Presentations

Reconstructability analysis (RA) is a method for detecting and analyzing the structure of multivariate categorical data. Jones and his colleagues extended the original variable-based formulation of RA to encompass models defined in terms of system states (Jones 1982; Jones 1985; Jones 1985; Jones 1986; Jones 1989). In this paper, we demonstrate that Jones’ previous work comprises two separable ideas: the “g to k” transformation and state-based modeling. We relate the concept of state-based modeling to established variable-based RA methods (Klir 1985; Krippendorff 1986), and demonstrate that statebased modeling, when applied to event and decision tree models, is a valuable adjunct …

[Introduction To] Schaum's Outline Programming With C++, 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 …

A Hierarchy Of Maps Between Compacta, Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

Let CH be the class of compacta (i.e., compact Hausdorff spaces), with BS the subclass of Boolean spaces. For each ordinal α and pair $\langle K,L\rangle$ of subclasses of CH, we define Lev_≥α K,L), the class of maps of level at least α from spaces in K to spaces in L, in such a way that, for finite α, Lev_≥α (BS,BS) consists of the Stone duals of Boolean lattice embeddings that preserve all prenex first-order formulas of quantifier rank α. Maps of level ≥ 0 are just the continuous surjections, and the maps of level ≥ 1 are …

Computational Geometry Column 36, Joseph O'Rourke

Computer Science: Faculty Publications

Two results in "computational origami" are illustrated.

Pushpush Is Np-Hard In 3d, Joseph O'Rourke, The Smith Problem Solving Group

Computer Science: Faculty Publications

We prove that a particular pushing-blocks puzzle is intractable in 3D. The puzzle, inspired by the game PushPush, consists of unit square blocks on an integer lattice. An agent may push blocks (but never pull them) in attempting to move between given start and goal positions. In the PushPush version, the agent can only push one block at a time, and moreover, each block, when pushed, slides the maximal extent of its free range. We prove this version is NP-hard in 3D by reduction from SAT. The corresponding problem in 2D remains open.

Evaluating Maximum Likelihood Estimation Methods To Determine The Hurst Coefficient, Christina Marie Kendziorski, J. B. Bassingthwaighte, Peter J. Tonellato

Mathematics, Statistics and Computer Science Faculty Research and Publications

A maximum likelihood estimation method implemented in S-PLUS (S-MLE) to estimate the Hurst coefficient (H) is evaluated. The Hurst coefficient, with 0.5<HS-MLE was developed to estimate H for fractionally differenced (fd) processes. However, in practice it is difficult to distinguish between fd processes and fractional Gaussian noise (fGn) processes. Thus, the method is evaluated for estimating H for both fd and fGn processes. S-MLE gave biased results of H for fGn processes of any length and for fd processes of lengths less than 2¹⁰. A modified method is proposed to correct for …

Zero-Parity Stabbing Information, Joseph O'Rourke, Irena Pashchenko

Computer Science: Faculty Publications

Everett et al. [EHN96, EHN97] introduced several varieties of stabbing information for the lines determined by pairs of vertices of a simple polygon P, and established their relationships to vertex visibility and other combinatorial data. In the same spirit, we define the “zero-parity (ZP) stabbing information” to be a natural weakening of their “weak stabbing information,” retaining only the distinction among {zero, odd, even > 0} in the number of polygon edges stabbed. Whereas the weak stabbing information’s relation to visibility remains an open problem, we completely settle the analogous questions for zero parity information, with three results: (1) ZP information …

Tracking The Trochoid On Safari, Andrew Simoson

ACMS Conference Proceedings 1999

While on sabbatical in Dar es Salaam in 1997–98, I was tasked to be the department’s seminar director and discovered that a dearth of speakers roam about in east Africa; so I opted to set up a lecture tour for myself to include Zambia, Zimbabwe, and Botswana as well as Tanzania—and spoke about the envelope of curves generated by a series of line segments obtained when two runners attached by an ideal bungee cord (the line segments) proceed about a circular track. Herein we describe life in east Africa and show that those envelopes are trochoids.

Revolutions In Mathematics (Book Review), Kevin Vander Meulen

ACMS Conference Proceedings 1999

A review of Revolutions in Mathematics, edited by Donald Gillies, Clarendon Press, Oxford 1992.

Lewis Carroll: Author, Mathematician, And Christian, David L. Neuhouser

ACMS Conference Proceedings 1999

Although a Christian, an author, and a mathematician, Charles Letwidge Dodgson (better known as Lewis Carroll) wrote very few works in which these three aspects of his person was present. The only examples of him merging these interests are in Sylvie and Bruno and Sylvie and Bruno Concluded. This paper will explore what motivated him to make these works and whether or not they were successful.

The Deconstruction Of Mathematics, David J. Stucki

ACMS Conference Proceedings 1999

This paper is a criticism of Reuben Hersh's What is Mathematics, Really? and the humanist philosophy of mathematics.

Book Review, David J. Stucki

ACMS Conference Proceedings 1999

A book review of Fashionable Nonsense: Postmodern Intellectuals' Abuse of Science by Alan Sokal and Jean Bricmont.

Book Review: Virtual Gods: The Seduction Of Power And Pleasure In Cyberspace, Jonathan R. Senning

ACMS Conference Proceedings 1999

This paper is a review of Virtual Gods: The Seduction of Power and Pleasure in Cyberspace, edited by Tal Brooke, Harvest House Publishers, 1997.