Computer Science Technical Reports
This collection consists of Technical Reports from the Faculty of Computer Science at UNB Fredericton. These were initially submitted to an older repository, but have been re-uploaded here with the same permissions.
Pages
- 3-D graphics in APL: user perspective
- The purpose of this document is to explain how a user can generate and display three dimensional objects in APL. We will not deal with how the system is put together. The top-down approach will be used.
- 3-D solids from 2-D views
- An algorithm to generate three dimensional sold objects, made up of planar surfaces, from the given three conventional engineering orthographic views is presented in this paper. Consisting of six major steps, the algorithm has been programmed in C on IRIS 1400 graphics workstation. The algorithm generates all possible solutions. The infinite space has been divided into finite subspaces by making use of the surface normals and the direction of travel of the edges that connect the faces. Classification of the probable 3-D subobjects into the certain and uncertain ones has proved to be very useful in reducing the time taken by the algorithm. Several illustrative examples, simple as well as complex giving single and multiple solutions, are included.
- 3-D visualization of message passing in distributed programs
- This paper describes PVMtrace, a software system for understanding and debugging message passing in distributed programs. In this system each process is represented as a node in a graph and the arcs represent the potential communication channels. The transfer of a packet of information from one process to another is shown by a bead-like object moving along an arc. A queue is a string of beads lined up waiting to be processed. The flexible control over time is found to be essential for the system to be useful and it allows the animation to be played forward and backwards in time both by the direct manipulation of the time line and by an animation rate controller. In addition there is an automatic time control method that rapidly moves the animation through intervals of low activity while slowing down in periods of high activity. The system was initially developed as a PVM debugging tool but it has also been found to be useful in other areas. In particular it has been used to visualize communications in a cellular phone system.
- A Data Structure for I/O Efficient Search of Objects Moving on a Graph
- We present a spatio-temporal data structure called minimum I/O Graph Strip Tree (minGStree) to index moving objects on a graph. The minGStree is designed to efficiently answer time instance and time interval queries about the past positions of moving objects. The minGStree uses Θ( n ) blocks of external memory, where n B is the number of moving object instances (unique entries of moving objects) and B is the I/O block size. For n moving object instances randomly distributed on the E edges of a graph over a time domain [0, T ], the expected number of I/Os required to determine the moving objects intersecting one edge (for both time instance queries and time interval queries) in a minGStree is O(logB ( n ) + k), where k is the number E of disk blocks required to store the answer. We anticipate this data structure will be practical to implement.
- A Fast Incremental Convex Hull Algorithm for Higher Dimensions
- An online algorithm is described which finds the facets of the convex hull of a set of points in d-dimensional space. For point sets chosen at random from some distribution, the algorithm is O(nl +F) for fixed d, where n is the number of points, l is the expected number of sides of a polygon defined by the intersection of a 2-flat with the polytope, and F is the expected number of facets.
- A Language for High-Level Description of Adaptive Web Systems
- This paper focuses on the proposal, design, and implementation of AWL, the Adaptive Web Language. Also, an example application named PENS is explained and implemented in AWL. AWL development was inspired by several issues and shortcomings in the development of adaptive Web systems using the framework for adaptive Web systems, developed in the Intelligent and Adaptive Systems Research Group, at the University of New Brunswick, Fredericton, Canada. Lack of verification mechanisms and difficulty in development are two of the existing issues in the framework. Not only does AWL address those issues in the framework, but it also offers mechanisms to increase software quality attributes, especially, reusability. AWL has been designed based on the analysis of adaptive Web systems, having taken into account the principles of reuse-based software engineering (product-lines), domain-specific languages, and aspect-oriented programming, all of which are ongoing research fields in software engineering research. A compiler, named AWL Compiler has been developed, as the implementation of AWL for our adaptive Web framework. AWL Compiler automates the development process through hiding the framework internals from the application designer, and provides verification services so that applications can be verified to be consistent and meaningful. PENS, a personalized e-News system, is explained and its various aspects are developed using AWL. Key words: Adaptive Web Systems, Domain-Specific Languages, Reuse-based Design
- A New Dominant Point-Based Parallel Algorithm for Multiple Longest Common Subsequence Problem
- This work introduces a new parallel algorithm for computing a multiple longest common subsequence (MLCS). Given a set of strings, the longest common subsequence can be obtained by removing a number of symbols from each sequence. Although there was a lot of research done in the parallelization of MLCS algorithms for the special case of two sequences, so far there were no any general parallel methods for computing MLCS of an arbitrary number of sequences. Our method is a parallel approach to dominant points-based method recently proposed by Hakata and Imai. The parallel algorithm is presented and the related theoretical results as well as the algorithm’s implementation on IBM SP3 using MPI system are discussed. Keywords: longest common subsequence, dominant points, parallel algorithms, IBM SP3