Physical Sciences and Mathematics Commons^™

Comparison Of Imsl/Idl With The Imsl Math Library And Exponet Graphics, Xingkang Fu, John R. Rice

Department of Computer Science Technical Reports

No abstract provided.

Topology Based Routing Algorithms For Multilayer Ic Layout Design, Moazzem Hossain

Masters Theses

In this thesis, we consider the multilayer topological routing problem and also the geometric routing problem based on topological routing solution. We show that the problem of multilayer topological planar routing for any arbitrary routing region can be modeled as a problem in a simple closed routing region. We also show that the solution to the multilayer planar routing leads to a better result of the topological via minimization problem. We present a provably-good approximation algorithm for the multilayer topological planar routing problem for different routing regions.

We also propose a graph theoretic algorithm to find 2-layer topological solutions that …

Entity Identification In Database Integration, Ee Peng Lim, Jaideep Srivastava, Satya Prabhakar, James Richardson

Research Collection School Of Computing and Information Systems

The objective of entity identification is to determine the correspondence between object instances from more than one database. Entity identification at the instance level, assuming that schema level heterogeneity has been resolved a priori, is examined. Soundness and completeness are defined as the desired properties of any entity identification technique. To achieve soundness, a set of identity and distinctness rules are established for entities in the integrated world. The use of extended key, which is the union of keys, and possibly other attributes, from the relations to be matched, and its corresponding identify rule are proposed to determine the equivalence …

Federated Autonomous Databases: Project Overview, Satya Prabhakar, Jiandong Huang, James Richardson, Jaideep Srivastava, Ee Peng Lim, Sham Navathe, Ashok Savarase, Mark Foresti

Research Collection School Of Computing and Information Systems

The paper presents an overview of an ongoing research program, Federated Autonomous Databases, sponsored by Rome Laboratory (US Air Force) and conducted by Honeywell in collaboration with the University of Minnesota and Georgia Institute of Technology. This program is exploratory in nature and is aimed at understanding and solving, within the scope of the program definition, the problem of providing integrated access to distributed, heterogeneous and autonomous databases.

Middle Terminal Cell Models For Efficient Over-The-Cell Routing, Siddharth Bhingarde

Masters Theses

In this thesis, we introduce a new class of cell models called Middle Terminal Models (MTM) which combines the advantages of existing cell models: BTM and CTM. This class contains the models 2MTM, 3MTM-V, and 3MTM+V depending on the number of metal layers and the permissibility of vias in over-the-cell areas. In MTM, two rows of terminals are located in the middle of the cell. This partitions over-the-cell area into three regions and allows allocation of more nets to over-the-cell area in congested channels. We prove that when vias are allowed over-the-cell, in "almost all" cases the MTM based layouts …

Recognition Of Quadric Surfaces From Range Data: An Analytical Approach, Ivan X. D. D'Cunha

Electrical & Computer Engineering Theses & Dissertations

In this dissertation, a new technique based on analytic geometry for the recognition and description of three-dimensional quadric surfaces from range images is presented. Beginning with the explicit representation of quadrics, a set of ten coefficients are determined for various three-dimensional surfaces. For each quadric surface, a unique set of two-dimensional curves which serve as a feature set is obtained from the various angles at which the object is intersected with a plane. Based on a discriminant method, each of the curves is classified as a parabola, circle, ellipse, hyperbola, or a line. Each quadric surface is shown to be …

Fast Fourier Transforms On Distributed Memory Parallel Machines, Anshu Dubey

Computer Science Theses & Dissertations

One issue which is central in developing a general purpose subroutine on a distributed memory parallel machine is the data distribution. It is possible that users would like to use the subroutine with different data distributions. Thus there is a need to design algorithms on distributed memory parallel machines which can support a variety of data distributions. In this dissertation we have addressed the problem of developing such algorithms to compute the Discrete Fourier Transform (DFT) of real and complex data. The implementations given in this dissertation work for a class of data distributions commonly encountered in scientific applications, known …

Time-Optimal Algorithms On Meshes With Multiple Broadcasting, Dharmavani Bhagavathi

Computer Science Theses & Dissertations

The mesh-connected computer architecture has emerged as a natural choice for solving a large number of computational tasks in image processing, computational geometry, and computer vision. However, due to its large communication diameter, the mesh tends to be slow when it comes to handling data transfer operations over long distances. In an attempt to overcome this problem, mesh-connected computers have recently been augmented by the addition of various types of bus systems. One such system known as the mesh with multiple broadcasting involves enhancing the mesh architecture by the addition of row and column buses. The mesh with multiple broadcasting …

A Performance Prediction Model For A Fault-Tolerant Computer During Recovery And Restoration, Rodrigo A. Obando

Electrical & Computer Engineering Theses & Dissertations

The modeling and design of a fault-tolerant multiprocessor system is addressed in this dissertation. In particular, the behavior of the system during recovery and restoration after a fault has occurred is investigated. Given that a multicomputer system is designed using the Algorithm to Architecture To Mapping Model (ATAMM) model, and that a fault (death of a computing resource) occurs during its normal steady-state operation, a model is presented as a viable research tool for predicting the performance bounds of the system during its recovery and restoration phases. Furthermore, the bounds of the performance behavior of the system during this transient …

Resource Utilization Model For The Algorithm To Architecture Mapping Model, Rakesh R. Patel

Electrical & Computer Engineering Theses & Dissertations

The analytical model for resource utilization, and the variable node time and conditional node model for the enhanced ATAMM model for a real-time data flow architecture, is presented in this research. The Algorithm To Architecture Mapping Model, ATAMM, is a Petri net based graph theoretic model developed at Old Dominion University, and is capable of modeling the execution of large-grained algorithms on a real-time data flow architecture. Using the resource utilization model, the resource envelope may be obtained directly from a given graph and, consequently, the maximum number of required resources may be evaluated. The node timing diagram for one …

Integrating Theory And Practice In Parallel File Systems, Thomas H. Cormen, David Kotz

Computer Science Technical Reports

Several algorithms for parallel disk systems have appeared in the literature recently, and they are asymptotically optimal in terms of the number of disk accesses. Scalable systems with parallel disks must be able to run these algorithms. We present a list of capabilities that must be provided by the system to support these optimal algorithms: control over declustering, querying about the configuration, independent I/O, turning off file caching and prefetching, and bypassing parity. We summarize recent theoretical and empirical work that justifies the need for these capabilities.

A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh

Computer Science: Faculty Publications and Other Works

This paper presents a CAD tool, SystSim, to ease the design of systolic systems. Given a high-level, functional description of processors, and a high-level description of their interconnection, SystSim will perform simulations and provide graphical output. SystSim will also perform transformations such as retiming, which eases use of the methodology of Leiserson and Saxe of designing a system with broadcasting and then obtaining a systolic system through retiming.

Difficulties Experienced Procedural Programmers Encounter When Transferring To An Object-Oriented Programming Paradigm, Scott Andrew Machaffie

Dissertations and Theses

Experienced procedural programmers seem to have difficulty when transferring from a procedural language to an object-oriented language. The problem is how to assist the experienced procedural programmers to make this shift. The long term goal of this research is to identify areas where programmers have problems and to develop an automated system to help them overcome these difficulties.

This study examines the class designs produced by procedural programmers and the effect of specifications and domain knowledge on class designs. Two types of specifications were used: those written from a procedural point of view which emphasized the functions and those written …

Comprehension Of Literate Programs By Novice And Intermediate Programmers, Christopher Forrest Bertholf

Dissertations and Theses

The studies reported herein compare comprehension of Lit style literate programs to that of traditional modular programs documented by embedded comments. Novice and intermediate programmers participated in three experiments designed to determine the comprehensibility of literate programs written using a language-independent system for abstraction-oriented literate programming compared with programs written using traditional modular programming techniques (traditional modular programs). Programs were written in either the C or FORTRAN programming language. Half of the subjects in each group received a literate program, while the other half received a traditional modular program with embedded documentation. Subjects received a problem specification, input and output …

Wright State University College Of Engineering And Computer Science Bits And Pcs Newsletter, Volume 9, Number 3, March 1993, 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.

Simulated Annealing And Optimal Codes, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Following standard notation, an (n, m, d) code C denotes a binary code C which has length n, size m, and Hamming distance d. According to Hill [6] the “main coding theory problem” is to optimize one of these three parameters when the other two are held fixed. The usual version of this optimization problem is to find the largest code for a given length and given minimum distance. This is the problem we shall consider, thus making it clear what we mean by an “optimal code.”

Smooth Splines Over Irregular Meshes Built From Few Polynomial Pieces Of Low Degree, Jörg Peters

Department of Computer Science Technical Reports

No abstract provided.

Multidatabase Atomic Commitment Protocols: A Taxonomy And Unified Approach, Ahmed K. Elmagarmid, James G. Mullen

Department of Computer Science Technical Reports

No abstract provided.

Back-Face Culling Applied To Collision Detection Of Polyhedra, George Vanĕček

Department of Computer Science Technical Reports

No abstract provided.

Supporting Distributed Transaction Dependencies And Security Constraints: A Knowledge Base Approach, Noureddine Boudriga, Omran Bukhres

Department of Computer Science Technical Reports

No abstract provided.

Finding Fixed Point Combinators Using Prolog, Richard Rankin, Ralph W. Wilkerson

Computer Science Faculty Research & Creative Works

A Powerful New Strategy, Called the Kernel Method, Has Been Developed by Larry Wos and William McCune at Argonne National Laboratories, to Study Various Fixed-Point Properties within Certain Classes of Applicative Systems. We Present a Very Simple Prolog Reasoning System, Named JIST, Which Incorporates Both Stages of the Kernel Method into a Single Unified Program. Furthermore, the Prolog Tool Has Been Extended to Run within a Distributed Environment using the Linda Protocol.

A Hybrid Genetic Algorithm For An Np-Complete Problem With An Expensive Evaluation Function, Richard Rankin, Ralph W. Wilkerson, Geoff Harris, Jo Spring

Computer Science Faculty Research & Creative Works

In This Paper, a Non-Standard Hybrid Genetic Algorithm is Presented. the Approach is Non-Standard in that It Violates Some of the Common Attributes Associated with Genetic Algorithms in the Literature. the Algorithm Presented Uses Local Maxima to Locate the Global Maximum Value, Uses Haploid Chromosomes with Dominance Mating Instead of Crossover, Generates One Offspring Per Set of Parents, Has No Specific Mutation Operator, and is Designed for Rapid Convergence. When Applied to an NP-Complete Problem, the Results of This Hybrid Algorithm Are Shown to Be Very Successful in Reducing the Complexity of the Problem.

Recovering 3d Image Parameters From Corresponding Two 2d Images, Chaman Sabharwal

Computer Science Faculty Research & Creative Works

An improved algorithm for computing the three-dimensional structure of a scene from pair of stereo images is given. The spatial relationship between the two images is not known, only the "corresponding" points in the two images are known. This problem of 3D scene reconstruction involves: (1) establishing a one-to-one correspondence between the image plane stereo pairs corresponding to the spatial points-'the correspondence problem', and (2) determining the relative orientation of the two image planes and the depth relation of spatial points with respect to the image planes. This paper assumes the first problem solved [Usikov et al. 1991] and addresses …

Development Of A Visual System Interface To Support A Domain-Oriented Application Composition System, Timothy L. Weide

Theses and Dissertations

This research designed and prototyped a visual system interface to generate, display, and modify domain-oriented application specifications. A visual system interface, called the Architect Visual System Interface (AVSI), supplements a text-based environment, called Architect, previously developed by two other students. Using canonical formal specifications of domain objects, Architect rapidly composes these specifications into a software application and executes a prototype of that application as a means to demonstrate its correctness before any programming language specific code is generated. This thesis investigates visual techniques for populating, manipulating, viewing, and composing these software application specifications within the formal object base scheme required …

An Intelligent Approach To Discrete Sampling Of Parametric Curves, Chaman Sabharwal

Computer Science Faculty Research & Creative Works

In graphics and animation applications, two of the problems are: (1) representation of an analytic curve by a discrete set of sampled points and (2) determining the similarity between two parametric curves. It is necessary to measure the accuracy of approximation and to have a metric to calculate the disparity between two parametric curves. Both of these problems have been associated with the reparameterization of the curves with respect to arc length. One of the methods uses Gaussian Quadrature to determine the arc length parameterization [Guenter and Parent 1990], while another interesting technique is a simple approximation method [Fritsch and …

Dynamic Id3: A Symbolic Learning Algorithm For Many-Valued Attribute Domains, Roger Gallion, Chaman Sabharwal, Daniel C. St. Clair, William E. Bond

Computer Science Faculty Research & Creative Works

Quinlan's ID3 machine learning algorithm induces classification trees (rules) from a set of training examples. The algorithm is extremely effective when training examples are composed of attributes whose values are taken from small discrete domains. The classification accuracy of ID3-produced trees on domains whose attributes are many-valued tends to be marginal due to the large number of possible values which may be associated with each attribute. Attempts to solve this problem by a priori grouping of attribute values into distinct subsets has met with limited success. The dynamic ID3 algorithm improves the performance of ID3 on this type of problem …

A Distributed Object-Oriented Database Application Design, Hsin-Feng Edward Wu

Theses and Dissertations

The purpose of this study is to analyze and develop a distributed object-oriented database management system (DOODBMS) application to support parallel software development of the Parallel Algorithms and Applications Group (PAAG) at AFIT. By following the software lifecycle of object-oriented paradigm, this thesis investigation is intended to generate requirements analysis, design, implementation, user interface design and implementation, and integration of the database application with the user interface. ITASCA, an existing DOODBMS platform, has been chosen to prototype the application for its distribution functionalities and object-oriented modeling power. The user interface of the database application is based on X-window OSF/Motif front-end …

Toward Reusable Graphics Components In Ada, Sam-Kyu Lim

Theses and Dissertations

This thesis demonstrates and illustrates a way of developing reusable graphics software components in Ada associated with a C++/C library. The work was carried out using object-oriented software development techniques that were used to analyze, design and implement a partial flight simulator. The objective of this thesis was to present a way of building reusable software components with Ada in a graphics application environment. An object-oriented approach was taken in the development of a set of reusable graphics software components for a flight simulator domain. A selection of a set of reusable software components came from domain analysis. These components …

Rendering The Out-The-Window View For The Afit Virtual Cockpit, W. Dean Mccarty

Theses and Dissertations

The Air Force Institute of Technology (AFIT) is developing a distributed interactive flight simulator, the Virtual Cockpit, using commercial graphics workstations and helmet mounted displays. The Virtual Cockpit communicates with other simulators via local and long-haul networks using the SIMNET protocol. The work reported in this thesis focuses on developing the terrain database for the synthetic environment and on rendering the pilot's view of the database. There are many different file formats for describing 3- dimensional geometric polygonal objects. An analysis of three formats, AFIT GEOM, the Naval Postgraduate School (NPS) DRP, and Software Systems' Flight, is presented. Each file …

Object-Oriented Database Access From Ada, Li Chou

Theses and Dissertations

Ada embodies many modern software engineering principles, namely, modifiability, efficiency, reliability, and understandability. Its powerful data abstraction allows programmers to easily model objects in the real world. A database management system (DBMS) provides long term storage. It provides a convenient and efficient environment to manipulate data. Currently, with Ada access to a DBMS is typically done through the use of a language extension and a preprocessor to convert the extensions to library calls appropriate for the DBMS. However, these systems are limited on more complex applications, such as computer-aided engineering design. Object-oriented design (OOD) is a new way of thinking …