Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

1993

Computer Sciences

Institution
Keyword
Publication
Publication Type
File Type

Articles 1 - 30 of 321

Full-Text Articles in Physical Sciences and Mathematics

Greengard's N-Body Algorithm Is Not Order N, Aluru Srinivas Dec 1993

Greengard's N-Body Algorithm Is Not Order N, Aluru Srinivas

Computer Science Technical Reports

Greengard's N-body algorithm claims to compute the pairwise interactions in a system of N particles in O(N) time for a fixed precision. In this paper, we show that the choice of precision is not independent of N and has a lower bound of log N. We use this result to show that Greengard's algorithm is not O(N).


Convex Hulls: Complexity And Applications (A Survey), Suneeta Ramaswami Dec 1993

Convex Hulls: Complexity And Applications (A Survey), Suneeta Ramaswami

Technical Reports (CIS)

Computational geometry is, in brief, the study of algorithms for geometric problems. Classical study of geometry and geometric objects, however, is not well-suited to efficient algorithms techniques. Thus, for the given geometric problems, it becomes necessary to identify properties and concepts that lend themselves to efficient computation. The primary focus of this paper will be on one such geometric problems, the Convex Hull problem.


Effect Of Joystick Versus Control Yoke Use On Personal Computer (Pc) Flight Training: A Comparative Analysis, Gregory Alan Fontaine Dec 1993

Effect Of Joystick Versus Control Yoke Use On Personal Computer (Pc) Flight Training: A Comparative Analysis, Gregory Alan Fontaine

Theses - Daytona Beach

The purpose of this study was to provide a comparative performance analysis of a generic control yoke device and a generic joystick device. The comparison provided data needed for further evaluation of personal computer (PC) aircrew training device (ATD) potential. Both devices were used in support of the same PC flight simulation software program, and were evaluated using the experimental research method. Objective and subjective data were obtained during controlled testing, and subsequently analyzed using basic summation and t-test methods. The results tested the research hypothesis that there is no significant difference in personal computer ATD operator performance using a ...


Probing Tcp Implementations, Douglas E. Comer, John C. Lin Dec 1993

Probing Tcp Implementations, Douglas E. Comer, John C. Lin

Department of Computer Science Technical Reports

No abstract provided.


An Optimal O(Log Log N) Time Parallel Algorithm For Detecting All Squares In A String, Albert Apostolico, Dany Breslauer Dec 1993

An Optimal O(Log Log N) Time Parallel Algorithm For Detecting All Squares In A String, Albert Apostolico, Dany Breslauer

Department of Computer Science Technical Reports

No abstract provided.


A Generalized Schwarz Splitting Method Based On Hermite Collocation For Elliptic Boundary Value Problems, Yu-Ling Lai, Apostolos Hadjidimos, Elias N. Houstis Dec 1993

A Generalized Schwarz Splitting Method Based On Hermite Collocation For Elliptic Boundary Value Problems, Yu-Ling Lai, Apostolos Hadjidimos, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.


Parallel Dynamic Mesh Generation And Domain Decomposition, Poting Wu, Elias N. Houstis Dec 1993

Parallel Dynamic Mesh Generation And Domain Decomposition, Poting Wu, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.


Correctness Proof Of A Geometric Constraint Solver, Ioannis Fudos, Christoph M. Hoffmann Dec 1993

Correctness Proof Of A Geometric Constraint Solver, Ioannis Fudos, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.


Combinatorial Optimization Problems For Which Almost Every Algorithm Is Asymptotically Optimal, Wojciech Szpankowski Dec 1993

Combinatorial Optimization Problems For Which Almost Every Algorithm Is Asymptotically Optimal, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.


A Probabilistic Analysis Of A String Editing Problem And Its Variations, Guy Louchard, Wojciech Szpankowski Dec 1993

A Probabilistic Analysis Of A String Editing Problem And Its Variations, Guy Louchard, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.


A Scheduling Policy With Maximal Stability Region For Rings Networks With Spatial Reuse, Leonidas Georgiadis, Wojciech Szpankowski, Leondros Tassiulas Dec 1993

A Scheduling Policy With Maximal Stability Region For Rings Networks With Spatial Reuse, Leonidas Georgiadis, Wojciech Szpankowski, Leondros Tassiulas

Department of Computer Science Technical Reports

No abstract provided.


C3: A Parallel Model For Coarse-Grained Machines, Susanne E. Hambrusch, Ashfaq A. Khokhar Dec 1993

C3: A Parallel Model For Coarse-Grained Machines, Susanne E. Hambrusch, Ashfaq A. Khokhar

Department of Computer Science Technical Reports

No abstract provided.


Extending Multidatabase Transaction Management Techniques To Software Development Environments, Aidong Zhang, Omran Bukhres Dec 1993

Extending Multidatabase Transaction Management Techniques To Software Development Environments, Aidong Zhang, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.


A View-Based Approach To Relaxing Global Serializability In Multidatabase Systems, Aidong Zhang, Evaggelia Pitoura, Bharat K. Bhargava Dec 1993

A View-Based Approach To Relaxing Global Serializability In Multidatabase Systems, Aidong Zhang, Evaggelia Pitoura, Bharat K. Bhargava

Department of Computer Science Technical Reports

No abstract provided.


Constructing Distributed Schedulers Using The Messiahs Interface Language, Steve J. Chapin, Eugene H. Spafford Dec 1993

Constructing Distributed Schedulers Using The Messiahs Interface Language, Steve J. Chapin, Eugene H. Spafford

Department of Computer Science Technical Reports

No abstract provided.


Object-Orientation In Multidatabase Systems, Evaggelia Pitoura, Omran Bukhres, Ahmed K. Elmagarmid Dec 1993

Object-Orientation In Multidatabase Systems, Evaggelia Pitoura, Omran Bukhres, Ahmed K. Elmagarmid

Department of Computer Science Technical Reports

No abstract provided.


Data Structures And Algorithms For The String Statistics Problem, Alberto Apostolico, Franco P. Preparata Dec 1993

Data Structures And Algorithms For The String Statistics Problem, Alberto Apostolico, Franco P. Preparata

Department of Computer Science Technical Reports

No abstract provided.


Collaborative Multimedia Game Environments, Vinod Anupam, Chandrajit L. Bajaj Dec 1993

Collaborative Multimedia Game Environments, Vinod Anupam, Chandrajit L. Bajaj

Department of Computer Science Technical Reports

No abstract provided.


Scheduling Support Mechanisms For Autonomous, Heterogeneous, Distributed Systems (Ph.D. Thesis), Steve J. Chapin Dec 1993

Scheduling Support Mechanisms For Autonomous, Heterogeneous, Distributed Systems (Ph.D. Thesis), Steve J. Chapin

Department of Computer Science Technical Reports

No abstract provided.


Asymptotic Behavior Of The Lempel-Ziv Parsing Scheme And Digital Search Trees, Philippe Jaquet, Wojciech Szpankowski Dec 1993

Asymptotic Behavior Of The Lempel-Ziv Parsing Scheme And Digital Search Trees, Philippe Jaquet, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.


The Use Of Neural Networks To Support "Intelligent" Scientific Computing, Anupam Joshi, Csanjiva Weerawarana, Elias N. Houstis Dec 1993

The Use Of Neural Networks To Support "Intelligent" Scientific Computing, Anupam Joshi, Csanjiva Weerawarana, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.


Parallel Numerical Methods For Partial Differential Equations (Ph.D. Thesis), Sang-Bae Kim Dec 1993

Parallel Numerical Methods For Partial Differential Equations (Ph.D. Thesis), Sang-Bae Kim

Department of Computer Science Technical Reports

No abstract provided.


Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole Dec 1993

Script-Based Qos Specifications For Multimedia Presentations, Richard Staehli, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Multimedia presentations can convey information not only by the sequence of events but by their timing. The correctness of such presentations thus depends on the timing of events as well as their sequence and content. This paper introduces a formal specification language for playback of real-time presentations. The main contribution of this language is a quality of service (QOS) specification that relaxes resolution and synchronization requirements for playback. Our definitions give a precise meaning to the correctness of a presentation. This specification language will form the basis for a QOS interface for reservation of operating system resources.


Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh Dec 1993

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Computer Science: Faculty Publications and Other Works

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O ...


Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih Dec 1993

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Computer Science: Faculty Publications and Other Works

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as ...


Self-Modifying Finite Automata, Roy S. Rubinstein, John N. Shutt Dec 1993

Self-Modifying Finite Automata, Roy S. Rubinstein, John N. Shutt

Computer Science Faculty Publications

We present here a new model of computation: the Self-Modifying Finite Au- tomaton (SMFA). This is similar to a standard finite automaton, but changes to the machine are allowed during a computation. It is shown here that a weak form of this model has the power to recognize an important class of context-free languages, the metalinear languages, as well as some significant non-context-free languages. Less restricted forms of SMFA's may accept even more.


Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis Dec 1993

Parallel H-V Drawings Of Binary Trees, Panagiotis T. Metaxas, Grammati E. Pantziou, Antonis Symvonis

Computer Science Technical Reports

In this paper we present a method to obtain optimal h-v and inclusion drawings in parallel. Based on parallel tree contraction, our method computes optimal (with respect to a class of cost functions of the enclosing rectangle) drawings in $O(\log^2 n)$ parallel time by using a polynomial number of EREW processors. The number of processors reduces substantially when we study minimum area drawings. The method can be extended to compute optimal inclusion layouts in the case where each leaf $l$ of the tree is represented by rectangle $l_x \times l_y$ (the dimensions of which are part of the ...


Dynamic Decision Modeling In Medicine: A Critique Of Existing Formalisms, Tze-Yun Leong Dec 1993

Dynamic Decision Modeling In Medicine: A Critique Of Existing Formalisms, Tze-Yun Leong

Research Collection School Of Information Systems

Dynamic decision models are frameworks for modeling and solving decision problems that take into explicit account the effects of time. These formalisms are based on structural and semantical extensions of conventional decision models, e.g., decision trees and influence diagrams, with the mathematical definitions of finite-state semi-Markov processes. This paper identifies the common theoretical basis of existing dynamic decision modeling formalisms, and compares and contrasts their applicability and efficiency. It also argues that a subclass of such dynamic decision problems can be formulated and solved more effectively with non-graphical techniques. Some insights gained from this exercise on automating the dynamic ...


A Probabilistic Approach To Fault Diagnosis In Linear Lightwave Networks, Robert H. Deng, A. A. Lazar, W. Wang Dec 1993

A Probabilistic Approach To Fault Diagnosis In Linear Lightwave Networks, Robert H. Deng, A. A. Lazar, W. Wang

Research Collection School Of Information Systems

The application of probabilistic reasoning to fault diagnosis in linear lightwave networks (LLNs) is investigated. The LLN inference model is represented by a Bayesian network (or causal network). An inference algorithm is proposed that is capable of conducting fault diagnosis (inference) with incomplete evidence and on an interactive basis. Two belief updating algorithms are presented which are used by the inference algorithm for performing fault diagnosis. The first belief updating algorithm is a simplified version of the one proposed by Pearl (1988) for singly connected inference models. The second belief updating algorithm applies to multiply connected inference models and is ...


Asynchronous Transaction Commitment In Federated Database Systems, San-Yih Hwang, Ee Peng Lim, Jaideep Srivastava Dec 1993

Asynchronous Transaction Commitment In Federated Database Systems, San-Yih Hwang, Ee Peng Lim, Jaideep Srivastava

Research Collection School Of Information Systems

We propose a new (and restricted) model for global transactions which allows asynchronous commitment of subtransactions. Our model requires each global transaction to have a fixed structure with update to the data in at most one database. Based on this transaction model, we present two concurrency control algorithms, namely Asynchronous Site Graph and Asynchronous VirtGlobalSG, which employ asynchronous commitment and achieve global serializability. Compared to other proposed algorithms, our algorithms employ asynchronous commitment so as to increase transaction performance. Furthermore, our algorithms do not put restrictions on transaction data access or local histories.