Computer Sciences Commons^™

Optimal Greedy Algorithms For Indifference Graphs, Peter J. Looges, Stephan Olariu

Computer Science Faculty Publications

A fundamental problem in social sciences and management is understanding and predicting decisions made by individuals, various groups, or the society as a whole. In this context, one important concept is the notion of indifference. We characterize the class of indifference graphs, that is, graphs which arise in the process of quantifying indifference relations. In particular, we show that these graphs are characterized by the existence of a special ordering of their vertices. As it turns out, this ordering leads naturally to optimal greedy algorithms for a number of computational problems, including coloring, finding a shortest path between two vertices, …

Multiple Learner Systems Using Resampling Methods, Binyun Xie

Computer Science Theses & Dissertations

The N-Learners Problem deals with combining a number of learners such that the resultant system is "better", under some criterion, than the best of the individual learners. We consider a system of probably approximately correct concept learners. Depending on the available information, there are several methods to make the composite system better than the best of the individual learners. If a sample and an oracle that generates data points (but, not their classification) is available, then we show that we can achieve arbitrary levels of the normalized confidence of the composite system if (a) a robust learning algorithm is available, …

High Performance Issues On Parallel Architectures, Peter J. Looges

Computer Science Theses & Dissertations

In an effort to reduce communication latency in mesh-type architectures, these architectures have been augmented by various types of global and reconfigurable bus structures. The static bus structures provide excellent performance in many areas of computation especially structured numerical computations, but they lack the flexibility required of many large numerical and non-numerical applications. Reconfigurable bus systems have the dynamic adaptability to handle a much wider range of applications. While reconfigurable meshes can often yield constant time results for many problems, the cost of this performance is paid in the number of processors required. While in actuality the majority of these …

Text-Independent Automatic Speaker Identification Using Partitioned Neural Networks, Laszlo Rudasi

Electrical & Computer Engineering Theses & Dissertations

This dissertation introduces a binary partitioned approach to statistical pattern classification which is applied to talker identification using neural networks. In recent years artificial neural networks have been shown to work exceptionally well for small but difficult pattern classification tasks. However, their application to large tasks (i.e., having more than ten to 20 categories) is limited by a dramatic increase in required training time. The time required to train a single network to perform N-way classification is nearly proportional to the exponential of N. In contrast, the binary partitioned approach requires training times on the order of N². …

Visual Graphic Knowledge Management Methodology, Jih-Shih Hsu

Computer Science Theses & Dissertations

As computer technology evolves, graphic workstations are becoming more popular. They support more friendly user interfaces than do conventional terminals. The better user interfaces require more effort to develop. Therefore, many user interface (UI) design systems have been developed to facilitate the creation of modern user interfaces, but not very successfully. Many of them either provide limited features or are difficult to use. Besides, these UI design systems are actually like black boxes to their users because the underlying technology is opaque; their users cannot learn how to utilize the underlying window systems through user interface design sessions. In a …

Multigrid Algorithms For Massively Parallel Machines, Satyanarayan Gupta

Computer Science Theses & Dissertations

Numerical solutions of partial differential equations (pde's) are required in many physical problems arising in areas such as computational fluid dynamics, atmospheric sciences, electromagnetics etc. One of the most popular methods of solving pde's is the use of the multigrid algorithm. However, the implementation of the multigrid algorithm on massively parallel machines is not very efficient because of (i) low processor utilization and (ii) high communication overheads. These problems need to be addressed to make better use of massively parallel machines for solving pde's using the multigrid algorithm.

In this dissertation, we present three parallel multigrid algorithms which …

Single Object Detection Using Multiple Sensors With Unknown Noise Distributions, Shaofen Chen

Computer Science Theses & Dissertations

We consider the design of an object classification system that identifies single objects using a system of sensors; each sensor outputs a random vector, according to an unknown (noise) probability distribution, in response to a sensed object. We consider a special class of systems, called the linearly separable systems, where the error-free sensor outputs corresponding to distinct objects can be mapped into disjoint intervals on real line. Given a set of sensor outputs corresponding to known objects, we show that a detection rule α_emp that approaches the correct rule with a high probability can be computed. We show …

Monitoring Computer Systems: An Intelligent Approach, Myron Zhihong Xu

Computer Science Theses & Dissertations

Monitoring modern computer systems is increasingly difficult due to their peculiar characteristics. To cope with this situation, the dissertation develops an approach to intelligent monitoring. The resulting model consists of three major designs: representing targets, controlling data collection, and autonomously refining monitoring performance. The model explores a more declarative object-oriented model by introducing virtual objects to dynamically compose abstract representations, while it treats conventional hard-wired hierarchies and predefined object classes as primitive structures. Taking the representational framework as a reasoning bed, the design for controlling mechanisms adopts default reasoning backed up with ordered constraints, so that the amount of data …

Reasoning By Analogy In A Multi-Level System Architecture For The Design Of Mechanisms, Ghassan F. Issa

Computer Science Theses & Dissertations

Since the first attempts to integrate AI technology and engineering design nearly two decades ago, few expert systems have been shown to demonstrate sufficient reasoning capabilities to solve real-world design problems. The complex nature of design, the lack of understanding of the design process, and the limitations of current expert system technology have all been shown to have adverse effects on the maturity of this research area. Therefore, our direction in this research concentrates on understanding the design process, investigating a novel area of research focusing on creative design, and incorporating the results into a system model feasible for production …

Formant Estimation From Dctc's Using A Feedforward Neural Network, Shubhangi U. Kelkar

Electrical & Computer Engineering Theses & Dissertations

Formants are the natural frequencies of the human vocal tract. Existing methods for estimating formants from speech signals are computationally complex and subject to errors for certain type of speech sounds. This thesis describes a method for estimating vowel formant frequencies from Discrete Cosine Transform Coefficients (DCTC's), a form of cepstral coefficients, using a feedforward neural network with back-propagation training. Experimental results are based on a large multispeaker data base. The results are obtained for both a linear transformation and a feedforward neural network with a nonlinear hidden layer. In general, the neural network transformation is superior to the linear …

Bounds On Constraint Weight Parameters Of Hopfield Networks For Stability Of Optimization Problem Solutions, Gursel Serpen

Electrical & Computer Engineering Theses & Dissertations

The purpose of the presented research is to study the convergence characteristics of Hopfield network dynamics. The relation between constraint weight parameter values and the stability of solutions of constraint satisfaction and optimization problems mapped to Hopfield networks is investigated. A theoretical development relating constraint weight parameter values to solution stability is presented. The dependency of solution stability on constraint weight parameter values is shown employing an abstract optimization problem. A theorem defining bounds on the constraint weight parameter magnitudes for solution stability of constraint satisfaction and optimization problems is proved. Simulation analysis on a set of optimization and constraint …

Smimd - A Synchronous Multiple Instruction Multiple Data Computer Architecture, Cathy C. Roberts

Computer Science Theses & Dissertations

This thesis assesses the feasibility of utilizing a hypercube interconnect topology to link a heterogeneous processor array in a very long instruction word (VLIW) computer architecture. The research focused upon the selection of a suitable arrangement of processors for the computer and the subsequent demonstration of the architecture's capability to handle simple loop iterations. Previous attempts at VLIW computer design are summarized, the new SMIMD architecture is presented, and suggestions for future research are given. The thesis concludes with results of the initial performance evaluations of the architecture design.

High Performance Issues In Image Processing And Computer Vision, Jingyuan Zhang

Computer Science Theses & Dissertations

Typical image processing and computer vision tasks found in industrial, medical, and military applications require real-time solutions. These requirements have motivated the design of many parallel architectures and algorithms. Recently, a new architecture called the reconfigurable mesh has been proposed. This thesis addresses a number of problems in image processing and computer vision on reconfigurable meshes.

We first show that a number of low-level descriptors of a digitized image such as the perimeter, area, histogram and median row can be reduced to computing the sum of all the integers in a matrix, which in turn can be reduced to computing …

The Morphology Of Convex Polygons, Stephan Olariu

Computer Science Faculty Publications

A simple polygon P is said to be unimodal if for every vertex of P, the Euclidian distance function to the other vertices of P is unimodal. The study of unimodal polygons has emerged as a fruitful area of computational and discrete geometry. We study unimodality properties of a number of special convex polygons from the morphological point of view. In particular, we establish a hierarchy among three classes of convex polygons in terms of their unimodality properties.

On Sources In Comparability Graphs, With Applications, Stephan Olariu

Computer Science Faculty Publications

We characterize sources in comparability graphs and show that our result provides a unifying look at two recent results about interval graphs.

A Tree Representation For P4-Sparse Graphs, B. Jamison, Stephan Olariu

Computer Science Faculty Publications

A graph G is P₄-sparse if no set of five vertices in G induces more than one chordless path of length three. P₄-sparse graphs generalize both the class of cographs and the class of P₄-reducible graphs. We give several characterizations for P₄-sparse graphs and show that they can be constructed from single-vertex graphs by a finite sequence of operations. Our characterization implies that the P₄-sparse graphs admit a tree representation unique up to isomorphism. Furthermore, this tree representation can be obtained in polynomial time.

A Case Study In Software Reuse: The Rntds Architecture, Barry J. Stevens

Computer Science Theses & Dissertations

It has been asserted that the most significant gains in software productivity will come from increased levels of software reuse. Some economic models for predicting savings through software reuse exist, but none are based on actual project experience. This paper surveys those models and presents the results of a case study, the Restructured Naval Tactical Data Systems (RNTDS) architecture, in the light of those models. According to the models, software reuse via the RNTDS architecture has enabled the production of fourteen major computer programs at five to twenty-one percent of the cost to create them without software reuse. Organizational characteristics …

Approaches To High Speed Networks, Frank Charles Paterra

Computer Science Theses & Dissertations

This work investigates possible methods by which existing potentially available communication bandwidth can be used by communication intensive applications. Presently fiber optic media are available that can provide multiple gigabits of throughput. Unfortunately, because of the computation overhead required to insure that data are reliably transmitted this capacity has not been tapped.

A survey of work toward enabling the use of the potential bandwidth is presented. The parallel paradigm is identified as a strong candidate for providing significant increases in system usable bandwidth. Performing communication processing in parallel, however, presents the developer with several implementation options. These options are considered …

Computer Simulation Techniques To Assess Bias And Precision In The Roving Creel Survey Estimator, David L. Wade

Biological Sciences Theses & Dissertations

Fisheries scientists use roving creel survey methods to estimate total catch and total effort of recreational fisheries. Bias in the roving creel estimators had been known to the scientific community, but it had not been quantified. I developed a roving-creel-survey computer simulation model to investigate the bias and precision of roving creel estimators, and estimated parameters for the model based on field observations from the blue crab (Callinectes sapidus) fishery of the Chesapeake Bay. The computer model was used to identify bias in roving-creel effort and catch estimators and to demonstrate survey methods that will reduce this bias. …

Domain Limitations And Interface Requirements For Expert Developed Knowledge Based Systems, Bernard Lee Lewis

Engineering Management & Systems Engineering Theses & Dissertations

The expanded use of graphical, case-based and object oriented techniques in expert systems creation has made it more practical for domain experts to develop their own applications. This thesis focuses on the elements necessary in an expert/developer interface and looks at various forms and techniques that exemplify such an approach. The spreadsheet metaphor is used for an interface or managed set of interfaces that a domain expert can use in building his own expert system or prototype. criteria are established for such interfaces and recent commercial offerings that make expert-created knowledge-bases more practical are reviewed for techniques that qualify. Approaches …

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 …

A Robust Approach To Human-Computer Interface Design Using The Taguchi Method, Billie Mitchell Reed

Engineering Management & Systems Engineering Theses & Dissertations

The application of Dr. Genichi Taguchi's approach for design optimization, called Robust Design, to the design of human-computer interface software is investigated. The Taguchi Method is used to select a near optimum set of interface design alternatives to improve user acceptance of the resulting interface software product with minimum sensitivity to uncontrollable noise caused by human behavioral characteristics.

Design alternatives for interaction with personal micro-computers are identified. Several important and representative alternatives are chosen as design parameters for the Taguchi matrix experiment. A noise field with three human behavioral characteristics as noise factors were chosen as a representative noise array. …

Indifference Graphs And The Single Row Routing Problem, Peter J. Looges

Computer Science Theses & Dissertations

This thesis investigates the subclass of interval graphs known as indifference graphs. New optimal algorithms for recognition, center, diameter, maximum matching, Hamiltonian path and domination in indifference graphs are presented. The recognition algorithm produces a linear order with properties which allow the solution of the other problems in linear time. Indifference graphs are further applied to the single row routing problem which results in both sequential,. and parallel routing algorithms.

Effectiveness Analysis Of Knowledge Bases, Shensheng Zhao

Computer Science Theses & Dissertations

Knowledge base systems (expert systems) are entering a critical stage as interest spreads from university research to practical applications. If knowledge base systems are to withstand this transition, special attention must be paid to checking their effectiveness. The issue of effectiveness analysis of knowledge base systems has been largely ignored and few works have been published in this field. This dissertation shows how the effectiveness of a knowledge base system can be defined, discussed and analyzed at the knowledge base system level and the knowledge base level. We characterize the effectiveness of a knowledge base system in terms of minimality, …

Kinematic Synthesis Of Deployable-Foldable Truss Structures Using Graph Theory, Dirk B. Warnaar

Mechanical & Aerospace Engineering Theses & Dissertations

A graph theoretic approach is applied to the conceptual design of deployable truss structures. The characteristics that relate to the inter-connectivity of the elements of a deployable truss structure can be captured in a schematic representation, called a graph. A procedure is presented that enables the exhaustive generation of these graphs for structures of any given number of nodes and links and which are foldable onto a plane or onto a line.

A special type of truss structures, called truss modules, is presented. Graphs of this class of structures form a subset of the graphs of truss structures. Two procedures …

Computer Use In The Scientific Office, Douglas L. Miller

Psychology Theses & Dissertations

Over the past two decades computers in research and development organizations have become a complex and integral part of the work process. Yet to date only a handful of systematic investigations have addressed issues involving scientists' or other professionals' use of computers, and very little is known about factors influencing use (Bikson and Gutek, 1983; Blacker and Brown, 1986; Collopy, 1988; Gasser, 1986; Helander, 1985; Nickolson, 1985; Pope, 1985). As a result, this research was designed to address four objectives. The first was to develop and evaluate a descriptive model of variables influencing scientists' computer use. The second objective was …

Simulator For Concurrent Processing Data Flow Architectures, Mahyar R. Malekpour

Electrical & Computer Engineering Theses & Dissertations

A software simulator capable of simulating execution of an algorithm graph on a given system under the Algorithm To Architecture Mapping Model (ATAMM) rules is presented in this thesis. ATAMM is capable of modeling the execution of large-grained algorithms on distributed data flow architectures. Investigating the behavior and determining the performance of an ATAMM based system requires the aid of software tools. The ATAMM Simulator presented in this thesis is capable of determining the behavior, performance, and reliability of a system without having to build a hardware prototype. Case studies are performed on four algorithms to demonstrate the capabilities of …

Estimation In A Marked Poisson Error Recapture Model Of Software Reliability, Rajan Gupta

Mathematics & Statistics Theses & Dissertations

Nayak's (1988) model for the detection, removal, and recapture of the errors in a computer program is extended to a larger family of models in which the probabilities that the successive programs produce errors are described by the tail probabilities of discrete distribution on the positive integers. Confidence limits are derived for the probability that the final program produces errors. A comparison of the asymptotic variances of parameter estimates given by the error recapture and by the repetitive-run procedure of Nagel, Scholz, and Skrivan (1982) is made to determine which of these procedures efficiently uses the test time.

Integration Of Abductive And Deductive Inference Diagnosis Model And Its Application In Intelligent Tutoring System, Jingying Zhang

Computer Science Theses & Dissertations

This dissertation presents a diagnosis model, Integration of Abductive and Deductive Inference diagnosis model (IADI), in the light of the cognitive processes of human diagnosticians. In contrast with other diagnosis models, that are based on enumerating, tracking and classifying approaches, the IADI diagnosis model relies on different inferences to solve the diagnosis problems. Studies on a human diagnosticians' process show that a diagnosis process actually is a hypothesizing process followed by a verification process. The IADI diagnosis model integrates abduction and deduction to simulate these processes. The abductive inference captures the plausible features of this hypothesizing process while the deductive …

A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen

Computer Science Faculty Publications

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).