Digital Commons Network^™

Asymptotic Properties Of Data Compressions And Suffix Trees, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Performance Of Pde Sparse Solvers On Hypercubes, Mo Mu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

A Spatial Index For Convex Simplicial Complexes In D Dimensions, George Vanĕček, Vincenzo Ferrucci

Department of Computer Science Technical Reports

No abstract provided.

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, January 1991, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

Type 3 Diminimal Maps On The Torus, Adrian Riskin

Mathematics

A polyhedral map on the torus is diminimal if either shrinking or removing an edge yields a nonpolyhedral map. We show that all such maps on the torus fall into one of two classes, type 2 and type 3, and show that there are exactly two type 3 ones, which are given explicitly.

Analyzing Images Containing Multiple Sparse Patterns With Neural Networks, Rangachari Anand, Kishan Mehrotra, Chilukuri K. Mohan, Sanjay Ranka

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

We have addressed the problem of analyzing images containing multiple sparse overlapped patterns. This problem arises naturally when analyzing the composition of organic macromolecules using data gathered from their NMR spectra. Using a neural network approach, we have obtained excellent results in using NMR data to analyze the presence of various amino acids in protein molecules. We have achieved high correct classification percentages (about 87%) for images containing as many as five substantially distorted overlapping patterns.

Scatter Scheduling For Problems With Unpredictable Structures, Min-You Wu, Wei Shu

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

An extended scatter scheduling was applied to problems with unpredictable, asynchronous structures. It has been found that with this simple scheduling strategy, good load balance can be reached without incurring much runtime overhead. This scheduling algorithm has been implemented on hypercube machines, and its performance is compared with other scheduling strategies.

Disjoint Covers In Replicated Heterogeneous Arrays, P.K. Mckinley, N. Hasan, Ran Libeskind-Hadas, C.L. Liu

All HMC Faculty Publications and Research

Reconfigurable chips are fabricated with redundant elements that can be used to replace the faulty elements. The fault cover problem consists of finding an assignment of redundant elements to the faulty elements such that all of the faults are repaired. In reconfigurable chips that consist of arrays of elements, redundant elements are configured as spare rows and spare columns.

This paper considers the problem in which a chip contains several replicates of a heterogeneous array, one or more sets of spare rows, and one or more sets of spare columns. Each set of spare rows is identical to the set …

Selection Networks, Nicholas Pippenger

All HMC Faculty Publications and Research

An upper bound asymptotic to $2n\log _e n$ is established for the number of comparators required in a network that classifies $n$ values into two classes, each containing $n / 2$ values, with each value in one class less than or equal to each value in the other. (The best lower bound known for this problem is asymptotic to $(n / 2)\log _2 n$.)

Performance Prediction For Distributed Load Balancing On Multicomputer Systems, Ishfaq Ahmed, Arif Ghafoor, Kishan Mehrotra

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents a performance evaluation approach to compare different distributed load balancing schemes on a unified basis. This approach is an integration of simulation, statistical and analytical models, and takes into account the fundamental system parameters that can possibly affect the performance. We show that all the sender-initiated distributed load balancing strategies can be modeled by a central server open queuing network. Furthermore, these load balancing strategies can be characterized by only two queuing parameters – the average execution queue length and the probability that a newly arrived task is executed locally or migrated to another node. To capture …

Three--Dimensional Medical Imaging: Algorithms And Computer Systems, M. R. Stytz, G. Frieder, O. Frieder

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

This paper presents an introduction to the field of three-dimensional medical imaging It presents medical imaging terms and concepts, summarizes the basic operations performed in three-dimensional medical imaging, and describes sample algorithms for accomplishing these operations. The paper contains a synopsis of the architectures and algorithms used in eight machines to render three-dimensional medical images, with particular emphasis paid to their distinctive contributions. It compares the performance of the machines along several dimensions, including image resolution, elapsed time to form an image, imaging algorithms used in the machine, and the degree of parallelism used in the architecture. The paper concludes …

Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney

Electrical Engineering and Computer Science - Technical Reports

Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in Ө (log nlogm) time with Ө (mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less …

Average Dependence And Random Oracles (Preliminary Report), Stuart A. Kurtz, Stephen R. Mahaney, James S. Royer

Electrical Engineering and Computer Science - Technical Reports

This paper is a technical investigation of issues in computational complexity theory relative to a random oracle. We introduce “average dependence,” an alternative method to Bennett and Gill’s “measure preserving map" technique and illustrate our technique by the following results.

A Model-Based Approach For Organizing Quantitative Computations, J. Sticklen, A. Kamel, William E. Bond

Computer Science Faculty Research & Creative Works

Model based reasoning (MBR) is currently receiving wide spread attention because it offers a way to circumvent the brittleness of reasoning systems built solely on associational knowledge. To date, most MBR approaches have focused on the use and manipulation of qualitative models. The authors report their experience in applying techniques of functional reasoning to the general problem of organizing quantitative calculations. As a testbed, they have solved a problem initially posed at the Model-Based Diagnosis workshop (Paris, July, 1989): representing an automotive cruise control system. The results show that the principles of the functional reasoning approach can provide leverage in …

Simulating Adaptive Load Sharing Policies On An Ipsc/2 Multicomputer, Yuh Jong Hu, Billy E. Gillett

Computer Science Faculty Research & Creative Works

Unlike most other adaptive load sharing (LS) policy studies, each node in the distributed system is modeled as a central server model represented by a closed queueing network (QN). The primary objective of this study is to use a simulation model to find the improvement for an adaptive LS policy in a distributed system. In homogeneous distributed systems, the simulation results in this study show that the performance improvements between no LS, LS with task placement, and LS with task migration are very small. These results are quite different from other studies, which show a significant improvement of mean response …

Fault-Tolerant Parallel Matrix Multiplication With One Iteration Fault Detection Latency, Chul Eui Hong, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

The checksum technique is a low-cost method to detect errors in matrix operations performed by processor arrays. The fault detection of this method is done only at problem termination, so this method is not an effective fault tolerance technique for large scale matrix multiplication. This paper presents a new algorithm, the ID algorithm, which minimizes the fault-detection latency, In the ID algorithm, a fault is detected as soon as the fault occurs instead of at problem termination. For n2 processors, the fault-latency time of the ID algorithm is l/n of that of checksum algorithm with a run-time penalty of O(nlog2n) …

Pattern Recognition For Nondestructive Evaluation, S. Morris, P. O'Rorke, William E. Bond, M. M. Amirfathi, Daniel C. St. Clair

Computer Science Faculty Research & Creative Works

The issues involved in automating nondestructive evaluation (NDE) techniques are outlined. Attention is given to research focused on the application of machine learning techniques to the construction and maintenance of knowledge-based systems which are capable of evaluating the readings from nondestructive tests that have been performed on aircraft components. Preliminary results obtained from this research are described. In particular, the authors discuss the application of a symbolic machine learning algorithm, ID3, to the NDE problem. ID3 has been used by Douglas Aircraft to classify defects in sets of standard NDE reference blocks. Based on the preliminary results, a need for …

A Decentralized Task Scheduling Algorithm And Its Performance Modeling For Computer Networks, Ishfaq Ahmad, Arif Ghafoor, Kishan Mehrotra

College of Engineering and Computer Science - Former Departments, Centers, Institutes and Projects

A dynamic task scheduling algorithm, that is stable, de-centralized, and adaptive to network topology, is presented. The proposed algorithm is an extension of nearest neighbor load balancing strategy with an enhanced degree of efficiency and it is intended for multicomputers connected by a store and forward communication network. The proposed algorithm is modeled by a central server open queuing network. It is shown that the response time of a task consists of two parts. The first part comprises a task‘s settling time which consists of scheduling time, communication time, and waiting time in scheduling and communication queues. The second part …

Supereuleriaun Graphs And The Petersen Graph, Zhi-Hong Chen

Scholarship and Professional Work - LAS

Using a contraction method, we find some best-possible sufficient condi­tions for 3-edge-connected simple graphs such that either the graphs have spanning eulerian subgraphs or the graphs are contractible to the Petersen graph.

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

Computer Science Faculty Research & Creative Works

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. 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 Faces have been selected to …

Functional Reasoning And Functional Modelling, J. Sticklen, William E. Bond

Computer Science Faculty Research & Creative Works

A car that will not start on a cold winter day and one that will not start on a hot summer day usually indicate two very different situations. When pressed to explain the difference, we would give a winter account- "Oil is more viscous in cold conditions, and that causes . . .'' -and a summer story- "Vapor lock is a possibility in hot weather and is usually caused by . . .'' How do we build such explanations? One possibility is that understanding how the car works as a device gives us a basis for generating the explanations. But …

Implementing A Neural Network In The Smalltalk Graphical Environment, John M. Damgaard

Presidential Scholars Theses (1990 – 2006)

Interest in artificial neural networks has grown rapidly over the past few years. The technology is intriguing and the potential applications of the technology are exciting and diverse. Another area of growing interest in the computer science field is that of object-oriented programming. The object-oriented paradigm is a very powerful tool which can improve software quality and streamline the development process. The most common object-oriented language is Smalltalk. I feel that Smalltalk is an excellent platform on which to implement artificial neural networks.

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 …

An Object-Oriented Learning/Design Support Environment, Fillia Makedon, Julie C. Jumes, Jill P. David

Computer Science Technical Reports

We present an object-oriented experimental learning and design support environment, call AVT, for an Algorithm Visualization Tool, implemented in Digitalk's Smalltalk/V1 on a Macintosh II2, AVT provides a domain- independent visualization tool, an exploratory learning environment, and an experimental heuristic design environment. Algorithm visualization is the exploration of ways to visualize intuitively the computational behavior of an algorithm using multiple views, some of which are visual in the graphical sense [2,4]. AVT employs other views (combining text and graphics) to explain the problem, the strategy, the heuristics, and the reasoning process behind the solutions. User interaction in AVT includes not …

A Metric Towards Efficient Exhaustive Test Pattern Generation, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

A viable technique [7] in built-in self-test (BIST)[2] is to generate test patterns pseudo-exhaustively by using linear feedback shift registers (LFSR's). The goal is to find an appropriate primitive polynomial of degree d that will generat 2d test patterns in order to exercise all circuit outputs simultaneously. In an attempt to reduce the degree d of the polynomial the following strategy was proposed in [6,5]. In the first phase, partition the circuit into segments by inserting a small number of register cells, so that the input dependency of any circuit element in the segments is no more than d. Then, …

On Minimizing Hardware Overhead For Exhaustive Circuit Testability, Dimitrios Kagaris, Fillia Makedon, Spyros Tragoudas

Computer Science Technical Reports

Exhaustive built-in self testing is given much attention as a viable technique in the context of VLSI technology. In this paper, we present heuristic in order to make exhaustive testing of combinational circuits practical. The goal is to place a small number of register cells on the nets of the input circuit so that the input dependency of combinational elements in the circuit is less than a small given integer k. Our heuristic guarantees that each output can be individually tested with 2k test patterns and can be used as a subroutine to generat efficient test patterns to test all …

Privacy-Enhanced Electronic Mail, Matt Bishop

Computer Science Technical Reports

The security of electronic mail sent through the Internet may be described in exactly three words: there is none. The Privacy and Security Research Group has recommended implementing mechanisms designed to provide security enhancements. The first set of mechanisms provides a protocol to provide privacy, integrity, and authentication for electronic mail; the second provides a certificate-based key management infrastructure to support key distribution throughout the internet, to support the first set of mechanisms. This paper describes these mechanisms, as well as the reasons behind their selection and how these mechanisms can be used to provide some measure of securtiy in …

Implementation Notes On Bdes(1), Matt Bishop

Computer Science Technical Reports

This note describes the implementation of bdes, the file encryption program being distributed in the 4.4 release of the Berkeley Software Distribution. It implements all modes of the Data Encryption Standard program.

Connected Components In O(Lg3/2|V|) Parallel Time For The Crew Pram, Donald B. Johnson, Panagiotis Metaxas

Computer Science Technical Reports

Computing the connected components of an undirected graph G = (V,E) on |V| = n vertices and |E| = m edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs on O(lg2n) time using n2/lg2n processors [CLC82,HCS79]. For the CRCW PRAM model in which concurrent writing is permitted, the best known algorithm runs in O(lg n) time using almost (n+m)/lg n processors [SV82,CV86,AS87]. Unfortunately, simulating this algorithm on the weaker CREW model increases its running time to O(lg2n) [CDR86, KR90,Vis83]. We present here an efficient and simple algorithm that runs in O(lg 3/2n) …