Physical Sciences and Mathematics Commons^™

Cmap, Ken Cox, John Dehart

All Computer Science and Engineering Research

This document specifies a Connection Management Access Protocol (CMAP) for call management in high-speed packet switched networks. We target CMAP to networks employing the Asynchronous Transfer Mode (ATM) communication standard. CMAP specifies the access procedues exercised by network clients to manipulate multipoint calls; it is thus a User-Network Interface (UNI) signalling protocol. We define a multipoint call as a group of multipoint connections. A multipoint connection is a communication channel between two or more clients or endpoints of the network, where all data sent by one client is received by all other clients who have elected to receive. A point-to-point …

Performance Comparison Of Asynchronous Adders, Mark A. Franklin, Tienyo Pan

All Computer Science and Engineering Research

In asynchronous systems, average function delays principally govern overall throughput. This paper compares the performance of six adder designs with respect to their average delays. Our results show that asynchronous addres (32 or 64-bits) with a hybrid structure (e.g., carry-select addres) run 20-40% faster than simple ripple-carry addres. Hybrid adders also outperform high-cost, strictly synchronous conditional-sum adders.

Speculative Computation: Overcoming Communication Delays In Parallel Algorithms, Vasudha Govindan, Mark A. Franklin

All Computer Science and Engineering Research

Communication latencies and delays are a major source of performance degradation in parallel computing systems. It is importnat to "mask" these communication delays by overlapping them with useful computation in order to obtain good parallel performance. This paper proposes speculative computation as a technique to mask communication latencies. Speculative computation is discussed in the context of synchronous iterative algorithms. Processors speculate the contents of messages that are not hyet received and perform computation based on the speculated values. When the messages are received, they are compared with the speculated values and, if the error is unacceptable, the resulitng computation is …

Morphing Binary Trees, John Hershberger, Subhash Suri

All Computer Science and Engineering Research

We investigate the problem of transforming one binary tree into another by rotatoins, subject to certain weight ocnstraints on the nodes of the trees. These constraints arise in the problem of "morphing" one simple polygon to another simple polygon by continuous deformatinos (translations and scalings) that preserve the turn angles and the simplicity of the polygon; the two polygons must have the same sequence of turn angles. Our main theorem is that two arbitrary n-leaf binary trees satisfying our weight constraint can be morphed into each other with O(n log n) rotations. Furthermore, we also present an O(n log n) …

Practical Methods For Approximating Shortest Paths On A Convex Polytope In R3, John Hershberger, Subhash Suri

All Computer Science and Engineering Research

We propose a n extremely simple approximation scheme for computing shortest paths on the surface of a convex polytope in three dimensions. Given a convex polytope P with n vertices and two points p,q on its surface, let dp (p,q) denote the shortest path distance between p and q on the surface of P. Our algorithm produces a path of length at most 2 × dp(p,q) in time O(n). Extending this results, we can also compute ana pproximation of the shortest path tree rooted at an arbitrary point χ Є P in time O(n log n). In the approximate tree, …

Distributed Data Layout, Scheduling And Playout Control In A Large Scale Multimedia Storage Server, Milind M. Buddhikot, Guru Parulkar

All Computer Science and Engineering Research

No abstract provided.

An Incremental Distributed Algorithm For Computing Biconnected Components, Bala Swaminathan, Kenneth J. Goldman

All Computer Science and Engineering Research

This paper describes a distributed algorithm for computing the biconnected components of a dynamically changing graph. Our algorithm has a worst case communication complexity of O(b + c) messages for an edge insertion and O(b' + c) messages for an edge removal, and a worst case time complexity of O(c) for both operations, where c is the maximum number of biconnected components in any of the connected components during the operation, b is the number of nodes in the biconnected component containing the new edge, and bprime is the number of nodes in the biconnected component in which the update …

Connection Management In Reconfigurable Distributed Systems, Bala Swaminathan

All Computer Science and Engineering Research

The Programmer's Playground takes a new approach to simplifying and supporting the construction of distributed applications. The approach, called I/O abstraction, separates the description of a system's communication structure from the descriptions of its computational components so that software modules written in existing programming languages cna be integrated flexibly and dynamically by both programmers and end-users. This separation is achieved by estabishing logical connectinos among the data interfaces of independent software modules. The logical connections provide a uniform high-level view of communication for both discrete and continuous data. The I/O abstraction approach inherits ideas from the I/O automaton model, a …

Issues And Obstacles With Multimedia Authoring, Fillia Makedon, Samuel A. Rebelsky, Matthew Cheyney, Charles Owen, Peter Gloor

Dartmouth Scholarship

Unlike traditional authoring, multimedia authoring involves making hard choices, forecasting technological evolution and adapting to software and hardware technology changes. It is, perhaps, an unstable field of endeavor for an academic to be in. Yet, it is important that academics are, in fact, part of this process. This paper discusses some of the common threads shared by three dissimilar cases of multimedia authoring which we have experimented with, that of multimedia conference proceedings, multimedia courseware development and multimedia information kiosks. We consider these applications from an academic point of view and review the benefits and pitfalls of academic development while …

Generalized Ffts - A Survey Of Some Recent Results, David K. Maslen, Daniel N. Rockmore

Dartmouth Scholarship

In this paper we survey some recent work directed towards generalizing the fast Fourier transform (FFT). We work primarily from the point of view of group representation theory. In this setting the classical FFT can be viewed as a family of efficient algorithms for computing the Fourier transform of either a function defined on a finite abelian group, or a bandlimited function on a compact abelian group. We discuss generalizations of the FFT to arbitrary finite groups and compact Lie groups.

Disk-Directed I/O For Mimd Multiprocessors, David Kotz

Dartmouth Scholarship

Many scientific applications that run on today's multiprocessors are bottlenecked by their file I/O needs. Even if the multiprocessor is configured with sufficient I/O hardware, the file-system software often fails to provide the available bandwidth to the application. Although libraries and improved file-system interfaces can make a significant improvement, we believe that fundamental changes are needed in the file-server software. We propose a new technique, \em disk-directed I/O, that flips the usual relationship between server and client to allow the disks (actually, disk servers) to determine the flow of data for maximum performance. Our simulations show that tremendous performance gains …

A Semantic Framework For Understanding The Behavior Of Modules And Classes In Programming Languages, Mahesh Dodani, Benjamin Kok Siew Gan

Research Collection School Of Computing and Information Systems

Recent trends in programming language design and implementation are aimed at integrating the two most important constructs to combat complexity: modules and classes. Both constructs provide encapsulation, a cornerstone of reliable programming. These constructs differ in their approach to building hierarchies: modules define visibility of components while classes define visibility of functionality. How can modules and classes be effectively integrated within a simple programming language? This question captures the essence of developing semantics of these constructs to ensure that they interact in a meaningful way. This paper develops a formal denotational semantic framework for understanding the interaction between classes and …

A Study Of The Approaches And Attitudes Of Information Systems Executives To Measuring Information Systems Effectiveness, Falantina Tjakra

Theses: Doctorates and Masters

The purpose of the research is to examine the attitudes of IS executives to the current and future importance of some of the approaches to measuring IS efficiency and IS effectiveness in large Australian organisations. The study identified the nature of IS effectiveness approaches along the lines of whether they are business-oriented, IS internal/operational, financial, quantitative or qualitative measures. It also examined whether the structure of the IS management and industry sector had an effect on attitudes towards these measures.

Software Metrics For Monitoring Software Engineering Projects, Edwin C. Lim

Theses: Doctorates and Masters

As part of the undergraduate course offered by Edith Cowan University, the Department of Computer Science has (as part of a year's study) a software engineering group project. The structure of this project was divided into two units, Software Engineering l and Software Engineering 2. ln Software Engineering 1, students were given the group project where they had to complete and submit the Functional Requirement and Detail System Design documentation. In Software Engineering 2, students commenced with the implementation of the software, testing and documentation. The software was then submitted for assessment and presented to the client. To aid the …

The Management Of Information Technology Investments In The Australian Ambulance Services, Anthony J. Ahern

Theses: Doctorates and Masters

Information Technology plays a significant role in the administration and operation of most organisations today. This is certainly the case with each of the Australian Ambulance Services. With the rapid increase in the use of Information Technology and the expectation about its use by both staff and the general public, the Ambulance Service managements' are faced with the dilemma of trying to ensure that their organisations are able to get the full advantage of advances in Information Technology and at the same time ensure that investments in IT are maintained at appropriate levels that will ensure the maximum return on …

Applications Of Fuzzy Counterpropagation Neural Networks To Non-Linear Function Approximation And Background Noise Elimination, I. M. Wiryana

Theses: Doctorates and Masters

An adaptive filter which can operate in an unknown environment by performing a learning mechanism that is suitable for the speech enhancement process. This research develops a novel ANN model which incorporates the fuzzy set approach and which can perform a non-linear function approximation. The model is used as the basic structure of an adaptive filter. The learning capability of ANN is expected to be able to reduce the development time and cost of the designing adaptive filters based on fuzzy set approach. A combination of both techniques may result in a learnable system that can tackle the vagueness problem …

A Model Of Visual Recognition Implemented Using Neural Networks, Vincent C. Phillips

Theses: Doctorates and Masters

The ability to recognise and classify objects in the environment is an important property of biological vision. It is highly desirable that artificial vision systems also have this ability. This thesis documents research into the use of artificial neural networks to implement a prototype model of visual object recognition. The prototype model, describing a computtional architecture, is derived from relevant physiological and psychological data, and attempts to resolve the use of structural decomposition and invariant feature detection. To validate the research a partial implementation of the model has been constructed using multiple neural networks. A linear feed-forward network performs pre-procesing …

Skin Cancer Diagnosis Using Hierarchical Neural Networks And Fuzzy Logic, Hsi-Chieh Lee

Masters Theses

"Skin cancer, the most common cancer in the United States that affects about 600,000 Americans every year, accounts for 1 % of all cancer deaths. Among all, Malignant Melanoma is the most virulent form of skin cancer that is responsible for 75% of all deaths from skin cancer. In 1992, approximately 32,000 people are expected to develop melanoma and about 6,700 will die. However, even malignant melanoma can be treated successfully if detected in the early phase. Therefore, our research goal is to diagnose skin cancer, especially malignant melanoma.

In this study, only the digitized images obtained from color tumor …

Multithreaded Computer Architecture: A Summary Of The State Of The Art, Robert Iannucci, Guang Gao, Robert Halstead, Burton Smith

Robert A Iannucci

No abstract provided.

Technology Transfer At Motorola, Robert Yacobellis

Robert H Yacobellis

No abstract provided.

The Variable Elision Of Unstressed Vowels In European Portuguese: A Case Study, David James Silva

David Silva

A Simulated Annealing/Tabu Search Algorithm For The Vehicle Routing Problem, Jeffrey Dale White, Billy E. Gillett

Computer Science Technical Reports

The Vehicle Routing Problem is an NP-complete problem that has been studied extensively since it was introduced in 1958 by G. B. Dantzig and J. H. Ramser. This thesis creates three algorithms that endeavor to find an optimal solution for each problem tested. Two of the algorithms (Simulated Annealing and Tabu Search) have been used previously to solve this problem. These two solution methods are revisited to discover whether a new approach to creating routes will produce the best-known optimal values every time. New routes are created by forming route neighborhoods and then selecting cities from these neighborhoods for insertion. …

Process Driven Software Engineering Environments, John Hayes Lampkin, T. Lo, Daniel C. St. Clair

Computer Science Technical Reports

Software development organizations have begun using Software Engineering Environments (SEEs) with the goal of enhancing the productivity of software developers and improving the quality of software products. The encompassing nature of a SEE means that it is typically very tightly coupled with the way an organization does business. To be most effective, the components of a SEE must be well integrated and the SEE itself must be integrated with the organization.

The challenge of tool integration increases considerably when the components of the environment come from different vendors and support varying degrees of “openness”. The challenge of integration with the …

Subsumption In Modal Logic, Dirk Heydtmann, Ralph W. Wilkerson

Computer Science Technical Reports

Subsumption has long been known as a technique to detect redundant clauses in the search space of automated deduction systems for classical first order logic. In recent years several automated deduction methods for non-classical modal logics have been developed. This thesis explores, how subsumption can be made to work in the context of these modal logic deduction methods.

Many modern modal logic deduction methods follow an indirect approach. They translate the modal sentences into some other target language, and then determine whether there exists a proof in that language, rather than doing deduction in the modal language itself. Consequently, subsumption …

The Difficulty Of Approximating The Chromatic Number For Random Composite Graphs, Jeffrey Wayne Jenness, Billy E. Gillett

Computer Science Technical Reports

Combinatorial Optimization is an important class of techniques for solving Combinatorial Problems. Many practical problems are Combinatorial Problems, such as the Traveling Salesman Problem (TSP) and Composite Graph Coloring Problem (CGCP). Unfortunately, both of these problems are NP-complete and it is not known if efficient algorithms exist to solve these problems. Even approximation with guaranteed results can be just as difficult. Recently, many generalized search techniques have been developed to improve upon the solutions found by the heuristic algorithms.

This paper presents results for CGCP. In particular, exact and heuristic algorithms are presented and analyzed. This study is made, to …

A Syntax-Directed Editor For Borland’S Turbo Pascal, John Gatewood Ham, Thomas J. Sager

Computer Science Technical Reports

This study details the design and implementation of the LSD program, a syntax-directed editor for use in editing the source code for Borland’s Turbo Pascal. LSD is a dual-mode editor which allows both traditional text editing and also grammar-based editing. LSD promotes better programming for novice users by allowing the user to edit the program with a graphical representation of a parse tree. A list of syntactically correct choices is displayed at each point where a choice must be made in the structure of the program. Since only these choices are available, no syntax errors are possible. For more advanced …

Fault-Tolerant Ring Embeddings In Hypercubes -- A Reconfigurable Approach, Jun-Lin Liu, Bruce M. Mcmillin

Computer Science Technical Reports

We investigate the problem of designing reconfigurable embedding schemes for a fixed hypercube (without redundant processors and links). The fundamental idea for these schemes is to embed a basic network on the hypercube without fully utilizing the nodes on the hypercube. The remaining nodes can be used as spares to reconfigure the embeddings in case of faults. The result of this research shows that by carefully embedding the application graphs, the topological properties of the embedding can be preserved under fault conditions, and reconfiguration can be carried out efficiently.

In this dissertation, we choose the ring as the basic network …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 10, December 1993, College Of Engineering And Computer Science, Wright State University

BITs and PCs Newsletter

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

Probing Tcp Implementations, Douglas E. Comer, John C. Lin

Department of Computer Science Technical Reports

No abstract provided.

An Optimal O(Log Log N) Time Parallel Algorithm For Detecting All Squares In A String, Albert Apostolico, Dany Breslauer

Department of Computer Science Technical Reports

No abstract provided.