Physical Sciences and Mathematics Commons^™

The Problem Of Mutual Exclusion: A New Distributed Solution, Rajeev Chawla

Theses and Dissertations

In both centralized and distributed systems, processes cooperate and compete with each other to access the system resources. Some of these resources must be used exclusively. It is then required that only one process access the shared resource at a given time. This is referred to as the problem of mutual exclusion. Several synchronization mechanisms have been proposed to solve this problem. In this thesis, an effort has been made to compile most of the existing mutual exclusion solutions for both shared memory and message-passing based systems. A new distributed algorithm, which uses a dynamic information structure, is presented to …

Implementing A Neural Network In The Smalltalk Graphical Environment, John M. Damgaard

Presidential Scholars Theses (1990 – 2006)

Interest in artificial neural networks has grown rapidly over the past few years. The technology is intriguing and the potential applications of the technology are exciting and diverse. Another area of growing interest in the computer science field is that of object-oriented programming. The object-oriented paradigm is a very powerful tool which can improve software quality and streamline the development process. The most common object-oriented language is Smalltalk. I feel that Smalltalk is an excellent platform on which to implement artificial neural networks.

Pattern Recognition For Nondestructive Evaluation, S. Morris, P. O'Rorke, William E. Bond, M. M. Amirfathi, Daniel C. St. Clair

Computer Science Faculty Research & Creative Works

The issues involved in automating nondestructive evaluation (NDE) techniques are outlined. Attention is given to research focused on the application of machine learning techniques to the construction and maintenance of knowledge-based systems which are capable of evaluating the readings from nondestructive tests that have been performed on aircraft components. Preliminary results obtained from this research are described. In particular, the authors discuss the application of a symbolic machine learning algorithm, ID3, to the NDE problem. ID3 has been used by Douglas Aircraft to classify defects in sets of standard NDE reference blocks. Based on the preliminary results, a need for …

A Visualization Model For Massively Parallel Algorithms, Rashi Khanna, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

A visualization model has been developed to analyze the performance of a massively parallel algorithm. Most visualization tools that have been developed so far for performance analysis are based generally on individual processor information and communication patterns. These tools, however, are inadequate for massively parallel computations. It is difficult to comprehend the visual information for many processors. The model, SMILI (Scientific visualization in Multicomputing for Interpretation of Large amounts of Information), addresses this problem by using abstract representations to attain a composite picture which gives better insight to the behavior of the algorithm. Chernoff s Faces have been selected to …

An Expert Inference Engine For Generation Of Nursing Diagnoses, Tom Edgar

UNF Graduate Theses and Dissertations

Expert computer systems for use in the nursing profession are emerging as a potentially viable alternative to manual procedures. As nursing science continues to develop, the intellectual requirements of assessment and diagnosis are demanding that the professional nurse draw on an ever increasing bank of knowledge to interact effectively with clients. An expert system appears a promising tool to assist the nurse in storing and accessing some of the knowledge necessary to perform the assessment and diagnostic functions.

Problems and opportunities In applying artificial intelligence techniques to nursing science are documented and the current state of expert systems for nursing …

Causal Reasoning About Distributed Programs, William Samuel Lloyd

Dissertations, Theses, and Masters Projects

We present an integrated approach to the specification, verification and testing of distributed programs. We show how "global" properties defined by transition axiom specifications can be interpreted as definitions of causal relationships between process states. We explain why reasoning about causal rather than global relationships yields a clearer picture of distributed processing.;We present a proof system for showing the partial correctness of CSP programs that places strict restrictions on assertions. It admits no global assertions. A process annotation may reference only local state. Glue predicates relate pairs of process states at points of interprocess communication. No assertion references auxiliary variables; …

On A Unique Tree Representation For P4-Extendible Graphs, B. Jamison, S. Olariu

Computer Science Faculty Publications

Several practical applications in computer science and computational linguistics suggest the study of graphs that are unlikely to have more than a few induced paths of length three. These applications have motivated the notion of a cograph, defined by the very strong restriction that no vertex may belong to an induced path of length three. The class of P₄-extendible graphs that we introduce in this paper relaxes this restriction, and in fact properly contains the class of cographs, while still featuring the remarkable property of admitting a unique tree representation. Just as in the case of cographs, the …

Integration Of Abductive And Deductive Inference Diagnosis Model And Its Application In Intelligent Tutoring System, Jingying Zhang

Computer Science Theses & Dissertations

This dissertation presents a diagnosis model, Integration of Abductive and Deductive Inference diagnosis model (IADI), in the light of the cognitive processes of human diagnosticians. In contrast with other diagnosis models, that are based on enumerating, tracking and classifying approaches, the IADI diagnosis model relies on different inferences to solve the diagnosis problems. Studies on a human diagnosticians' process show that a diagnosis process actually is a hypothesizing process followed by a verification process. The IADI diagnosis model integrates abduction and deduction to simulate these processes. The abductive inference captures the plausible features of this hypothesizing process while the deductive …

Estimation In A Marked Poisson Error Recapture Model Of Software Reliability, Rajan Gupta

Mathematics & Statistics Theses & Dissertations

Nayak's (1988) model for the detection, removal, and recapture of the errors in a computer program is extended to a larger family of models in which the probabilities that the successive programs produce errors are described by the tail probabilities of discrete distribution on the positive integers. Confidence limits are derived for the probability that the final program produces errors. A comparison of the asymptotic variances of parameter estimates given by the error recapture and by the repetitive-run procedure of Nagel, Scholz, and Skrivan (1982) is made to determine which of these procedures efficiently uses the test time.

A Meta-Analysis Of Learner Control In Computer-Based Learning Environments, June A. Parsons

CCE Theses and Dissertations

The objective of this meta-analysis was to integrate the results of a collection of primary research studies on learner control of computer-based environments. The scope for the meta-analysis was limited to inquiry on different learner-control models and their effect on student achievement as represented by posttest scores. Three specific research questions were defined:

1. What are the characteristics of the body of learner-control research which has examined the effect on achievement of learner control?
2. Is there a difference in the achievement of students who are provided with learner control and students who are provided with other control models?
3. Do specific moderator …

Shadow Casting Phenomena At Newgrange, Frank Prendergast

Articles

A digital model of the Newgrange passage tomb and surrounding ring of monoliths known as the Great Circle is used to investigate sunrise shadow casting phenomena at the monument. Diurnal variation in shadow directions and lengths are analysed for their potential use in the Bronze Age to indicate the passage of seasonal time. Computer-aided simulations are developed from a photogrammetric survey to accurately show how three of the largest monoliths, located closest to the tomb entrance and archaeologically coded GC1, GC-1 and GC-2, cast their shadows onto the vertical face of the entrance kerbstone, coded K1. The phenomena occur at …

Exclusive And Inclusive Semileptonic Decays Of B Mesons To D Mesons, R. Fulton, M. Thulasidas

Research Collection School Of Computing and Information Systems

We report new measurements of the branching fractions B ( B − → D 0 l − ¯ ν ) , B ( ¯ B 0 → D + l − ¯ ν ) , and B ( B − → D * 0 l − ¯ ν ) . Combining these results with our previous measurement of B ( ¯ B 0 → D * + l − ¯ ν ) , we find that the ratio of semileptonic widths for final states with a vector meson and pseudoscalar meson is ( 2.6 + 1.1 + 1.0 − 0.6 …

Dissertation Report Is 8995 Using Dialog Cip At Winona State University To Educate End-Users, Kathryn Sullivan

CCE Theses and Dissertations

Graduate students need to know the resources of their university library in order to do research and cannot be expected to remember any library training they may have received as undergraduates. A class offered by the library on how to search databases available through DIALOG's Classroom Instruction Program (CIP) was proposed, in cooperation with existing research classes in the student's field. A study was conducted at Winona State University. Winona, MN, with research classes offered by two professors in the field of special education. The study was to determine whether the information presented in an instruction session based on six …

Curriculum-Oriented Cai Based On Instructional Technology To Be Used For Teaching Secondary School Students Introductory Library Skills, Theresa K. Toohil

CCE Theses and Dissertations

In 1990, the New York State Education Department presented a syllabus that required the teaching of curriculum-oriented library skills and suggested the use of computers to be integrated with the teaching of these skills whenever possible. Schools in New York State are now trying to implement the suggestions in the syllabus. Many authors of educational articles have written at length concerning the incorporation of computer-assisted instruction (CAl) into the classroom, but clear directions have not been provided in the literature for the design or implementation of the necessary software.

The purpose of this study was to design a program based …

Fault-Tolerant Parallel Matrix Multiplication With One Iteration Fault Detection Latency, Chul Eui Hong, Bruce M. Mcmillin

Computer Science Faculty Research & Creative Works

The checksum technique is a low-cost method to detect errors in matrix operations performed by processor arrays. The fault detection of this method is done only at problem termination, so this method is not an effective fault tolerance technique for large scale matrix multiplication. This paper presents a new algorithm, the ID algorithm, which minimizes the fault-detection latency, In the ID algorithm, a fault is detected as soon as the fault occurs instead of at problem termination. For n2 processors, the fault-latency time of the ID algorithm is l/n of that of checksum algorithm with a run-time penalty of O(nlog2n) …

A Model-Based Approach For Organizing Quantitative Computations, J. Sticklen, A. Kamel, William E. Bond

Computer Science Faculty Research & Creative Works

Model based reasoning (MBR) is currently receiving wide spread attention because it offers a way to circumvent the brittleness of reasoning systems built solely on associational knowledge. To date, most MBR approaches have focused on the use and manipulation of qualitative models. The authors report their experience in applying techniques of functional reasoning to the general problem of organizing quantitative calculations. As a testbed, they have solved a problem initially posed at the Model-Based Diagnosis workshop (Paris, July, 1989): representing an automotive cruise control system. The results show that the principles of the functional reasoning approach can provide leverage in …

Inclusive Production Of The Charmed Baryon C+ From E+E- Annihilations At S=10.55 Gev, P. Avery, Manoj Thulasidas

Research Collection School Of Computing and Information Systems

We report results on inclusive production of the charmed baryon Λc+ from e+e− annihilations at √s=10.5 GeV. Measurements are presented of the inclusive cross section times branching fraction for the continuum production of Λc+ as observed in six different decay modes, and of a new, improved value of the Λc+ mass. The inclusive cross section times the branching fraction into pK−π+ is measured to be 10.0±1.5±1.5 pb summed over all xp. The branching fractions of Λc+ into p¯K0, p¯K0π+π−, Λπ+, Λπ+π−π+, and Ξ−K+π+ relative to that into pK−π+ are measured to be 0.44±0.07±0.05, 0.43±0.12±0.04, 0.18±0.03±0.03, 0.65±0.11±0.12, and 0.15±0.04±0.03, respectively. The …

A Mergeable Double-Ended Priority Queue, S. Olariu, Z. Wen

Computer Science Faculty Publications

An implementation of a double-ended priority queue is discussed. This data structure referred to as min–max–pair heap can be built in linear time; the operations Delete-min, Delete-max and Insert take O(log n) time, while Find-min and Find-max run in O(1) time. In contrast to the min-max heaps, it is shown that two min–max–pair heaps can be merged in sublinear time. More precisely, two min–max–pair heaps of sizes n and k can be merged in time O(log (n/k) * log k).

Some Aspects Of The Semi-Perfect Elimination, Stephan Olariu

Computer Science Faculty Publications

Several efficient algorithms have been proposed to construct a perfect elimination ordering of the vertices of a chordal graph. We study the behaviour of two of these algorithms in relation to a new concept, namely the semi-perfect elimination ordering, which provides a natural generalization of chordal graphs.

Error Flow In Computer Programs, Branson Wayne Murrill

Dissertations, Theses, and Masters Projects

White box program analysis has been applied to program testing for some time, but this analysis is primarily grounded in program syntax, while errors arise from incorrect program semantics. We introduce a semantically-based technique called error flow analysis, which is used to investigate the behavior of a program at the level of data state transitions. Error flow analysis is based on a model of program execution as a composition of functions that each map a prior data state into a subsequent data state. According to the fault/failure model, failure occurs when a fault causes an infection in the data state …

An Examination And Analysis Of The Boltzmann Machine, Its Mean Field Theory Approximation, And Learning Algorithm, Vincent Clive Phillips

Theses : Honours

It is currently believed that artificial neural network models may form the basis for inte1ligent computational devices. The Boltzmann Machine belongs to the class of recursive artificial neural networks and uses a supervised learning algorithm to learn the mapping between input vectors and desired outputs. This study examines the parameters that influence the performance of the Boltzmann Machine learning algorithm. Improving the performance of the algorithm through the use of a naïve mean field theory approximation is also examined. The study was initiated to examine the hypothesis that the Boltzmann Machine learning algorithm, when used with the mean field approximation, …

An Object-Oriented Learning/Design Support Environment, Fillia Makedon, Julie C. Jumes, Jill P. David

Computer Science Technical Reports

We present an object-oriented experimental learning and design support environment, call AVT, for an Algorithm Visualization Tool, implemented in Digitalk's Smalltalk/V1 on a Macintosh II2, AVT provides a domain- independent visualization tool, an exploratory learning environment, and an experimental heuristic design environment. Algorithm visualization is the exploration of ways to visualize intuitively the computational behavior of an algorithm using multiple views, some of which are visual in the graphical sense [2,4]. AVT employs other views (combining text and graphics) to explain the problem, the strategy, the heuristics, and the reasoning process behind the solutions. User interaction in AVT includes not …

A Security Analysis Of Version 2 Of The Network Time Protocol Ntp: A Report To The Privacy And Security Research Group, Matt Bishop

Computer Science Technical Reports

The Network Time Protocol is being used throughout the Internet to provide an accurate time service. This paper examines the security requirements of such a service, analyzes version 2 of the NTP protocol to determine how well it meets these requirements, and suggests improvements where appropriate.

Connected Components In O(Lg3/2|V|) Parallel Time For The Crew Pram, Donald B. Johnson, Panagiotis Metaxas

Computer Science Technical Reports

Computing the connected components of an undirected graph G = (V,E) on |V| = n vertices and |E| = m edges is a fundamental computational problem. The best known parallel algorithm for the CREW PRAM model runs on O(lg2n) time using n2/lg2n processors [CLC82,HCS79]. For the CRCW PRAM model in which concurrent writing is permitted, the best known algorithm runs in O(lg n) time using almost (n+m)/lg n processors [SV82,CV86,AS87]. Unfortunately, simulating this algorithm on the weaker CREW model increases its running time to O(lg2n) [CDR86, KR90,Vis83]. We present here an efficient and simple algorithm that runs in O(lg 3/2n) …

Multipacket Routing On Rings, Fillia Makedon, Adonios Simvonis

Computer Science Technical Reports

We study multipacket routing problems. We divide the multipacket routing problem into two classes, namely, distance limited and bisection limited routing problems. Then, we concentrate on rings of processors. Having a full understanding of the multipacket routing problem on rings is essential before trying to attack the problem for the more general case of r-dimensional meshes and tori. We prove a new lower bound of 2n/3 routing steps for the case of distance limited routing problems. We also give an algorithm that tightens this lower bound. For bisection limited problems, we present an algorithm that completes the routing in near …

Apt Compiler Toolkit User Manual, George K. Thiruvathukal, Ufuk Verun

Computer Science: Faculty Publications and Other Works

The Apt Compiler Toolkit was designed to address the need for structured, efficient, portable, and capable tools to prototype language translators and compilers. In the current release of the toolkit tools are available for the generation of scanners, parsers, and data structures. A robust library of functions is supplied with the toolkit which includes support for the scanner, the parser, abstract data types (which are commonly used in language translators/compilers), and string functions.

An Analysis And Implementation Of Linear Derivation Strategies, Winston M. Tabada

Theses: Doctorates and Masters

This study examines the efficacy of six linear derivation strategies: (i) s-linear resolution, (ii) the ME procedure; (iii) t-linear resolution, (iv) SL -resolution, (v) the GC procedure, and (vi) SLM. The analysis is focused on the different restrictions and operations employed in each derivation strategy. The selection function, restrictive ancestor resolution, compulsory ancestor resolution on literals having atoms which are or become identical, compulsory merging operations, reuse of truncated literals, spreading of FALSE literals, no-tautologies resection, no two non-B-literals having identical atoms restriction, and the use of semantic information to trim irrelevant derivations from the search tree are the major …

A Simulation Of Demand-Driven Dataflow: Translation From Lucid Into Mdc Language, George K. Thiruvathukal, Thomas W. Christopher

Computer Science: Faculty Publications and Other Works

Message Driven Computation (MDC) is a model of computation with which they have been experimenting at the Illinois Institute of Technology. The authors aim to prove the viability of MDC in practice for the expression of parallel algorithms and the implementation of functional and dataflow programming languages. In the paper they discuss their implementation of the Lucid programming language in MDC. The discussion presents a subset of Lucid which illustrates the principles of Lucid, Message Driven Computing, and the translation into and the interpretation of dataflow graphs.

Solving Ill-Posed Problems With Artificial Neural Networks, Arun D. Kulkarni

Arun Kulkarni

Implementation Of Object Oriented University Database Using Vodak/Vml-0 Prototype, Abhay V. Bhave

Theses

In recent years object - oriented programming has gained a tremendous popularity in the design and implementation of emerging data - intensive application systems. Object oriented knowledge based approaches have proved to be very powerful vehicle when developing, integrating complex systems.

Using a University database demonstrated here is an object oriented model. This model uses VODAK/VML-0 prototype which was developed by GMD - IPSI, Darmstadt FRG. The Conceptual Schema of this database was done using The Dual Model, but as the current VODAK/VML version does not support dual model, the schema was modified before use. There are 167 classes defined …