Digital Commons Network^™

Parallel Monte Carlo Trials, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

The best results of Monte Carlo methods are generally obtained by performing the same computation many times with different random numbers. We develop a generic algorithm for parallel execution of Monte Carlo trials on a multicomputer. The generic algorithm has been adapted for simulated annealing and primality testing by simple substitutions of data types and procedures. The performance of the parallel algorithms was measured on a Computing Surface.

Designing Efficient Maximum-Likelihood Soft-Decision Decoding Algorithms For Linear Block Codes Using Algorithm A*, Yunghsiang S. Han, Carlos R.P. Hartmann

Electrical Engineering and Computer Science - Technical Reports

In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which uses a priority-first search strategy, is employed to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search …

Primality Testing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes the Miller-Rabin method for testing the primality of large integers. The method is illustrated by a Pascal algorithm. The performance of the algorithm was measured on a Computing Surface.

Simulated Annealing, Per Brinch Hansen

Electrical Engineering and Computer Science - Technical Reports

This tutorial describes simulated annealing, an optimization method based on the principles of statistical mechanics. Simulated annealing finds near-optimal solutions to optimization problems that cannot be solved exactly because they are NP-complete. The method is illustrated by a Pascal algorithm for the traveling salesperson problem. The performance of the algorithm was measured on a Computing Surface.

The 3-Tier Structured Access Protocol To Control Unfairness In Dqdb Mans, Lakshmana N. Kumar, Andreas D. Bovopoulos

All Computer Science and Engineering Research

This paper addresses the unfairness problem appearing in 802.6-based DQDB MANs. Traffic load demand is characterized as low (below 0.4 of the channel capacity), normal (from 0.4 to 0.9 of the channel capacity) or heavy (greater than 0.9 of the channel capacity). At low loads the 802.6 protocol is acceptably fair. At normal loads, however, the protocol performance is markedly unfair. The unfairness is related to the latency in transporting a request. At heavy loads the unfairness is both latency-related and flooding-related. In this paper, both types of unfairness are carefully analyzed. As a control measure, a 3-Tier Structured Access …

Algorithms For Structural Schema Integration, James Geller, Ashish Mehra, Yehoshua Perl, Erich Neuhold, Amit P. Sheth

Kno.e.sis Publications

Current view and schema integration methodologies are driven by semantic considerations, and allow integration of objects only if that is valid from semantic and structural viewpoints. We had introduced a new integration technique called structural integration. It permits integration of objects that have structural similarities, even if they differ semantically. This technique uses the object-oriented Dual Model which separates the representation of structure and semantics.

In this paper we introduce algorithms for structural integration. We apply these algorithms to integrate two views of a large university database schema which had significant structural similarities but differed semantically.

Sequential And Parallel Discrete Event Simulation On Computer Communication Networks, Tao Zhou

Masters Theses

This thesis presents the discrete event simulation technique on the network design, focusing on the methodology, modeling and implementation. The developed technique is suitable for the analysis of any store-and-forward computer communication networks with any level of complexity. The proposed generic simulation model can be used to test the architectures and protocols of existing networks and networks being designed. In implementation of the sequential discrete event simulation, an object-oriented programming strategy is applied to the network simulation using the C++ language. The parallel discrete event simulation is introduced to solve the problem of long time execution of the sequential simulation …

Design Of A Laboratory Computer Interface, Douglas L. Durand

Theses and Dissertations

An interface for the LSI-11 computer was designed and implemented so that the computer supports data acquisition, data reduction, and equipment control. The design includes both hardware and software and addresses both parallel and serial input/output (I/0). The serial interface's hardware is simply a Serial Line Unit card. This card plugs into the LSI-11 bus and provides the signals necessary to interface EIA RS-232 compatible devices. A software utility was developed to allow communication with the serial device and to allow exchange of data files. Routines were written to allow serial I/O through a FORTRAN program. The interface's parallel hardware …

Graphical Image Persistence And Code Generation For Object Oriented Databases, Subrata Chatterjee

Theses

Attached is the detailed description of the design and implementation of graphical image persistence and code generation for object oriented databases. Graphical image persistent is incorporated into a graphics editor called OODINI. OODINI creates and manipulates graphical schemas for object-oriented databases. This graphical image on secondary storage is then translated into an abstract, generic code for dual model databases. This abstract code, DAL can then be converted into different dual model database languages. We provide an example by generating code for the VODAK Data Modeling language. It is also possible to generate a different abstract language code, OODAL from a …

Interpreting And Integrating Landsat Remote Sensing Image And Geographic Information System By Fuzzy Unsupervised Clustering Algorithm, Gwotsong Philip Chen

Theses

Due to the resolution of Landsat images and the multiplicity of the terrain, it is improper to assign each pixel in an image to one of a number of land cover types by using the conventional remote sensing classification method. This is also known as the hard partition method. The concept of the fuzzy set provides the means to resolve this problem. This paper presents a two-pass-mode fuzzy unsupervised clustering algorithm.

In the first passing, the cluster mean vectors which represent the geographic attributes or the land cover types are derived. In the second passing, the concept of fuzzy set …

Transformations And Analysis Of Parallel Real Time Programs, Chandima J. Gunasekara

Theses

The problem of schedulability analysis of a set of real time programs form a NP complete problem. The exponential complexity of analysis is a direct result of the complexity in the real time programs, as a combinatorial explosion takes place when trying to determine access patterns of shared resources. Thus, to transform the original programs to a less complex form, while preserving its timing characteristics, is the only viable solution. By using such transformations to reduce the complexity of real time programs, it is possible to schedulability analyze programs at compile time efficiently, without adding an unnecessary overhead to the …

An Implementation And Evaluation Of Distributed Information System Based On The Osca Architecture Guidelines, Babita Masand

Theses

The concepts in this thesis discuss and evaluate the need for systems integration. As a conceptual architecture, the OSCA^TM architecture is investigated. A prototype of the CS Department distributed information system is built following the guidelines and standards of this conceptual architecture. This prototype is implemented in 'C'. RPC (remote procedure call) is used for the communication channel to implement the distributed environment. Conclusions and results that were achieved by implementing this prototype are presented. The main outcome of this thesis is the introduction of the infrastructure to the GenSIF framework.

New Algorithms For Mid-Crack Codes In Image Processing, Wai-Tak Wong

Theses

The chain code is a widely-used description for a contour image. Recently, a mid-crack code algorithm has been proposed as another more precise method for image representation. New algorithms using this new mid-crack code for image representation, restoration, and skeletonization are developed. The efficiency and accuracy can be increased obviously.

Firstly, the conversion of a binary image with multiple regions into the mid-crack codes is presented. A fast on-line implementation can be achieved using tables look-up. The input binary image may contain several object regions and their mid-crack codes can be extracted at the same time in a single-pass row-by-row …

Decomposition Of Geometric-Shaped Structuring Elements And Optimization On Euclidean Distance Transformation Using Morphology, Hong Wu

Theses

Mathematical morphology which is based on geometric shape, provides an approach to the processing and analysis of digital images. Several widely-used geometric-shaped structuring elements can be used to explore the shape characteristics of an object. In first chapter, we present a unified technique to simplify the decomposition of various types of big geometric-shaped structuring elements into dilations of smaller structuring components by the use of a mathematical transformation. Hence, the desired morphological erosion and dilation are equivalent to a simple inverse transformation over the result of operations on the transformed decomposable structuring elements. We also present a strategy to decompose …

An Application Of Program Unification To Priority Queue Vectorization, Ling-Yu Chuang, Vernon J. Rego, Aditya P. Mathur

Department of Computer Science Technical Reports

No abstract provided.

Minimizing Total Wire Length During 1-Dimensional Compaction, Susanne E. Hambrusch, Hung-Yi Tu

Department of Computer Science Technical Reports

No abstract provided.

Future Research Directions In Problem Solving Environments For Computational Science, Stratis Gallopoulos, Elias N. Houstis, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Shortest Path Computations In Source- Deplanarized Graphs, Greg N. Frederickson, Susanne E. Hambrusch, Hung-Yi Tu

Department of Computer Science Technical Reports

No abstract provided.

On Domains Of Superior Convergence Of The Ssor Method Over The Sor Method, A. Hadijidmos, Michael Neumann

Department of Computer Science Technical Reports

No abstract provided.

Optimally Computing The Shortest Weakly Visible Subedge For A Simple Polygon, Danny Z. Chen

Department of Computer Science Technical Reports

No abstract provided.

Unified Stochastic Simulations For Vector Machines: Empirical Results, Vernon J. Rego, Ling-Yu Chuang, Aditya P. Mathur

Department of Computer Science Technical Reports

No abstract provided.

Stabilty Conditions For Some Multiqueue Distributed Systems: Buffered Random Access Systems, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 8, Number 5, May 1992, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

A six page newsletter created by the Wright State University College of Engineering and Computer Science that addresses the current affairs of the college.

Computer Science Education At Wku, Malcolm Stallings

Mahurin Honors College Capstone Experience/Thesis Projects

No abstract provided.

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.

General Model Theoretic Semantics For Higher-Order Horn Logic Programming, Mino Bai, Howard A. Blair

Electrical Engineering and Computer Science - Technical Reports

We introduce model-theoretic semantics [6] for Higher-Order Horn logic programming language. One advantage of logic programs over conventional non-logic programs has been that the least fixpoint is equal to the least model, therefore it is associated to logical consequence and has a meaningful declarative interpretation. In simple theory of types [9] on which Higher-Order Horn logic programming language is based, domain is dependent on interpretation [10]. To define T p operator for a logic program P, we need a fixed domain without regard to interpretation which is usually taken to be a set of atomic propositions. We build a semantics …

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.