Digital Commons Network^™

Ua66/3/2 Computer Science Alumni Newsletter, Vol. 7, Wku Computer Science

WKU Administration Documents

Newsletter created by WKU Computer Science for alumni of the program. This issue includes course offerings, computer lab diagram and an alumni survey.

Effects Of Nonsymmetric Release Times On Rate Monotonic Scheduling, R. G. Karl, T. L. Lo, D. C. St. Clair

Computer Science Technical Reports

This paper discusses problems associated with scheduling periodic tasks in a hard, real-time processing or computing environment using a static-priority, preemptive-resume operating system . The scheduling problems associated with a task set containing a single periodic task which has two fixed release periods of unequal length are examined. Some real-world applications may require task release times which are periodic, but whose tasking periods are not symmetric. A scheduling algorithm for task sets with a single nonsymmetric task has been developed for staticpriority, preemptive-resume operating systems. The nonsymmetric scheduling algorithm is based on the rate monotonic scheduling algorithm which assigns higher …

Design Of Backpropagation Neural Network Architectures Using A Decision Tree Classifier, B. M. Van Horn, D. C. St. Clair

Computer Science Technical Reports

The backpropagation neural network algorithm is a popular machine learning methodology. One difficulty with using the algorithm is that the network architecture must be designed before learning can occur. This includes deciding the number of layers, the number of nodes in each layer, and the number of connections. Traditionally this problem is solved by heuristics gained by an expert through experience.

This paper presents an algorithm for using ID3 decision trees to design the network architecture. Previous approaches rely on binary decision trees. The proposed technique utilizes n-ary trees. These trees are easier to understand, are better suited for continuous-valued …

Optimizing Accuracy And Generalization In Numeric Classification Systems, M. D. Walters, D. C. St. Clair

Computer Science Technical Reports

Classifier systems are knowledge-based learning algorithms that take training instances as input and produce a set of rules as output. The classifier systems focused on in this paper represent the knowledge they learn in the form of decision trees, and are built upon Quinlan's [ 1986] inductive algorithm ID3.

The ID3 algorithm suffers from the inability to easily and effectively handle domains with numeric-valued attributes. Numeric attributes are those whose values are taken from a continuous domain or from a domain with a large number of discrete values. A number of approaches have been developed for extending ID3 to handle …

The Identification And Processing Of Don't-Care Attribute Values In Id3 Decision Tree Construction, P. D. Dorr, D. C. St. Clair

Computer Science Technical Reports

ID3 is most successful when used with sets of training and testing data that contain no missing attribute values. Many times, however, real-world domains have attributes with missing values. Sometimes these attribute values may not be needed to classify an instance. Such attribute values are called don't-care attribute values. In other cases, the values are needed but are unavailable. These values are called unknown attribute values. This paper describes the difference between unknown and don't-care attribute values and discusses several ways of identifying don't-care attribute values in ID3. Numerical results are described which validate the practicality of these approaches.

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 …

The Development And Application Of Testing Techniques In An Object-Oriented Paradigm, Robert F. Kozal

Masters Theses

This thesis is the study of testing object-oriented programs. Aspects of object-oriented programs for which testing techniques are developed include classes, methods, inheritance, polymorphism, and encapsulation. The application of these techniques are illustrated, and a comparison between traditional testing techniques and object-oriented techniques is also drawn.

Modeling The Darpa Diesel Engine In Proengineer, Christoph M. Hoffmann

Department of Computer Science Technical Reports

No abstract provided.

A Vml Based Implementation Of A Neural Network Library On General Purpose Parallel Processors, H. Byun, S. K. Kortesis, Elias N. Houstis

Department of Computer Science Technical Reports

No abstract provided.

Relaxing Synchronization In Distributed Simulated Annealing, Chul-Eui Hong, Bruce M. Mcmillin

Computer Science Technical Reports

Simulated annealing is an attractive, but expensive, heuristic for approximating the solution to combinatorial optimization problems. Attempts to parallelize simulated annealing, particularly on distributed memory multicomputers, are hampered by the algorithm's requirement of a globally consistent system state. In a multicomputer, maintaining the global state S Involves explicit message traffic and is a critical performance bottleneck. To mitigate this bottleneck, it becomes necessary to amortize the overhead of these state updates over as many parallel state changes as possible. By using this technique, errors in the actual cost C(S) of a particular state S will be introduced into the annealing …

Embedding Data Mappers With Distributed Memory Machine Compilers, Ravi Ponnusamy, Joel Saltz, Raja Das, Charles Koelbel, Alok Choudhary

Electrical Engineering and Computer Science - Technical Reports

In scalable multiprocessor systems, high performance demands that computational load be balanced evenly among processors and that interprocessor communication be limited as much as possible. Compilation techniques for achieving these goals have been explored extensively in recent years [3, 9, 11, 13, 17, 18]. This research has produced a variety of useful techniques, but most of it has assumed that the programmer specifies the distribution of large data structures among processor memories. A few projects have attempted to automatically derive data distributions for regular problems [12, 10, 8, 1]. In this paper, we study the more challenging problem of automatically …

Graph Theory Based Routing Algorithms, Bo Wu

Masters Theses

In this thesis, we study two VLSI layout problems.

We investigate the Minimum-Bend Single Row Routing Problem in which the objective function is to minimize the number of doglegs (or blends) per net. Our approach uses a graph theoretic representation in which an instance of the Single Row Routing Problem is represented by three graphs, an overlap graph, a containment graph and an interval graph. Using this graph representation, we develop three algorithms for minimum-bend single row routing problem.

We present a three-layer over-the-cell router (ICR-3) for the standard cell design style based on a new cell model which assumes …

Feature Extraction And Classification Of Flir Imagery Using Relative Locations Of Non-Homogeneous Regions With Feedforward Neural Networks, Kevin L. Priddy

Theses and Dissertations

The classification of forward looking infrared (FLIR) imagery is explored using Gabor transform decomposition and relative locations of non- homogeneous regions combined with feedforward neural networks. A feature saliency metric is developed from a Bayesian sensitivity analysis of feedforward neural networks. This metric is then used to reduce the dimensionality of the feature vectors used to identify FLIR imagery without any degradation of classification accuracy. Several system architectures are developed using a roving window combined with a series of Gabor filters to produce feature vectors for presentation to a neural network classifier. One architecture uses the Gabor filter coefficients to …

Algorithms For Incomplete Hypercubes, Venkata K. Prabhala

Masters Theses

Networked multiprocessing architectures for parallel com putation offer an alternative to high cost supercomputing. Recently hypercube has emerged as the most versatile architecture for parallel com putations. However, the number of nodes m in a hypercube is a power of 2, 2^d, where d is the dimension of the hypercube. In practice, it m ay not be possible to have a complete hypercube because the cost of upgradation is proportional to the num ber of nodes. Incomplete and Composite hypercubes help remove the exponential node(and hence cost) constraint.

In this thesis we establish the equality of m-node …

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 …

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 …

A Visualization System For Correctness Proofs Of Graph Algorithms, Peter A. Gloor, Donald B. Johnson, Fillia Makedon, Panagiotis Metaxas

Computer Science Technical Reports

In this paper we describe a system for visualizing correctness proofs of graph algorithms. The system has been demonstrated for a greedy algorithm. Prim's algorithm for finding a minimum spanning tree of an undirected, weighted graph. We believe that our system is particularly appropriate for greedy algorithms, though much of what we discuss can guide visualization of proofs in other contexts. While an example is not a proof, our system provides concrete examples to illustrate the operation of the algorithm. These examples can be referred to by the user interactively and alternatively with the visualization of the proof where the …

An Algorithm For Generating Executable Assertions For Fault Tolerance, Martina Schollmeyer, Hanan Lutfiyya, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents an algorithm for deriving executable assertions that can be evaluated in a faulty distributed environment. A transformation from the global auxiliary variable approach into a new proof system based on the history of the auxiliary variables is introduced. This transformation, which matches the operational distributed environment more closely than the global auxiliary variable system, is then shown to retain the properties of this system such as noninterference, satisfaction, soundness, and completeness. An example is presented in which a model problem is transformed from one system into the other.

The Interbase Parallel Language: Supporting The Flex Transaction Model And Beyond, Ahmed K. Elmagarmid, Jiansan Chen

Department of Computer Science Technical Reports

No abstract provided.

Interbase: An Execution Environment For Global Applications Over Distributed, Autonomous And, Heterogeneous Software Systems, Ahmed K. Elmagarmid, Jiansan Chen, Weimin Du, Omran Bukhres, Rob Pezzoli

Department of Computer Science Technical Reports

No abstract provided.

Fault-Tolerant Distributed Database Lock Managers Formally Derived From Program Verification, Hanan Lutfiyya, Martina Schollmeyer, Bruce M. Mcmillin

Computer Science Technical Reports

This paper presents a system for formally deriving executable assertions that can be evaluated in the faulty distributed computing environment. Since executable assertions for fault tolerance need to show that a program meets its specification and, since program verification is the process of formally showing that a program satisfies some particular properties with respect to its specification, we use program verification as a basis for derivation. It is well known that in the sequential computing environment the assertions from a program verification proof outline may be translated directly into executable assertions. However, due to the lack of global state information …

Integrated Symbolic-Numeric Computing In //Ellpack: Experiences And Plans, Sanjiva Weerawarana, Ann C. Catlin, Elias N. Houstis, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Performance Analysis Of A Polyhedral Boolean Set Operations Algorithm, George Vanĕček, Dana S. Nau, Raghu R. Karinthi

Department of Computer Science Technical Reports

No abstract provided.

Hardware-Verification Through Logic Extraction, Michael A. Dukes

Theses and Dissertations

A Prolog-based system is described which employs logic-extraction to perform hardware-verification. The extraction rules are built automatically from hierarchical structural VHDL models, enabling the equivalence of a structural VHDL description and a layout specification to be verified. Pin-to-pin critical- path analysis is performed within the logic-extraction process; many noncritical paths are pruned early, making pin-to-pin critical path analysis of large circuits feasible. It is demonstrated that a design methodology based on logic extraction, VHDL, and a layout tool can provide a fabricated functionally- correct IC design without circuit-level or switch-level simulation. This methodology is shown to be practical for VLSI …

An Examination Of Hypercube Implementations Of Genetic Algorithms, Andrew Dymek

Theses and Dissertations

Genetic algorithms are stochastic search algorithms which model natural adaptive systems. In support of the development of a genetic search package for AFIT's iPSC/2 Hypercube, this study focused on two problem areas associated with hypercube implementations. Premature convergence occurs when the population becomes dominated by locally optimal, but globally inferior, solutions. Based on an examination of past hypercube implementations, the selection and communication strategies were hypothesized as causes of premature convergence. Experiments to test these hypotheses were conducted on Rosenbrock's saddle, a function often associated with premature convergence. Communication of best solutions led to premature convergence in small population sizes, …

Development Of A Flight Information System Using The Structured Method, Yeong-Lae Kwak

Theses and Dissertations

This thesis documents the development of a database system for the Flight Information System (FIS) of the Korean Air Force. The scope of the FIS is too large to be covered by this thesis. Thus, this thesis covers only the core part of the FIS due to the limitation of time and man-power. This thesis uses the structured method. Structured analysis and structured design techniques are mainly used two techniques. This thesis focused not only the development of the FIS but also the application of the software development method, the structured method, and its tools such as DFD, DD, ERD, …

Satool Ii: An IdefO Case Workbench Using Ada And The X Window System, Betty Topp

Theses and Dissertations

The objective of this research effort is to perform an object oriented analysis, design and implementation of the graphical user interface (GUI) for the SATool II system. SATool II is a computer Assisted Software Engineering (CASE) workbench developed using Ada and the X Window system. It is designed to serve as an IDEFo graphical project editor and data dictionary editor. IDEF₀ is the ICAM Definition Method Zero graphical notation language adopted by the Air Force to produce a function model of a manufacturing system or environment. The Air Force Institute of Technology is conducting on-going research in the use …

Reservable Transactions: An Approach For Reliable Multidatabase Transaction Management, Ahmed K. Elmagarmid, Jin Jing, James G. Mullen, Jamshid Sharif-Askary

Department of Computer Science Technical Reports

No abstract provided.

Software Forensics: Can We Track Code To Its Authors?, Eugene H. Spafford, Stephen A. Weeber

Department of Computer Science Technical Reports

No abstract provided.

Conceptual Background For Symbolic Computation, Klaus Berkling

Electrical Engineering and Computer Science - Technical Reports

This paper is a tutorial which examines the three major models of computation--the Turing Machine, Combinators, and Lambda Calculus--with respect to their usefulness to practical engineering of computing machines. While the classical von Neumann architecture can be deduced from the Turing Machine model, and Combinator machines have been built on an experimental basis, no serious attempts have been made to construct a Lambda Calculus machine. This paper gives a basic outline of how to incorporate a Lambda Calculus capability into a von Neumann type architecture, maintaining full backward compatibility and at the same time making optimal use of its advantages …