# Research Reports

## Permanent URI for this collection

Reports are separately-published records of research findings, research still in progress, policy developments and events, or other technical findings, usually bearing a report number and sometimes a grant number assigned by the funding agency. Also, an official record of the activities of a committee or corporate entity, the proceedings of a government body, or an investigation by an agency, whether published or private, usually archived or submitted to a higher authority, voluntarily or under mandate. (URI: http://purl.org/coar/resource_type/c_93fc)

Item types include:

- clinical study
- data management plan
- memorandum
- policy report
- project deliverable
- research protocol
- research report
- technical report

## Browse

### Browsing Research Reports by Subject "Computer Science"

Now showing 1 - 20 of 185

###### Results Per Page

###### Sort Options

Item 3-D graphics in APL: user perspective(1988) Gujar, Uday, G.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.Item 3-D solids from 2-D views(1988) Gujar, Uday, G.; Nagendra, I., V.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.Item 3-D visualization of message passing in distributed programs(1996) Gobrecht, Cyril; Ware, Colin; Bhavsar, Virendrakumar, C.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.Item A comparison of non-point spatial data indexing methodologies(1990) Xie, LipingThe general objective of this research is to compare the performance of several spatial indexing methods. In order to do so, we built spatial indices for two-dimensional nonzero size objects and performed range searches on those objects. There are two ways to create an index: 1) use the spatial data support in commercially available databases such as Oracle 8i and O2, and 2) create the spatial data-indexing scheme directly using spatial data structures such as the R-tree or Grid file. A new data structure based on the binaryradix bucket-region (BR2) grid file was created for non-point objects. Two sets of data from the National Topological Database were used to perform the experimental comparisons. We performed two different types of range search: search based on the bounding box of the objects only (primary) and search based on the real data (secondary). Testing was performed with query window areas= 1%, 4%, 9%, 16%, 25%, 36%, 49%, 64%, 81%, and I 00% of the data extent. For secondary range search, the R-tree and the modified grid file took the least amount of time (0.497 seconds and 0.628 seconds respectively) on average to report (out of a test set of 20,000 objects) the objects in range for a query window area= 49% of the original data extent. The Oracle 8i Spatial object-relational, and the Oracle 8i Spatial relational methods required, on average, 220, and 400 times more time for the same search, respectively. Significant difficulties were encountered in getting the commercially available databases to perform range searches on the test data.Item A comparison of vectorizable discrete sampling methods in Monte Carlo applications(1995) Sarno, Riyanarto; Bhavsar, Virendra, C.; Hussein, Esam, M., A.The performance of various vectorizable discrete random-sampling methods, along with the commonly used inverse sampling method, is assessed on a vector machine. Monte Carlo applications involving, one-dimensional, two-dimensional and multi-dimensional probability tables are used in the investigation. Various forms of the weighted sampling method and methods that transform the original probability table are examined. It is found that some form of weighted sampling is efficient, when the original probability distribution is not far from uniform or can be approximated analytically. Table transformation methods, though require additional memory storage, are best suited in applications where multi-dimensional tables are involved. Keywords: Discrete sampling, Weighted sampling, Monte Carlo simulations, Vector processing.Item A computer aided design tutorial system (CADETS)(1986) Slipp, Leonard; Gujar, Uday, G.Computer aided design (CAD) systems have proved to be a very valuable toll widely used in industry. These systems are often expensive both from the hardware and software point of view. As such first hand training becomes an expensive proportion especially in an environment where training is the main goal and production a secondary or a minor goal. Such is the case in the educational institutions. This paper describes a two-dimensional Computer Aided Design Tutorial System (CADETS) modelled after Unigraphics I. Written in APL, the system does not demand any knowledge of APL for the user. An IBM 3279 colour graphics terminal is used as a graphics input as well as output device. The screen is divided into five windows. The main, and the largest, window is used for graphics; the others are used for user communication. Menus are used extensively to generate, modify and manipulate the display. Within CADETS, there are currently eleven ways to create a point, thirteen ways to create a line segment, ten ways to specify a circular arc and several functions to generate common geometric objects such as triangles, rectangles, polygons, etc. Once created, the user may edit the graphics model by deleting geometric entities either individually or in a group. Line segments may be extended or trimmed to specified boundaries, constrained to intersect at a corner, etc. Arcs may be extended or truncated so that they would be bound by specified angles or points or lines which intersect them. The visual attributes of any entity may be changed. The user can also control the view area and scale of model thus providing a pan and zoom capability to concentrate on selected areas of the display. An interface has been provided to produce a hardcopy on a variety of devices. The system has been used by several users including high school students who were unaware of even the existence of APL. The system requires minimal investment on hardware as well as software compared to sophisticated expensive systems, yet provides tools for teaching several fundamental CAD techniques. Plans are underway to enhance 2-D capabilities, incorporate other inexpensive graphics devices and include 3-D graphics.Item A Data Structure for I/O Efficient Search of Objects Moving on a Graph(2009) Le, Thuy, T., T.; Nickerson, Bradford, G.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.Item A device independent computer plotting system(1976) Gujar, Uday, G.Almost every computing centre has a variety of plotting devices. Software available for these plotting devices is often device dependent. As a result, in order to switch from one plotting device to another, the user has to make several programming changes. This procedure is error prone and time consuming. This paper describes a device independent computer plotting system which is based on several routines accessible from FORTRAN IV. The transition from one plotting device to another is completely transparent to the user of this system. The paper begins with the descriptions of various plotting devices and plotting modes. This is followed by an overview which consists of an example and functional descriptions of all the routines. The system interface and the basis on which the device independence is achieved are discussed in the later portion of the paper. Finally, the data structures used in the offline mode of plotting, the algorithms used in the various driver routines and the mechanism used to account for the plotting resources are presented. The interface for adding a new plotting device has been formalized and defined. The system is open ended and can be expanded in the device independent as well as the device dependent area.Item A driver for raster-like plotting devices(1976) Gujar, Uday, G.; Fitzgerald, J., A.Electrostatic plotter type devices, CRT or hardcopy, are basically printers which allow the "paper" movement only in one direction. As a result, the entire display file has to be created before the process of generating the display can begin. This arrangement differs significantly from the X-Y plotters where the "plotting pencil" and/or paper may be moved in any direction. An algorithm for generating a display on the electrostatic plotter type devices is described in this paper. This algorithm is based upon creating and maintaining a vector file consisting of end points of visible vectors, sorting these vectors, and then generating the plot - a strip at a time. Only the points that lie within the strip are calculated. The details of implementation and the data structure used are discussed. There is no restriction on the size of the display that can be generated; in fact, plots of size 100" by 20" have been produced using this algorithm. No a-priori knowledge of the extent of the plot is required. The algorithm has been designed to operate in a device independent computer plotting system and has worked very satisfactorily without imposing any restrictions on the users. Key Words and Phrases: graphics, electrostatic plotters, raster displays, vector generation, data structure, sorting.Item A dynamic data structure for efficient bounded line range search(2010) Le, Thuy, T.; Nickerson, Bradford, G.A dynamic data structure for efficient axis-aligned orthogonal range search on a set of n lines in a bounded plane is presented. The algorithm requires O(log n + k) time in the worst case to find all lines intersecting an axis aligned query rectangle R, for k the number of lines in range. O(n + lambda) space is required for the data structure used by the algorithm, where lambda is the number of intersection points among the lines. Insertion of a new rightmost line l or deletion of a leftmost line l requires O(n) time in the worst case. For a sparse arrangement of lines (i.e., for lambda = O(n)), insertion of a rightmost line l or deletion of a leftmost line l requires O (√n) expected time.Item A dynamic data structure for multi-dimensional range searching(1996) Lamoureau, Michael, G.This thesis addresses the following question: Is it possible to have a k-dimensional data structure which provides for efficient k-d range search and dynamic updates on a set of n points in the worst case while maintaining reasonable storage and preprocessing requirements? Define a data structure to be optimally balanced when the product of its worst case preprocessing, storage, insertion, deletion, and range search cost functions is minimal and dynamically balanced when the product of its insert, delete and range search cost functions is minimal. The optimal balance cost is Q(n2lg4kn) and the dynamic balance cost is O(lg3kn). The optimal worst case range search time is O(lgkn + t) (where we report t points in range) for such structures. Structures optimal for range search in the class of dynamically balanced structures are illustrated and found to be within O(lgk-1n) of optimal. A new k-d structure labeled the k-d Range Deterministic Skip List (DSL) is defined and analyzed along with a new variation of the dynamic range tree labeled the k-d Range AVL tree. Both structures are dynamically balanced and optimal for worst case range search in the model. Experimentally, a mere 20 milliseconds was required to report all 500 datapoints in range for the largest 4-d structure (of 336 MB) built. Both structures perform well. They possess similar update times but we find that the k-d Range DSL is approximately twice as fast as the k-d Range AVL tree for insertions while the k-d Range AVL tree is approximately fifteen times faster for deletions.Item A Fast Incremental Convex Hull Algorithm for Higher Dimensions(1990) Stewart, W. M.; Horton, J. D.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.Item A Formal Grammar for Geographic Information Metadata(2000) Nickerson, Bradford, G.; Teng, YingItem A Fortran to Modula 2 dictionary(1992) Knight, W., R.; Fellows, D., M.Item A hyperfactorization of order 8, index 2(1988) Horton, J., D.Item A knowledge-based spectroscopic assignment system(1993) Wang, JinStudying the energy level structure of different molecules by means of spectroscopy is one of the fields in physics and chemistry. MOSAA[superscript 1] developed in this thesisis a knowledge-based system which can assist researchers in the assignment of the peaks of the molecules in question by using the spectral information provided, along with a knowledge base containing known energy levels of the given molecules and spectroscopic assignment rules provided by physicists. Rules together with their associated components (i.e. parameters, functions and properties) compose the knowledge base for methanol spectroscopy assignment. Rules and their components are written in plain text using special grammars. A compiler created using lex and yacc is used to translate a rule file into an internal knowledge base data structure. A total of 313 rules for spectroscopic assignment are defined. The MOSAA system inference engine combines backward chaining and forward chaining as well as two special mechanisms 'TRY' and 'Restart'. This inference engine is written in C++, and was designed specifically to handle the "generate and test" process required for spectroscopic assignment. An overview of the MOSAA implementation is given. This includes a description of the top level structure, preprocessing and user interface. MOSAA was tested using two methanol species spectra (Spectrum CD[subscript 3][supercript 18]OH in the 900-1100 cm[superscript -1] region and Spectrum CD[subscript 3][superscript 16]OH in the 915-1030 cm[superscript -1] region). This testing showed that MOSAA successfully assigns 11 series in spectrum CH§ 8 0H testing and 11 series in spectrum CD[subscript 3][superscript 16]OH testing.Item A Language for High-Level Description of Adaptive Web Systems(2006) Hossein Sadat, S.; Mohtasham, K.; Ghorbani, Ali, A.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 DesignItem A lower bound on the number of one-factors in bicubic graphs(1984) Horton, J., D.The number of one-factors in a bicubic graph is shown to be more than polynomial in the number of vertices. Thus the permanent of a matrix of 0's and 1's in which each row and column includes precisely three 1's is more than polynomial. This improves the known lower bound of 3n. The form of the bound for a graph with 2n vertices is cnan [an superscript], where c is some constant and a < log 2[subscript] (9/4)=.85... . OTHER KEYWORDS: permanents, 0-1 matricesItem A method for designing a lexical analyzer(1979) Gujar, Uday, G.; Dedurek, John, M.; McIntyre, Marion, E.The scanner is a subroutine which is frequently called by an application program like a compiler. The primary function of a scanner is to combine characters from the input stream into recognizable units called tokens. A method has been presented in this paper for designing such a scanner, also frequently referred to as a lexical analyzer in the current literature. The major steps involved in this design process are: identification of tokens, construction of a state diagram, building driver tables and finally writing a scanning routine. The rules for generating the driver tables are described and an algorithm for the scanner, utilizing these driver tables, is included. The method has been successfully used to build the system scanner for a user oriented plotting language. It is concluded that the method is well defined, gives rise to a modular design and as such easily lends itself to language extensions.Item A New Approach for Specification and Verification Of Distributed Agents(2000) Mironov, Andrew, M.; Bhavsar, Virendra, C.