Physical Sciences and Mathematics Commons^™

Algorithms For Closest Point Problems: Practice And Theory, Peter Su

Computer Science Technical Reports

This paper describes and evaluates know sequential algorithms for constructing planar Voronoi diagrams and Delaunay triangulations. In addition, it describes a new incremental algorithm which is simple to understand and implement, but whose performance is competitive with all known methods. The experiments in this paper are more than just simple benchmarks, they evaluate the expected performance of the algorithms in a precise and machine independent fashion. Thus, the paper also illustrates how to use experimental tools to both understand the behaviour of different algorithms and to guide the algorithm design process.

A Set Of Orthogonal Polynomials Induced By A Given Orthogonal Polynomial, Walter Gautschi, Shikang Li

Department of Computer Science Technical Reports

No abstract provided.

Two Dimensional Mat To Boundary Conversion, Pamela J. Vermeer

Department of Computer Science Technical Reports

No abstract provided.

On Correspondence, Line Tokens And Missing Tokens, Chia-Hoang Lee, Anupam Joshi

Department of Computer Science Technical Reports

No abstract provided.

The Visual Diagnosis On The Numerical Calculation Of Pde Problems, Yukio Umetani

Department of Computer Science Technical Reports

No abstract provided.

Multi-Parameterized Schwarz Splittings, Sang-Bae, Elias N. Houstis, Apostolos Hadjidimos, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Abduction In Annotated Logic Programming, Krishnaprasad Thirunarayan

Kno.e.sis Publications

The author investigates techniques to make the logic programming paradigm more expressive for knowledge representation, while simultaneously retaining the computational advantages of efficiency and simplicity. He extends the annotated language of K. Thirunarayan and K. Kifer (1989) in various directions to obtain an enriched representation language. In particular, rule bodies are permitted to be a conjunction of literals, and the rules to be recursive. A class of annotated logic programs called the stratified programs is identified which can be given a unique supported minimal Herbrand model as their meaning. Abductive reasoning is integrated into this annotated logic framework. The notion …

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of “congestion” and “dilation” measures for a set of packet paths. We give, for any constant ε > 0, a randomized on-line algorithm for routing any set of N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also …

Adaptive Boundary Detection Using “Live-Wire” Two-Dimensional Dynamic Programming, William A. Barrett, Bryan S. Morse, Eric N. Mortensen, Jayaram Udupa

Faculty Publications

An adaptive boundary detection algorithm that uses two-dimensional dynamic programming is presented. The algorithm is less constrained than previous one-dimensional dynamic programming algorithms and allows the user to interactively determine the mathematically optimal boundary between a user-selected seed point and any other dynamically selected "free” point in the image. Interactive movement of the free point by the cursor causes the boundary to behave like a “live wire” as it adapts to the new minimum cost path between the seed point and the currently selected free point. The algorithm can also be adapted or customized to learn boundary-defining features for a …

Process And Policy: Resource-Bounded Non-Demonstrative Reasoning, Ronald P. Loui

All Computer Science and Engineering Research

This paper investigates the appropriateness of formal dialectics as a basis for non-monotonic and defeasible reasoning that takes computational limits seriously. Rules that can come into conflict should be regarded as policies, which are inputs to deliberative processes. Dialectical protocols are appropriate for such deliberations when resources are bounded and search is serial. AI, it is claimed here, is now perfectly positioned to correct many misconceptions about reasoning that have resulted from mathematical logic's enormous success in this century: among them (1) that all reasons are demonstrative, (2) that rational belief is constrained, not constructed, (3) that process and disputation …

Finite Representations Of Real Parametric Curves And Surfaces, Chandrajit L. Bajaj, Andrew V. Royappa

Department of Computer Science Technical Reports

No abstract provided.

Improving Gl Surface Joins By Using A Composite Patch, Jörg Peters

Department of Computer Science Technical Reports

No abstract provided.

Experiments With Program Unification On The Cray Y-Mp, Ling-Yu Chuang, Vernon J. Rego, Aditya P. Mathur

Department of Computer Science Technical Reports

No abstract provided.

Efficient Techniques For Simulating Service Disciplines, Janche Sang, Ke-Hsiung Chung, Vernon J. Rego

Department of Computer Science Technical Reports

No abstract provided.

Smooth Free-Form Surfaces Over Irregular Meshes Generalizing Quadratic Splines, Jörg Peters

Department of Computer Science Technical Reports

No abstract provided.

A New Family Of Preconditioners For Domain Decomposition, Mo Mu

Department of Computer Science Technical Reports

No abstract provided.

Separating Structure From Function In The Specification And Design Of Distributed Systems, Kenneth J. Goldman

All Computer Science and Engineering Research

A distributed system is viewed as a collection of functional components and a unifying structure that defines relationships among the components. In the paper, we advocate a particular approach to distributed system specification and design in which the structure of a distributed system is specified separately from the functional components. This permits one to reason about individual functional components in isolation, and encourages one to make explicit not only the input/output behavior of the functional components but also the logical placement of these components within the overall structure of the system. We describe a new software tool for the specification, …

Introduction To Software Engineering, An, Harlan D. Mills, J. R. Newman, Charles B. Engle, Jr., Luwana Clever

The Harlan D. Mills Collection

No abstract provided.

On Multisplitting Methods And M-Step Preconditioners For Parallel And Vector Machines, A. Hadjidimos, A. K. Yeyios

Department of Computer Science Technical Reports

No abstract provided.

A Performance Comparison Of Simulation Calendar Algorithms: An Empirical Approach, Kehsiung Chung, Janche Sang, Vernon J. Rego

Department of Computer Science Technical Reports

No abstract provided.

A Generic Virus Scanner In C++, Sandeep Kumar, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.

Backpropagation Learns Marr's Operator, Anupam Joshi, Chia-Hoang Lee

Department of Computer Science Technical Reports

No abstract provided.

Constructing Cl Surfaces Of Arbitrary Topology Using Biquadratic And Bicubic Splines, Jörg Peters

Department of Computer Science Technical Reports

No abstract provided.

On The Problem Of Correspondence In Range Data And Some Inelastic Uses For Elastic Nets, Anupam Joshi, Chia-Hoang Lee

Department of Computer Science Technical Reports

No abstract provided.

The Emergence Of Algebraic Curves And Surfaces In Geometric Design, Chandrajit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.

Effect Of The X² Test On Construction Of Id3 Decision Trees, Mayank Thakore, Daniel C. St. Clair

Computer Science Technical Reports

Inductive machine learning algorithms are knowledge-based learning algorithms which take training instances as input and produce knowledge as output. One popular induction algorithm is Quinlan's ID3 [1986]. This algorithm produces knowledge in the form of a decision tree. Each path in the tree can be interpreted as a rule with the leaves representing rule conclusions. Selected attributes which describe the training instances form the interior nodes of the tree.

The ID3 algorithm is extremely sensitive to noisy training data. In an effort to reduce the effects of noise on tree construction, Quinlan used the X² test to identify noisy …

Numerical Solution Of Laplace's Equation, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial discusses Laplace's equation for steady state heat flow in a two-dimensional region with fixed temperatures on the boundaries. The equilibrium temperatures are computed for a square grid using successive overrelaxation with parity ordering of the grid elements. The numerical method is illustrated by a Pascal algorithm. We assume that the reader is familiar with elementary calculus.

Parallel Cellular Automata: A Model Program For Computational Science, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

We develop a model program for parallel execution of cellular automata on a multicomputer. The model program is then adapted for simulation of forest fires and numerical solution of Laplace's equation for stationary heat flow. The performance of the parallel program is analyzed and measured on a Computing Surface configured as a matrix of transputers with distributed memory.

Multiple-Length Division Revisited: A Tour Of The Minefield, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

Long division of natural numbers plays a crucial role in Cobol arithmetic, cryptography, and primality testing. Only a handful of textbooks discuss the theory and practice of long division, and none of them do it satisfactorily. This tutorial attempts to fill this surprising gap in the literature on computer algorithms. We illustrate the subtleties of long division by examples, define the problem concisely, summarize the theory, and develop a complete Pascal algorithm using a consistent terminology.

All-To-Many Communication Avoiding Node Contention, Sanjay Ranka, Jhy-Chun Wang

Electrical Engineering and Computer Science - Technical Reports

In this paper we present several algorithms for all-too-many personalized communications which avoid node contention.