Computer Sciences Commons^™

Industrial Simulation With Animation, Edward T. Hammerand, Chung You Ho

Computer Science Technical Reports

This thesis examines and evaluates the new simulation language PCModel. Prior to the arrival of PCModel, simulation via computer typically resulted in pages of statistics compiled over the duration of the simulation. PCModel's approach is to simulate the model on the display before the user in real time. Additionally, user interaction is supported to allow changes to be made throughout the simulation run.

The evaluation of PCModel is accomplished through inspection of a pair of examples already simulated in a conventional simulation language. The examples show the relative strong and weak points of the language, as well as demonstrating how …

A Monte Carlo Analysis Of The Mincycle Algorithm For Generating Minimal Perfect Hash Functions, Pao-Po Hou, Thomas J. Sager

Computer Science Technical Reports

In this paper, several minimal perfect hashing function generating methods are examined. One of them, the mincycle method by Sager is evaluated by the Monte Carlo method. The results are represented in graphs and tables.

A Parallel Branch And Bound Algorithm For Integer Linear Programming Models, Rochelle L. Boehning, Billy E. Gillett

Computer Science Technical Reports

A parallel branch and bound algorithm is developed for use with MIMD computers to study the efficiency of parallel processors on general integer linear programming problems. The Haldi and IBM test problems and a System Design model are used in the implementation of the algorithm. Initially the algorithm solves the Haldi and IBM test problems on a single processor computer which simulates a multiple processor computer. The algorithm is then implemented on the Denelcor HEP multiprocessor using two of the IBM problems to compare the results of the simulation to the results using an MIMD computer. Finally the algorithm is …

Bruce: A Graphics System With Hidden Line And Hidden Surface Algorithms, Keith Vetter, Christopher Roche

Computer Science Technical Reports

Accurately representing the physical world by computer is a topic which has direct benefits to fields like chemistry and architecture, and is a source of much research in computer science. This paper examines the steps necessary to develop and implement a graphical system that will allow for the modeling of physical world objects. In particular, this is a description of BRUCE: a graphical system that will describe a world of three dimensional polyhedra, implementing algorithms for hidden line and hidden surface removal. This paper also deals with the problems incurred along the way and suggestions for further improvement of BRUCE.

An Algorithm For Parallel Subsumption, Ralph M. Butler, Arlan R. Dekock

Computer Science Technical Reports

Many current automated theorem provers use a refutation procedure based on some version of the principle of resolution. These methods normally lead to the generation of large numbers of new clauses. Subsumption is a process that eliminates the superfluous clauses from the clause space, thus speeding up the proof. The research presented in this thesis is concerned with the design and implementation of a subsumption algorithm which exploits the parallelism provided by a multiprocessor. For portability, all coding is done in the programming language C. Monitors are used as the synchronization mechanism. Correct performance in both a multiprocessor and uniprocessor …

A Parallel Array Scanning Algorithm, Ralph M. Butler, Ralph W. Wilkerson

Computer Science Technical Reports

Suppose we are given a vector X of n real numbers and we want to find the maximum sum found in any contiguous subvector of X. In Jon Bentley's article [l] on algorithm design and technique, a simple vector scanning problem and a series of progressively more efficient algorithms to solve this problem were discussed in some detail. Clearly, any algorithm must visit each location of X at least once and consequently a lower bound on the running time for problem is 0(n), which is in fact attainable as Bentley’s paper illustrates. However, the original motivation for this problem was …

Survey Of Routing Algorithms For Computer Networks, Lu Yu, Thomas J. Sager

Computer Science Technical Reports

This thesis gives a general discussion of routing for computer networks, followed by an overview of a number of typical routing algorithms used or reported in the past few years. Attention is mainly focused on distributed adaptive routing algorithms for packet switching (or message switching) networks. Algorithms for major commercial networks (or network architectures) are reviewed as well, for the convenience of comparison.

A Simple Method For Organizing Nearly Optimal Binary Search Trees, Joy L. Henderson, John R. Metzner

Computer Science Technical Reports

Improving the efficiency of retrieving information concerns users of computer systems involved in many applications- One way of addressing this concern is to organize a sorted sequence into a binary search tree. Knuth's Algorithm K is a bottom-up organization algorithm that always constructs a binary tree which minimizes average search time. However, the cost of executing Algorithm K is prohibitive for a large tree. The aim of this work is to find a less costly method of organizing sorted sequences into nearly-optimal binary search trees.

We present a top-down organization method which yields better average search times than top-down methods …

The Design And Implementation Of The Programming Language Natural, Alan L. Sparks, Thomas J. Sager, Arlan R. Dekock

Computer Science Technical Reports

This paper reports progress on the development of the programming language Natural, currently under design by Dr. Thomas J. Sager at the University of Missouri--Rolla. Natural is a very high-level language with a mathematical flavor, and includes several concepts relatively uncommon in programming language design.

The text also discusses an implementation on the IBM Personal Computer of Mini-Natural, a subset of Natural, and presents examples of programs written in Mini-Natural.

Color Computer Graphics As Applied To Introductory Calculus Instruction, Kathy B. Windhorst, Ralph E. Lee

Computer Science Technical Reports

The use of computer graphics to support and enhance the presentation of introductory calculus concepts is described.

Computer graphics provides more accurate graph sketching, consistent presentations and the ability to develop mathematical models incrementally. The addition of extensive use of color aids even more, adding contrast, color keying, dimensionality, and interest to an illustration.

Ten lessons have been designed, developed, and evaluated. They employ a set of subroutines which interface to the NBC APC microcomputer graphics software. These lessons as developed and evaluated may be used interactively in the classroom or by individuals, or noninteractively in the classroom by the …

A Focus Of Attention Algorithm For Expert Systems, Kevin W. Whiting, Arlan R. Dekock, John Bruce Prater

Computer Science Technical Reports

This research is primarily concerned with increasing the performance of expert systems. A refined focus of attention strategy and its affect on performance are discussed. Early expert systems used a brute force approach to process the knowledge base. Each production rule in the knowledge base was evaluated each cycle. More recently, processing efficiency has been increased by focusing the attention of the inference engine on a subset of the rules by "filtering" for further testing, only rules that could possibly fire given the current content of the context base. Focus of attention as developed in this research increases performance over …

Ciegen: A System For Testing Knowledge Base Compilation Heuristics On A Microcomputer, Jayne D. Ward, Billy E. Gillett, Arlan R. Dekock

Computer Science Technical Reports

The expert system has proven itself to be a valuable aid in diagnosing and treating problems in domains requiring expertise. The commercial world has been alerted to this fact and the thrust is to make the expert system portable and available on small computers.

The goal of this research has been to lay the groundwork for a domain independent expert system builder on a microcomputer. The result of this effort was CIEGEN, a system consisting of a rule compiler, inference engine, and rule generator developed on the IBM PC. It is domain independent, responsible for transforming a knowledge base of …

Dartmouth-Smalltalk: An Exercise In Implementation, Joon Sup Lee

Computer Science Technical Reports

This report discusses a preliminary implementation of the Smalltalk-80 virtual machine for Vax/Unix.

An Image Processing Software Package For The Laser Scanning Phase Modulation Microscope, William J. Murray

Computer Science Technical Reports

This thesis documents the most recent effort to develop a user-friendly image processing software package for the Laser Scanning Phase Modulation Microscope (LSPMM). The LSPMM is composed of three integrated subsystems, the Laser Scanning (LS) system, the Phase Modulation (PM) system, and Digital Image Acquisition (DIA) system. Under the control of the image processing software, the DIA system can receive and store the digital image data, display the image on a monochrome monitor, and process the image to provide the microscopist with quantitative information regarding the image. The implementation of this image processing software package required the specification of a …

A Graphical Representation Of An Executing Program, Sherry A. Lile, Arlan R. Dekock, John Bruce Prater, Darrow Finch Dawson

Computer Science Technical Reports

This thesis describes the rationale for a computer program used as a teaching aid, as well as, the design, development, and implementation of that computer program. The program is a prototype that displays, line by line, a graphical depiction of a BASIC program being executed. Icons are used to represent FOR-NEXT loops, the contents of variables, I/O, and other programming elements. The internal logic associated with the Arithmetic-Logic Unit is also represented. The purpose is to produce an environment where the student may visualize the processes occurring in memory by viewing a symbolic portrayal of an executing program. The example …

The Optimal Trajectory Modelling Of Robot Manipulators, Mary Claire Miller, Chung You Ho, Arlan R. Dekock

Computer Science Technical Reports

Greater robot capability can be achieved through the use of robot manipulator control systems. Crucial to the success of these control systems is the optimal trajectory modelling of the path traced by the end- effector. To create this optimal path the utilization of B-Spline curve functions will be investigated, and compared to Cubic Spline curve functions.

An Experimental Study Of The Effects Of Modularity On Resource Consumption In Software Development, Alan D. Christiansen, Arlan R. Dekock, John Bruce Prater

Computer Science Technical Reports

Many authors have encouraged the use of modular programming techniques in software development. In fact, there is almost total agreement within industrial and academic circles that modularity is a desirable feature of any software package. Unfortunately, the desirability of modular design is almost always voiced without support from experimental evidence.

This paper consists of an experiment comparing the resource consumption of programmers based on the modularity practices employed during the design and programming phases of software development. The experiment tests the effectiveness of modularity in reducing psychological complexity of software.

The results of the research show that in some cases …

An Improved Algorithm For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A minimal perfect hash function (MPHF) is a function from a set of M objects to the first M non-negative integers. MPHF's are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language. In this paper we improve on an earlier result and present an algorithm for generating MPHF's with an expected time complexity proportional to M⁴. We also give a MPHF for the 256 most frequently used words in the English language.

Parallelism In The Language, Natural, Thomas J. Sager

Computer Science Technical Reports

Natural is a language designed to provide a vehicle for the expression of abstract programming concepts clearly and precisely in a natural and mathematical form. The concept of parallelism can be expressed both explicitly and implicitly in the language, Natural. Due to relative freedom from side-effects and the use of a special value, undef, subexpressions can often be evaluated in parallel. The for and do statements both allow for a parallel mode of execution. A builtin functional, prlleval, creates functions which can evaluate their arguements in a parallel mode. In addition, the concept of module allows for the definition of …

A New Method For Generating Minimal Perfect Hash Functions, Thomas J. Sager

Computer Science Technical Reports

A perfect hash function, PHF, is an injection, F, from a set, W, of M objects into the set consisting of the first N non-negative integers where N>=M. If N=M then F is a minimal perfect hash function, MPHF. PHFs are useful for the compact storage and fast retrieval of frequently used objects such as reserved words in a programming language or commonly employed words in a natural language.

The mincycle algorithm for finding PHFs executes with an expected time complexity proportional to M⁴ and has been used successfully on sets of cardinality up to 256. The mincycle …

Stochastic Modeling Of Individual Resource Consumption During The Programming Phase Of Software Development, Daniel G. Mcnicholl, Kenneth Magel

Computer Science Technical Reports

In the past several years there has been a considerable amount of research effort devoted to developing models of individual resource consumption during the software development process. Since many conditions affect individual resource consumption during the software development process, including several which are difficult if not impossible to quantify, it is our contention that a stochastic model is more appropriate than a deterministic model.

In order to test our hypothesis we conducted an experiment based upon several student programming assignments. Data from this experiment is used to demonstrate that the two parameter Log-Normal distribution is appropriate for describing the probabilistic …

A Hybrid Metric To Measure Software Complexity, Warren Harrison, Kenneth I. Magel

Computer Science Technical Reports

Software complexity is an important facet of the software development process, especially in regard to maintenance. A number of complexity metrics have been developed to measure the complexity contributed by: program size, flow of control, data structures, or a combination of two or more of these. Several representative measures from each of these groups are described.

A new hybrid complexity metric, the Extended Scope Metric, is presented and compared with other popular complexity metrics. While the new metric appears to be an improvement over existing metrics due to its enhanced context sensitivity and comprehensiveness, conclusive results cannot be determined until …