Digital Commons Network^™

Fast Parallel Algorithms For Basic Problems, Zhaofang Wen

Computer Science Theses & Dissertations

Parallel processing is one of the most active research areas these days. We are interested in one aspect of parallel processing, i.e. the design and analysis of parallel algorithms. Here, we focus on non-numerical parallel algorithms for basic combinatorial problems, such as data structures, selection, searching, merging and sorting. The purposes of studying these types of problems are to obtain basic building blocks which will be useful in solving complex problems, and to develop fundamental algorithmic techniques.

In this thesis, we study the following problems: priority queues, multiple search and multiple selection, and reconstruction of a binary tree from its …

An Nc Algorithm For Scheduling Unit-Time Jobs With Arbitrary Release Times And Deadlines, Greg N. Frederickson, Susan H. Rodger

Department of Computer Science Technical Reports

No abstract provided.

Porting Ncube Packages To Ipsc/860 And Ipsc/2 Hypercubes, Jingwen Wang, Mo Mu

Department of Computer Science Technical Reports

No abstract provided.

Ambivalent Data Structures For Dynamic 2-Edge-Connectivity And K Smallest Spanning Trees, Greg N. Frederickson

Department of Computer Science Technical Reports

No abstract provided.

Negotiating And Supporting Interdependent Data In Very Large Federated Database Systems, Ahmed K. Elmagarmid, James G. Mullen

Department of Computer Science Technical Reports

No abstract provided.

Smili-Visualization Of Asynchronous Massively Parallel Programs, Rashi Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyse the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMil...l (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Comparison Of Three Axiomatic Systems For Csp, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

Currently software engineering practices use relatively few formal methods. However, formal methods can be used to find errors earlier in the software cycle and hence reduce software cost. One useful formal method is program verification. The axiomatic approach to program verification uses assertions to characterize properties of program variables and relationships between them at various stages of program execution. In order to verify these assertions, axioms or inference rules are needed for each statement as well as some statement-independent inference rules. The message passing and nondeterminism of a distributed programming language present special difficulties. This paper examines and compares three …

Smili-Visualization Of Asynchronous Massively Parallel Programs, Rashi Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyse the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMil...l (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

Comparison Of Three Axiomatic Systems For Csp, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

Currently software engineering practices use relatively few formal methods. However, formal methods can be used to find errors earlier in the software cycle and hence reduce software cost. One useful formal method is program verification. The axiomatic approach to program verification uses assertions to characterize properties of program variables and relationships between them at various stages of program execution. In order to verify these assertions, axioms or inference rules are needed for each statement as well as some statement-independent inference rules. The message passing and nondeterminism of a distributed programming language present special difficulties. This paper examines and compares three …

Fundamental Techniques For Geometric And Solid Modeling, Christoph M. Hoffmann, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

Corrigendum To "Taxonomies Of Model-Theoretically Defined Topological Properties", Paul Bankston

Mathematics, Statistics and Computer Science Faculty Research and Publications

An error has been found in the cited paper; namely, Theorem 3.1 is false.

Hidden Markov Model For Visual Guidance Of Robot Motion In Dynamic Environment, Qiuming Zhu

Computer Science Faculty Publications

Models and control strategies for dynamic obstacle avoidance in visual guidance of mobile robot are presented. Characteristics that distinguish the visual computation and motion-control requirements in dynamic environments from that in static environments are discussed. Objectives of the vision and motion planning are formulated as: 1) finding a collision-free trajectory that takes account of any possible motions of obstacles in the local environment; 2) such a trajectory should be consistent with a global goal or plan of the motion; and 3) the robot should move at as high a speed as possible, subject to its kinematic constraints. A stochastic motion-control …

Time Delay Neural Networks And Speech Recognition: Context Independence Of Stops In Different Vowel Environments, Gregory Andrew Makowski

Masters Theses

A series of speech recognition experiments was conducted to investigate time-dynamic speech recognition of stop consonants invariant of vowel environment using data from six talkers. The speech preprocessing was based on previous studies investigating acoustic characteristics which correlate to the place of articulation (Blumstein and Stevens 1979). The place of articulation features were statistically abstracted using four moments and the energy level of the speech sample.

Both statistical and neural network pattern recognition methods were used. Statistical methods included linear and quadratic discriminant functions, maximum likelihood estimator (MLE) and K-nearest neighbors (KNN). The neural network approach used was Time Delay …

A Visualization Model For Massively Parallel Algorithms, R. Khanna, Bruce M. Mcmillin

Computer Science Technical Reports

A visualization model has been developed to analyze the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns (eg. processor load, message traffic etc.). These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMILI (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff's …

One-Sided Error Probabalistic Inductive Interface And Reliable Frequency Identification, Efim Kinber, Thomas Zeugmann

School of Computer Science & Engineering Faculty Publications

For EX- and BC-type identification, one-sided error probabilistic inference and reliable frequency identification on sets of functions are introduced. In particular, we relate the one to the other and characterize one-sided error probabilistic inference to exactly coincide with reliable frequency identification, on any setM. Moreover, we show that reliable EX and BC-frequency inference forms a new discrete hierarchy having the breakpoints 1, l/2, l/3, ...

Connectionist Expert System With Adaptive Learning Capability, B. T. Low, Hochung Lui, Ah-Hwee Tan, Hoonheng Teh

Research Collection School Of Computing and Information Systems

A neural network expert system called adaptive connectionist expert system (ACES) which will learn adaptively from past experience is described. ACES is based on the neural logic network, which is capable of doing both pattern processing and logical inferencing. The authors discuss two strategies, pattern matching ACES and rule inferencing ACES. The pattern matching ACES makes use of past examples to construct its neural logic network and fine-tunes itself adaptively during its use by further examples supplied. The rule inferencing ACES conceptualizes new rules based on the frequencies of use on the rule-based neural logic network. A new rule could …

Computational Learning Theory Lecture Notes For Cs 582 Spring Semester, 1991, Sally A. Goldman

All Computer Science and Engineering Research

This manuscript is a compilation of lecture notes from the graduate level course CS 582, "Computational Learning Theory," I taught at Washington University in the spring of 1991. Students taking the course were assumed to have background in the design and analysis of algorithms as well as good mathematical background. Given that there is no text available on this subject, the course material was drawn from recent research papers. I selected the first twelve topics and the remainder were selected by the students from a list of provided topics. This list of topics is given at the end of these …

An Ada Based Expert System For The Ada Version Of Satool Ii, Min-Fuh Shyong

Theses and Dissertations

This thesis continues the work of implementing the expert system for the Ada version of SAtool II, an software design requirement analysis tool. The background, history, design process together with the design results and validation of the implementation with Ada and CLIPS/Ada is presented.

Rule-Based Module And Object-Oriented Design For Optical Character Recognition, Min Gao

Theses

In this thesis, I present a optical character recognition technique based on the rule-based module and object-oriented design. A document image is first scanned, and then segmented into isolated characters by the use of projection profiles. The recognition procedures include three steps: contour extraction, strokes detection and rule-based classification. The contour extraction is to extract the outbound boundary and to perform the boundary linking and noise removal. The stroke detection is to detect the features or strokes of the outbound boundary, such as horizontal/vertical lines, left/right slash lines and left-/right-opened curves. The rule-based classification consists of two rules: character definition …

Learning: An Experiment With Five Selection Forms, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Cystic Fibrosis: Cluster Analysis Of Microbiology And Pulmonary Function, Lori Lee M. Larson '91

Honors Projects

In an attempt to find a relationship between pulmonary infection and pulmonary function in cystic fibrosis (CF) patients, microbiology data and pulmonary function test (PFT) data for clinic patients' visits were obtained from the University of Minnesota Relational Database. The two files were merged, totaling 12,193 cases, and then analyzed using a quick cluster subroutine of SPSSX on the University of Illinois IBM Mainframe System. QUICK CLUSTER analysis showed a relationship between the virulence of the microorganisms, the amount of growth of the microorganisms, and the pulmonary function test scores of CF patients

Correspondence Problem In Image Sequence Analysis, Chia-Hoang Lee, Anupam Joshi

Department of Computer Science Technical Reports

No abstract provided.

Visual Interaction In Diagnostic Radiology, Erika Rogers, Ronald C. Arkin, M. Baron

Computer Science and Software Engineering

The concept of Visual Interaction is introduced as the process which links perception and problem-solving such that problem-solving is affected by what is seen, and conversely, what is seen and perceived is affected by the current state of the problem-solving process. This paper describes the development of a cognitively-based model of the visual interaction process in diagnostic radiology, and shows how aspects of this model are being incorporated into the design and implementation of an intelligent computer-based radiological assistant. In order to achieve this, it is necessary to extract information about the nature and type of knowledge involved in this …

Applying Parallel Bidirectional Search To A System For The Diagnosis Of Faults, J. E. Finlay, R. W. Wilkerson

Computer Science Technical Reports

Decreasing the time it takes an application to run is always an important concern. One of the ways to achieve this is through separating work in the application that need not be run sequentially onto two or more processors to be run in parallel. This work will take a look at an attempt to do this in one of the primary application areas of Artificial Intelligence, diagnosis.

Reiter's theory is presented for the diagnosis of faults from first principles, as well as a correction to the algorithm which defines the theory. An existing implementation of the theory is also discussed. …

An Implementation Of "Theorem Proving With Lemmas", C. J. Merz, R. W. Wilkerson

Computer Science Technical Reports

Two resolution proof strategies developed by Peterson [ Pe76j are implemented by modifying Otter, an existing automated theorem prover. The methods, Lock-T refutation and LNL-T refutation, are generalizations of unit refutation and input refutation, respectively, to non-Hom sets and represent independent, equivalent but opposite ways of searching. Thus, the two techniques can be run simultaneously, exchanging only important intermediate results known as lemmas.

The algorithms used in the implementation, which are based on a corrected version of the foundational work, are outlined in detail and justified. Next, the newly implemented strategies are tested individually and together on various non-Horn challenge …

Object Orientation In The Cim Environment, B. M. Higgins, J. B. Prater

Computer Science Technical Reports

Manufacturing industries are constantly looking for better ways to develop the software required to plan and control production processes. Experimental software is being developed using objectoriented program development techniques. There are many prototypes being used and tested at both academic and industrial institutions around the world.

The purpose of this paper is to examine a selection of these systems in order to highlight some of the main benefits which are being achieved by using object-oriented methods over the use of conventional approaches. Practical considerations are made concerning the long-term adoption of object-oriented methodologies in software development for Computer Integrated Manufacturing …

Investigation Of Threaded Code, K. E. Graves, Paul D. Stigall

Computer Science Technical Reports

The design, structure and performance of threaded code are examined through the development of a threaded. code classification system and the modification of the threaded code technique used by a Forth programming language implementation. The classification system distinguishes threaded code designs by three elements: the interpreter, the code structure and the reference method to routines. Threaded code designs from the literature are described using the new classification scheme. The threaded code techniques of variable depth indirect threaded code and token indirect token threaded code are examined in a Forth programming language system on an INMOS IMS T222 transputer. Their design …

Incremental Learning Of Numeric Clusters In Classifier Systems, K. R. Hacke, D. C. St. Clair

Computer Science Technical Reports

Classifier systems are knowledge-based learning algorithms which take training instances as input and produce a set of rules as output Many classifier systems represent the knowledge they learn in the form of one or more decision trees. Accurate knowledgebase systems for a variety of domains have been constructed by generating decision trees using J. R. Quinlan's (1986) inductive algorithm ID3 and P. E. Utgoffs (1988) IDS. IDS is an incremental version of ID3.

Unfortunately, all these algorithms suffer from the inability to easily and effectively handle domains with numeric-valued attributes. Numeric attributes are those whose values are taken from a …

Applying Parallel Bidirectional Search To A System For The Diagnosis Of Faults, J. E. Finlay, R. W. Wilkerson

Computer Science Technical Reports

Decreasing the time it takes an application to run is always an important concern. One of the ways to achieve this is through separating work in the application that need not be run sequentially onto two or more processors to be run in parallel. This work will take a look at an attempt to do this in one of the primary application areas of Artificial Intelligence, diagnosis.

Reiter's theory is presented for the diagnosis of faults from first principles, as well as a correction to the algorithm which defines the theory. An existing implementation of the theory is also discussed. …

An Implementation Of "Theorem Proving With Lemmas", C. J. Merz, R. W. Wilkerson

Computer Science Technical Reports

Two resolution proof strategies developed by Peterson [ Pe76j are implemented by modifying Otter, an existing automated theorem prover. The methods, Lock-T refutation and LNL-T refutation, are generalizations of unit refutation and input refutation, respectively, to non-Hom sets and represent independent, equivalent but opposite ways of searching. Thus, the two techniques can be run simultaneously, exchanging only important intermediate results known as lemmas.

The algorithms used in the implementation, which are based on a corrected version of the foundational work, are outlined in detail and justified. Next, the newly implemented strategies are tested individually and together on various non-Horn challenge …