Most measures of program complexity gauge either textual or
control flow attributes of a program. A recent addition to the field
of complexity measures, the knot metric, is a function of both these
attributes. A knot measurement reflects the degree of control-flow
tangle in a program's listing. This thesis discusses...
The general problem of classroom scheduling is well known to be NP-complete. A typical classroom scheduling problem is that of assigning students to a limited number of pieces of laboratory equipment. Frequently several identical pieces of equipment are available only at fixed hours and have limited access due to physical...
This paper demonstrates the effectiveness of a heuristic for
the Traveling Salesman Problem based purely on the efficient
storage of multiple partial sub-tours. The heuristic is among the
best available for the solution of large scale geometric Traveling
Salesman Problems. Additionally, a version of the heuristic can be
used to...
Quickersort, Straight Insertion Sort, Mehlhorn's AVL-tree Sorting Algorithm and Cook's new sorting algorithm are compared on nearly and nedium sorted lists. The ratio of the minimum number of list elements that must be removed so that the remaining portion of the list is in order to the size of the...
This research work investigates the use of production
systems as a model of parallel processing. The purpose of
the model is to provide a suitable medium within which parallel
processing systems can be systematically specified,
analyzed, and designed. Furthermore, the model provides a
suitable means for deriving implementations of synchronization...
An experiment was conducted at Oregon State University to evaluate the effectiveness of Computer Aided Instruction based lessons in a self study environment. The 47 student subjects were assigned to one of three groups: a CAI-EXP group which used a CAI lesson for teaching introductory FORTRAN formatted input and output;...
The methodology of structured programming has
enabled rapid progress in many areas of theoretical
computer science. Structured programs are generally
easier to debug, test, prove and analyse. The development
of these achievements into commercially viable applications
and products has been slower than expected.
The primary reason is that most of...
Production Systems are languages widely used for the implementation of Artificial Intelligence projects. They support programs in which the sequence of instructions is not fully determined at the beginning of their execution, as well as 'event driven' programs (i.e. the occurrence of a particular element in the data set determines...
System architectures for interconnecting large numbers of processors are being widely studied [AG82,TH75,TR82]. Of particular interest in such architectures is the exploitation of concurrency among processors. This concurrency can be parallelism, in which different parts of a single data case are processed at the same time, or pipelining, in which...
Program understanding is an integral part of the testing and maintenance phases of the software life cycle. There have been numerous investigations of the influence of various aspects of a program and the program- ming process on program comprehension. However, the many different measures of understanding used in these studies...
Cichelli has presented a simple method for constructing minimal perfect hash tables of identifiers for small static word sets. The hash function value for a word is computed as the sum of the length of the word and the values associated with the first and last letters of the word....
Historically, coding theory has dealt with binary
codes correcting symmetric errors, in which errors are
made in both 0 and 1 bits with equal likelihood.
Within the past ten years, some study has been made of
asymmetric codes, under the assumption that the only
errors which occur are errors in...
In process control systems where an entire process
is being controlled by a computer, the component tasks of
the system have to be monitored. An efficient message
oriented environment could be an important factor in the
optimization of such systems. In this paper we discuss
the design of a real...
A software system to study network algorithms was implemented on UNIX. Each part of a network algorithm is written as a single C program which becomes a virtual node in the network. During a simulation, all virtualized nodes run as separate processes on a single PDP 11/40. Inter-node communication is...
Why are the fast Fourier transform and the fast
Hadamard transform fast? A transform can be computed by
multiplying a matrix times a vector, which normally requires 0(n²) operations. The matrices corresponding to
these transforms can be rearranged to eliminate redundant
computations resulting in O(nlogn) operations.
We investigate algebraic reasons...
The system described is an interface between a student and a problem-solving production system that solves some class of problems. Its purpose is to help a student learn some part of the realm of problem solving. As a student attempts to solve a problem the system controls the firing of...
A process-resource graph is a directed graph with m
resource nodes and n process nodes. A request edge is
directed from a process to a resource. An assignment edge
is directed from a resource to a process. A cycle in the
process-resource graph is a necessary and sufficient condition for...
A new algorithm, the Horizontal and Vertical Algorithm, for
on-line detection of deadlocks in distributed computer systems, is
presented. Two protocols for implementing the algorithm are given.
The first protocol, the centralized protocol, is based on the
assumption that one site in the network acts as the controller for
global...
Cichelli gave a simple machine independent minimal perfect hashing function for small static sets. The hash function value for a word is computed as the sum of the length of the word and the values associated with the first and last letters of the word. Cichelli's algorithm (word-oriented) to find...
Very High Level Languages (VHLL) provide higher level abstractions and more powerful primitives than high level languages (HLL). A programmer uses these abstractions to solve a problem by specifying "what" is to be done rather than "how" it is to be done. This research work reports the design and development...
Topological Sorting is a standard computation performed on finite partial order relations, for which efficient algorithms are well known.
This work is a study of using a depth-first search of a directed graph to implement topological sorting algorithms. A new algorithm is presented, along with a discussion of how it...
A computer program complexity measure is a measure of how easy the program is to understand, test, modify, maintain, etc. Many of these measures are derived from the control or flow graph of the program. We describe these measures graph theoretically, indicate what aspect or aspects of the program they...
A software system to study network algorithms was implemented on UNIX. Each part of a network algorithm can be written as a single C program which becomes a virtual node in the network. During a simulation all virtualized nodes run as separate processes on a single PDP 11/44. Inter-node communication...
A concurrency and resiliency control scheme for a distributed database system with replicated data is discussed. The scheme, true-copy token scheme, uses true-copy tokens in order to designate the physical data copies (true copies) that can be identified with the current logical data that are globally unique, and then it...
A theory for resiliency control of distributed database systems is developed, and schemes that preserve the consistent global database state in the presence of site crashes and message link failures are discussed. The schemes can at least theoretically be paired with any concurrency control scheme that produces y-serializable executions. Further,...
An interactive computer graphics package was developed for the
purpose of solving certain geometric problems in the Euclidean plane.
The Geometric Graphics Package provides basic application-independent
functions for creating arbitrary views of two-dimensional objects and
for supporting interaction between the application program and its
user. The application program contains a...
The paper, "On the Duality of Operating System
Structures," by Lauer and Needham [21], claims that
operating systems can be modeled as procedure-oriented or
message-oriented, and that the two models are duals of each
other. Duality, in this case, means that the models are
logically and functionally equivalent, and have...
This grant supported acquisition of a minicomputer system for departmental research. The equipment selected is a DEC VAX-11/750 system, installed in remodeled space in the Computer Science (formerly Farm Crops) Building. Grant funds for equipment acquisition were supplemented by support from the Tektronix Foundation.
After completion of the physical facilities...
The minimal kernel for a network data base management
system is developed. It includes format specification for
the object schema and the data base file, and routines for
performing the basic network functions.
The object schema defines the relationship between the
schema, records, sets, and fields. It informs the system...
A typical database system maintains target data, which contain information useful for users, and access path data, which facilitate faster accesses to target data. Further, most large database systems support concurrent processing of multiple transactions. For a static database system model, where units of concurrency control are not dynamically created...
This paper presents a model for deterministic parsing which was designed to simplify the task or writing and understanding a deterministic grammar. While retaining structures and operations similar to those or Marcus's PARSIFAL parser [Marcus 80] the grammar language incorporates the following changes. (1) The use or productions operating in...
Caesar is an interactive graphic editor that is used to generate layouts for VLSI circuits . It runs on a VAX-11/780 under the UNIX operating system with Berkeley extensions. Caesar has a unique and simple user interface. Phled is an enhanced version of Caesar
that runs on a M68000-based engineering...
A denotational semantics is presented for a language that includes multiple-valued functions (essentially Lisp S-expressions), which map from ground values into the power domain of ground values. The domain equations are reflexive. and fixed points of all functions are defined. Thus, it is possible to specify an operating system as...
It is highly desirable for a distributed database system to achieve logically continuous operation even if some sites or message links fail. In this paper, we describe a scheme that can automatically reconfigure a fully-replicated distributed database system upon subsystem failures. The scheme can tolerate total failures of some sites....
Tbc expanding complexity of database application worlds, and the accelerating pace of change of these worlds mandate data models which support some of the tasks of data interpretation which formerly were borne by the applications programs. Chief among these are the support for virtual data, definition of transactions, and enforcement...
A database to be used by electrical circuit design, test, and repair expert systems must support both structural data and inferential data about the circuit. It is well known that engineering databases must support dynamic schema (re)definition of the structural data and entity-based access to it. We analyze this requirement...
The objective of this thesis is to develop a tool
which can be used to implement query processing algorithms
produced by a query optimizer. The tool should have the
following properties:
(1) it should support a description of the query solution in a dataflow-like language,
(2) it should support data...
The SEAS Directory and File Manager is a multiple window interactive tool to assist users in modifying and maintaining UNIX files and directories. This tool includes a show directory utility, a show file utility, a type file utility and provides access to the UNIX shell.
The purpose of this project is to design and implement an intermediate language interpreter for a very high level language called Bagit. The Bagit compiler produces Bcode, and this in turn is interpreted by the program described in this report.
A new class of information intensive applications is emerging [Fuch82;
Ohsu82] for which neither Artificial Intelligence (AI) nor Database technologies
alone are well suited. Database systems do not provide the general inferential
capabilities required for problem solving, while AI techniques have not been
adapted to handle massive amounts of structured...
Rapid Prototyping is a technique that has been created to alleviate some of the problems inherent in the traditional approach to software development. Various prototyping techniques currently employed are presented. The user interface aspect of system design is studied and where the benefit of prototyping user interfaces lies is shown....