Digital Commons Network^™

Optimal Parallel And Sequential Algorithms For The Vertex Updating Problem Of A Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas

Computer Science Technical Reports

We present a set of rules that can be used to give optimal solutions to the vertex updating problem for a minimum spanning tree: Update a given MST when a new vertex z is introducted, along with weighted edges that connect z with the vertices of the graph. These rules lead to simple parallel algorithms that run in O(lg n) parallel time using n/lg n EREW PRAMs. They can also be used to derive simple linear-time sequential algorithms for the same problem. Furthermore, we show how our solution can be used to solve the multiple vertex updating problem.

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 …

A Parallel Algorithm For The Minimum Spanning Tree, Donald B. Johnson, Panagiotis Metaxas

Computer Science Technical Reports

No abstract provided.

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.

An Overview Of Computer Viruses In A Research Environment, Matt Bishop

Computer Science Technical Reports

The threat of attack by computer viruses is in reality a very small part of a much more general threat, specifically attacks aimed at subverting computer security. This paper examines computer viruses as malicious logic in a research and development environment, relates them to various models of security and integrity, and examines current research techniques aimed at controlling the threats viruses in particular, and malicious logic in gerneral, pose to computer systems. Finally, a brief examination of the vulnerabilities of research and development systems that malicious logic and computer viruses may exploit is undertaken.

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 …

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

CCAC 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 …

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

CCAC 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 …

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

CCAC 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 …

Transforming A Rule-Based Program, Rose F. Gamble

All Computer Science and Engineering Research

Conflict resolution is a form of global control used in production systems to achieve an efficient sequential execution of a rule-based program. This type of control is not used to parallel production system models [6,13]. Instead, only those programs that make no assumptions regarding conflict resolution are executed in parallel. Therefore, the initial sequential rule-based programs are either executed in parallel without their conflict resolution strategy, which normally results in incorrect behavior, or the programs are transformed in an ad hoc manner to execute on an particular parallel production system model. As a result, these programs do not exhibit the …

Intelligent Structural Operators For The K-Way Graph Partitioning Problem, Gregor Von Laszewski

Northeast Parallel Architecture Center

A parallel genetic algorithm for the graph partitioning problem is presented, which combines general heuristic algorithms with techniques that are described in evolution theory. In the parallel genetic algorithm the selection of a mate is restricted to a local neighborhood. In addition, the parallel genetic algorithm executes an adaptation step after an individual is generated, with the genetic operators crossover and mutation. During the adaptation step the solution is improved by a common algorithm. Another selection step decides if the adapted descendant should replace the parent individual. Instead of using a uniform crossover operator a more intelligent crossover operator, which …

Graduate Bulletin, 1991-1993, Moorhead State University

Graduate Bulletins (Catalogs)

No abstract provided.

Actuarial Computation Of Multiemployer Pension Plan Withdrawal Liability, Kelly A. Renze

Presidential Scholars Theses (1990 – 2006)

This project helps to demonstrate how pension actuaries must keep a constant eye on new laws. The pension industry is constantly bombarded with new laws which force them to alter policies and procedures. Because of the huge number of laws, it is difficult for all employees to fully understand every law. During my stay at the Principal, I discovered that many passages are interpreted differently by different people. I also uncovered some details through my research that other employees were not aware of.

Because of this complexity, it is often necessary to assign to one person, such as myself, the …

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 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, …

Optimal Processor Assignment For Pipeline Computations, David Nicol, Rahul Simha, Alok N. Choudhury, Bhagirath Narahari

Electrical Engineering and Computer Science - All Scholarship

The availability of large-scale multitasked parallel architectures introduces the following processor assignment problem for pipelined computations. Given a set of tasks and their precedence constraints, along with their experimentally determined individual response times for different processor sizes, find an assignment of processors to tasks. Two objectives interest us: minimal response given a throughput requirement, and maximal throughput given a response time requirement. These assignment problems differ considerably from the classical mapping problem in which several tasks share a processor; instead, we assume that a large number of processors are to be assigned to a relatively small number of tasks. In …

Three Denerations Of Dbms, Maria Skiba

Theses : Honours

This paper describes the evolution of data base technology from early computing to the sophisticated systems of today. It presents an overview of the most popular data base management systems architectures such as hierarchical, network, relational and object-oriented. The last section of this paper presents a view of the factors that will influence the future of data base technology.

Parallel Test Pattern Generation Using Boolean Satisfiability, V. Sivaramakrishnan, Sharad C. Seth, Prathima Agrawal

School of Computing: Conference and Workshop Papers

Recently, Larrabee proposed a sequential test generation algorithm for combinational circuits based on boolean satisfiability and presented results on benchmark circuits in support of the viability of this approach. Parallel implementations of test generation algorithms are attractive in view of the known difficulty (NP-completeness) of the problem. In this paper we suggest parallel versions of Larrabee’s algorithm, suitable for implementation on shared-memory and message-passing multicomputers.

Design For Testability And Test Generation With Two Clocks, Vishwani D. Agrawal, Sharad C. Seth, Jitender S. Deogun

School of Computing: Conference and Workshop Papers

We propose a novel design for testability method that enhances the controllability of storage elements by use of additional clock lines Our scheme is applicable to synchronous circuits but is otherwise transparent to the designer. The associated area and speed penalties are minimal compared to scan based methods, however, a sequential ATPG system is necessary for test generation. The basic idea Is to use independent clock lines to control disjoint groups of flip-flops. No cyclic path are permitted among the flip-flops of the same group. During testing, a selected group can be made to hold its state by disabling its …

Estimating The Quality Of Manufactured Digital Sequential Circuits, Dharam Vir Das, Sharad C. Seth, Vishwani Agrawal

School of Computing: Faculty Publications

Detection of a fault in a sequential circuit requires a sequence of test vectors. This sequence activates the fault and propagates the effect of the fault to a primary output. To accomplish this, the test sequence must set flip-flops through a series of states. Unlike a combinational circuit, many faults in a sequential circuit cannot be detected by a single vector. We propose a statistical model in which. a fault is characterized by two parameters: a pervector detection probability and an integer-valued latency. Irrespective of its detection probability, the fault cannot be detected by a vector sequence shorter than the …

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 …

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.

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 …

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.

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 …

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 …

Fuzzy Neural Logic Network And Its Learning Algorithms, Fiona Fui-Hoon Nah, Nah Fiona

Research Collection School Of Computing and Information Systems

The paper introduces the basic features of fuzzy neural logic network. Each fuzzy neural logic network model is trained from a set of knowledge in the form of examples using one of the three learning algorithms introduced. These three learning algorithms are the delta rule controlled learning algorithm and two mathematical construction algorithms, namely, the local learning method and the global learning method. Once the fuzzy neural logic network model is constructed, it is ready to accept any unknown input from the user. With a low percentage of mismatched features, output solution can be obtained.

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 …

Reducing Computational Expense Of Ray-Tracing Using Surface Oriented Pre-Computation, Robert E. Rinker

UNF Graduate Theses and Dissertations

The technique of rendering a scene using the method of ray-tracing is known to produce excellent graphic quality, but is also generally computationally expensive. Most of this computation involves determining intersections between objects in the scene and ray projections. Previous work to reduce this expense has been directed towards ray oriented optimization techniques. This paper presents a different approach, one that bases pre-computation on the characteristics of the scene itself, making the results independent of the position of the observer. This means that the results of one pre-computation run can be applied to renderings of the scene from multiple view …