The communication complexity of fundamental problems in distributed computing on an asynchronous ring are examined from both the algorithmic and lower bound perspective. A detailed study is made of the effect on complexity of a number of assumptions about the algorithms. Randomization is shown to influence both the computability and complexity of several problems. Communication complexity is also shown to exhibit varying degrees of sensitivity to additional parameters including admissibility of error, kind of error, knowledge of ring size, termination requirements, and the existence of identifiers. A unified collection of formal models of distributed computation on asynchronous rings is developed which captures the essential characteristics of a spectrum of distributed algorithms those that are error free (deterministic, Las Vegas, and nondeterministic), and those that err with small probability (Monte Carlo and nondeterministic/probabilistic). The nondeterministic and nondeterministic/probabilistic models are introduced as natural generalizations of the Las Vegas and Monte Carlo models respectively, and prove useful in deriving lower bounds. The unification helps to clarify the essential differences between the progressively more general notions of a distributed algorithm. In addition, the models reveal the sensitivity of various problems to the parameters listed above. Complexity bounds derived using these models typically vary depending on the type of algorithm being investigated. The lower bounds are complemented by algorithms with matching complexity while frequently the lower bounds hold on even more powerful models than those required by the algorithms. Among the algorithms and lower bounds presented are two specific results which stand out because of their relative significance. 1. If g is any nonconstant cyclic function of n variables, then any nondeterministic algorithm for computing g on an anonymous ring of size n has complexity [Formula Omitted] bits of communication; and, there is a is nonconstant cyclic boolean function [Formula Omitted], such that [Formula Omitted] can be computed by a Las Vegas algorithm in [Formula Omitted] expected bits of communication on a ring of size n. 2. The expected complexity of computing AND (and a number of other natural functions) on a ring of fixed size n in the Monte Carlo model is [Formula Omitted] messages and bits where [Formula Omitted] is the allowable probability of error. / Science, Faculty of / Computer Science, Department of / Graduate

One of the important tasks during software testing is the generation of test cases. Various approaches have been proposed to automate this task. The approaches available, however, often have problems limiting their use. A problem of dynamic test case generation approaches, for instance, is that a large number of iterations can be necessary to obtain test cases. This article proposes a novel algorithm for path-oriented test case generation based on binary search and describes a possible implementation.

No description available.

No description available.

No description available.

No description available.

Typescript (photocopy). / Digitized by Kansas Correctional Industries

This research explores the concepts of defensive programming as currently defined in the literature. Then these concepts are extended and more explicitly defined. The relationship between defensive programming, as presented in this research, and current programming practices is discussed and several benefits are observed. Defensive programming appears to benefit the entire software life cycle. Four identifiable phases of the software development process are defined, and the relationship between these four phases and defensive programming is shown. In this research, defensive programming is defined as writing programs in such a way that during execution the program itself produces communication allowing the programmer and the user to observe its dynamic states accurately and critically. To accomplish this end, the use of defensive programming snap shots is presented as a software development tool.

The problem of this study concerns the performance of students in computer programming following exposure to a computer-aided instruction (CAI) drill in sequencing and practice exercises. The purpose of this study was to determine whether or not student success rates improve in computer programming after completing CAI sequencing drills and practice exercises.

Typescript (photocopy). / Digitized by Kansas Correctional Industries