Digital Commons Network^™

Asymptotically Fast Algorithms For Spherical And Related Transforms, James R. Driscoll, Dennis M. Healy

Computer Science Technical Reports

This paper considers the problem of computing the harmonic expansion of functions defined on the sphere. We begin by proving convolution theorems that relate the convolution of two functions on the sphere to a "multiplication" in the sprectral domain, as well as the multiplication of two functions on the sphere to a "convolution" in the spectral domain. These convolution theorems are then used to develop a sampling theorem on the sphere.

Library Automation In South Carolina Media Centers, Nellita P. Dubose

CCAC Theses and Dissertations

This investigation, which was started in April, 1988, was designed to assess the extent of automation in academic and public libraries and school library media centers in the state of South Carolina as well as the prevailing attitude toward library automation. School media specialists were surveyed at their annual convention, and public and academic librarians were mailed the same surveys to ascertain the percentage of media centers in the process of automating a part or all its processes and to determine their attitude toward library automation. From the results of the study, one sees that the direction of library automation …

Teacher Utilization Of A Middle School Media Program: A Case Study, Earnestine T. Mccloud

CCAC Theses and Dissertations

The goal of this research study was to determine the effectiveness of the media center within the school environment. The components of the media center program that should be strengthened were identified. The role of the media center, teachers, and staff in facilitating media center goals and objectives were evaluated.

Permission to survey teachers of the Lemmel Middle School was granted by the assistant Superintendent of Planning and Research. The letter of introduction, the questionnaire, directions for completing the questionnaire, and self-addressed, return envelopes were placed in the teachers' mailboxes.

To facilitate in the processing of the questionnaires, the data …

An Inexpensive Electronic Viewbox, J. R. Cox Jr., R. G. Jost, T. Monsees, S. Ramamurthy, M. Karlsson

All Computer Science and Engineering Research

An "electronic viewbox" is described that has been designed to meet the demand for a modestly priced soft-copy display for radiology. Issues associated with spatial resolution, intensity resolution, image magnification, user interface, digital communications and possible applications are discussed.

Determinism And Connectionism In A Rule-Based Natural Language System, Stan C. Kwasny, Kanaan A. Faisal

All Computer Science and Engineering Research

The processing of Natural Language is, at the same time, natural symbolic and naturally symbolic and naturally sub-symbolic. It is symbolic because ultimately symbols play a critical role. Writing systems, for example, owe their existence to the symbolic nature of language. It is also sub-symbolic because of the nature of speech, the fuzziness of concepts, and the high degree of parallelism that is difficult to explain as a purely symbolic phenomenon. This report details a set of experiments which support the claim that Natural Language can be syntactically processed in a robust manner using a connectionist deterministic parser. The model …

The Next Generation Of Internetworking, Gurudatta M. Parulkar

All Computer Science and Engineering Research

This paper describes a research effort concerned with the design of the next generation of internet architecture, which has been necessitated by two emerging trends. First, there will be at least a few orders of magnitude increase in data rates of communication networks in the next few years. For example, researchers are already prototyping networks with data rates of up to a few hundred Mbps, and are planning networks with data rates up to a few Gbps. Second, researchers from all disciplines of science, engineering, and humanities plan to use the communication infrastructure to access widely distributed resources in order …

Computing Hough Transforms On Hypercube Multicomputers, Sanjay Ranka, Sartaj Sahni

Electrical Engineering and Computer Science - Technical Reports

Efficient algorithms to compute the Hough transform on MIMD and SIMD hypercube multicomputers are developed. Our algorithms can compute p angles of the Hough transform of an N x N image, p ≤ N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N2) processors. We also consider the computation of the Hough transform on MIMD hypercubes with a fixed number of processors. Experimental results on an NCUBE/7 hypercube are presented.

Edge Contours, Donna J. Williams

Retrospective Theses and Dissertations

The accuracy with which a computer vision system is able to identify objects in an image is heavily dependent upon the accuracy of the low level processes that identify which points lie on the edges of an object. In order to remove noise and fine texture from an image, it is usually smoothed before edge detection is performed. This smoothing causes edges to be displaced from their actual location in the image. Knowledge about the changes that occur with different degrees of smoothing (scales) and the physical conditions that cause these changes is essential to proper interpretation of the results …

Automated Translation Of Digital Logic Equations Into Optimized Vhdl Code, John Evan Stark

Masters Theses

"It was desired to develop an algorithm for the automated translation of' finite slate machines from state table form to optimized VHDL form. To do this, algorithms arc needed for reducing the state machine to simplest form, making state assignments, producing minimal logic equations to represent the state machine, and producing VHDL code which describes the intended circuit. Various such algorithms were examined and a prototype program written to perform this translation"--Abstract, page ii.

Automatically Generating Functional Tests From Specifications - A Knowledge Based Constraint Logical Programming Approach, Ji Chen

Computer Science Theses & Dissertations

Recent experimental results indicate that functional testing is one of the most effective methods in detecting certain classes of faults. Very little work has been done in automating functional testing. This thesis research develops a method, called hierarchical partition, for automating functional testing. The key to our approach is the utilization of a pre-existing knowledge base about the domain of discourse. Several approaches to knowledge organiza­tion are discussed along with the resulting effects on the quantity and quality of functional tests produced. This research is an application and development of Generic Constraint Logic Programming and the Knowledge Driven …

The Algorithm Mapper: A System For Modeling And Evaluating Parallel Applications/Archicture Pairs, C. E. Houstis, Elias N. Houstis, John R. Rice, S. M. Samartzis, D.L. Alexandrakis

Department of Computer Science Technical Reports

No abstract provided.

Evaluation Of Concurrent Pools, David Kotz, Carla Ellis

Dartmouth Scholarship

The assignment of resources or tasks to processors in a distributed or parallel system needs to be done in a fashion that helps to balance the load and scales to large configurations. In an architectural model that distinguishes between local and remote data access, it is important to base these allocation functions on a mechanism that preserves locality and avoids high-latency remote references. This paper explores performance considerations affecting the design of such a mechanism, the Concurrent Pools data structure. We evaluate the effectiveness of three different implementations of concurrent pools under a variety of stressful workloads. Our experiments expose …

Design Of Parity Testable Combinational Circuits, Bhargab B. Bhattacharya, Sharad C. Seth

School of Computing: Faculty Publications

The parity testability of a single output is related to its partition in terms of maximal supergates and then a scheme is proposed for making an untestable circuit parity testable by augmenting its maximal supergates. Only a small amount of extra logic and a single external test-mode pin is required to complete the design. The test procedure is simple and the hardware overhead is low.

A Theory Of Testability With Application To Fault Coverage Analysis, Sharad C. Seth, Vishwani Agrawal, Hassan Farhat

School of Computing: Faculty Publications

When test vectors are applied to a circuit, the fault coverage increases. The rate of increase, however, could be circuit-dependent. In fact, the actual rise of fault coverage depends on the characteristics of vectors, as well as, on the circuit. The paper shows that the average fault coverage can be computed from circuit testability. A relationship between fault coverage and circuit testability is derived. The mathematical formulation allows computation of coverage for deterministic and random vectors. Applications of this analysis include: determination of circuit testability from fault simulation, coverage prediction from testability analysis, prediction of test length, and test generation …

Testability Analysis Of Synchronous Sequential Circuits Based On Structural Data, Raghu V. Hudli, Sharad C. Seth

School of Computing: Faculty Publications

Bounds on test sequence length can be used as a testability measure. We give a procedure to compute the upper bound on test sequence length for an arbitrary sequential circuit. We prove that the bound is exact for a certain class of circuits. Three design rules are specified to yield circuits with lower test sequence bounds.

A Microcomputer-Based Cia System Designed To Compliment Traditional Instruction In Navy Technical Training, John M. Kaiser

CCAC Theses and Dissertations

A prototype microcomputer-based CBI program was developed to provide review, structured self-study, and remediation to students undergoing initial skills training at the Naval Air Technical Training Center (NATTC), Lakehurst, NJ. The program demonstrates the capabilities of the authoring (LSAUT) and delivery (LSSTU) programs that are parts of the Language Skills Computer Aided Instruction (LSCAI) system developed by the Navy Personnel Research and Development Center and the University of Utah. A course of instruction at NATTC, Lakehurst was selected for this project on the basis of level of training, student throughput, attrition and setback rates, and category of learning objectives. Student …

Graph Coloring Algorithms On Random Graphs, Shi-Jen Lin

Doctoral Dissertations

"The graph coloring problem, which is to color the vertices of a simple undirected graph with the minimum number of colors such that no adjacent vertices are assigned the same color, arises in a variety of scheduling problems. This dissertation focuses attention on vertex sequential coloring. Two basic approaches, backtracking and branch-and-bound, serve as a foundation for the developed algorithms. The various algorithms have been programmed and applied to random graphs. This dissertation will present several variations of the Korman algorithm, Korw2, Pactual, and Pactmaxw2, which produce exact colorings quicker than the Korman algorithm in the average for some classes …

The Directed Steiner Problem On Graphs: A Simulated Annealing Approach, Lawrence Joseph Osborne

Doctoral Dissertations

"The well-known Steiner Problem on Graphs is an NP-complete problem for which there are many heuristic and exact algorithms that are deterministic. In this dissertation a new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing. A version of annealing is developed for the Directed Steiner Problem and compared with one of the best general annealing schemes. Then a comparison is made between simulated annealing and the traditional branch and bound technique. The dual ascent algorithm of Richard T. Wong is used to …

An Investigation Into The Use Of Prolog For Chinese-English Translation, J. W. L. Millar

Research outputs pre 2011

In order to undertake machine translation from Chinese to English, it is necessary to accomplish three tasks. Firstly, the Chinese characters need to be handled on the computer system in use - in this case an IBM PC/XT. Secondly, the grammar for the language has to be represented and here Prolog has been used with a Definite Clause Grammar. Finally, the lexicon must be stored in a manner that facilitates efficient retrieval. Arity Prolog provides a hash table that achieves this task. This report describes the current state of a project aimed at producing a Chinese English machine translation system.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Computer Science: Faculty Publications and Other Works

Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda + lg n lg lg n) with probability 1-O(1/n). The best previous …

Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg

Computer Science: Faculty Publications and Other Works

There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.

Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein

Computer Science: Faculty Publications and Other Works

No abstract provided.

A New Conjecture About Minimal Imperfect Graphs, H. Meyniel, Stephan Olariu

Computer Science Faculty Publications

H. Meyniel proved that in every minimal imperfect graph, every pair of vertices is joined by a chordless path containing an odd number of edges. We conjectured that in every minimal imperfect graph, every pair of vertices is joined by a path containing an even number of edges. We give an equivalent version of this new conjecture.

The Strong Perfect Graph Conjecture For Pan-Free Graphs, Stephan Olariu

Computer Science Faculty Publications

A graph G is perfect if for every induced subgraph F of G, the chromatic number χ(F) equals the largest number ω(F) of pairwise adjacent vertices in F. Berge's famous Strong Perfect Graph Conjecture asserts that a graph G is perfect if and only if neither G nor its complement G contains an odd chordless cycle of length at least five. Its resolution has eluded researchers for more than twenty years. We prove that the conjecture is true for a class of graphs which strictly contains the claw-free graphs.

Weak Bipolarizable Graphs, Stephan Olariu

Computer Science Faculty Publications

We characterize a new class of perfectly orderable graphs and give a polynomial-time recognition algorithm, together with linear-time optimization algorithms for this class of graphs.

Symbolic Automation And Numerical Synthesis For Robot Kinematics, Jen Sriwattanathamma, Chung You Ho

Computer Science Technical Reports

This research analyzes three topics in robot arm kinematics. First, the direct kinematics which determines the Cartesian position and orientation of the end effector for the specified values of joint parameters is analyzed. Second, the differential motions concerning the differential relationships between the command variables in position and orientation of the end effector and the joint-controlled variables are studied. Finally, the inverse kinematics which determines the joint variables for a specified Cartesian position and orientation of the end effector is considered.

This dissertation presents a methodology for incorporating the artificial intelligence types of knowledge into automating solutions for the direct …

A Band And Bound Technique For Simple Random Algorithms, Vernon J. Rego

Department of Computer Science Technical Reports

No abstract provided.

Machine Knowledge Maniputation Issues In Parallel Compilers, Ko-Yang Wang, Dennis Gannon, Piyush Mehrotra

Department of Computer Science Technical Reports

No abstract provided.

On The Bottleneck And Capacity Assignment Problems, Wojciech Szpankowski

Department of Computer Science Technical Reports

No abstract provided.

Elliptic Expert: The Design Of An Expert System For Elliptic Partial Differential Equations, Wayne R. Dyksen, Carl R. Gritter

Department of Computer Science Technical Reports

No abstract provided.