Faculty & Staff Research

Permanent URI for this community

https://unbscholar.lib.unb.ca/handle/1882/12768

Browse

Browsing Faculty & Staff Research by Issue Date

Filter results by year or month
Now showing 1 - 20 of 1016
  • Thumbnail Image
    Item
    A new spanning tree algorithm
    (1974) Wasson, W., D.; McIssaac, Robert
    The algorithm outlined in this paper finds all the spanning trees of a non-directed graph G. The graph is represented by a binary incidence matrix using compact bit storage. Each row of the matrix corresponds to a branch of the graph and is represented by one or more computer words. Each column of the matrix corresponds to a graph node and is represented by a single bit within each computer word or multiple word. It is shown, in addition to saving computer storage, that this representation greatly speeds up the tree generation process by allowing many bit-parallel operations to occur during the execution of a single computer instruction cycle.
  • Thumbnail Image
    Item
    A search algorithm for finding the simple cycles of a directed graph
    (1974) Johnson, LeRoy
    Two efficient algorithms, that admit each simple cycle once in searching the ares of a digraph, are presented and a proof of the algorithms provided. The first algorithm is nonadaptive while the second is an adaptive one. Since they extract cycles directly, they require less storage than Weinblatt. Since the method of search of the first is more efficient than Tiernan, it is faster than Tiernan. An example used by Tiernan is given for comparison. The speed is discussed in relation to number of vertices, arcs, and simple cycles. The storage requirement is 0(n). The adaptive version has a theoretical speed bound by O(c.m.n), where c is the number of cycles, m the number of arcs, and n the number of vertices. Both algorithms are bounded by 0(N[subscript c] .m) on the complete graph where Ν[subscript c] is the number of cycles of the complete graph.
  • Thumbnail Image
    Item
    Remote job entry and output through APL
    (1974) Gujar, Uday, G.
    The power of interactive computing and especially of APL is already well recognized. Some limitations and inconveniences of processing a job through batch can at least partially be offset by providing a similar processing capability for O.S. jobs from an APL terminal. This paper describes such a facility. The system, called RJE/RJO, is first described from the APL user's point of view. The later portion of the paper discusses the system design and implementation. The facility, which has satisfied the needs of a number of users, has been used under APL/360 and is currently being used under APLSV.
  • Thumbnail Image
    Item
    Quadrature formulae for functions of two variables and applications
    (1975) Garey, Lawrence; LeBlanc, Marcella
  • Thumbnail Image
    Item
  • Thumbnail Image
    Item
    Block methods for nonlinear Volterra integral equations
    (1975) Garey, Lawrence, E.
    An adaptation of a method by Boland [3] leading to a generalization of the block methods of Linz [8] are presented in this paper. Conditions for such methods to be convergent and A-stable are given along with some numerical examples.
  • Thumbnail Image
    Item
    An algorithm for determining the chromatic number of a graph
    (1975) Miller, D., M.
    An algorithm for determining the chromatic number of a graph is presented. The storage requirement is on the order of the square of the number of vertices in the graph. Preliminary empirical tests indicate this algorithm is faster than previous algorithms.
  • Thumbnail Image
    Item
    Determining Cliques of a Graph
    (1975) Johnson, Leroy, F.
    A generalization of the neighborhood of a vertex [7] is used to prove several results on the relation of a set of vertices of a graph to cliques of that graph. These results lead to an efficient adaptive algorithm for enumerating the cliques of a graph. The storage requirement of the algorithm is of order O(n2).
  • Thumbnail Image
    Item
    Subroutines with variable number of arguments
    (1975) Gujar, Uday, G.
    In designing a general purpose subroutine package to solve a class of problems, one often has to write subroutines with a large number of arguments. Though these arguments are required to cover a range of possibilities, many of these arguments have some commonly occurring values. The user is usually burdened with supplying a long list of arguments and making sure that the number and types match. Alternate solution is to write such subroutines in the assembly language so that they could have variable number of arguments. This approach eliminates a large class of program designers who do not and do not want to know the assembler language. This paper describes a facility which enables these program designers to write their routines completely in a higher level language (FORTRAN) and yet enjoy the "luxury" of having variable number of arguments in the calling sequence.
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
  • Thumbnail Image
    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.
  • Thumbnail Image
    Item
    A partition monitor for fast-batch-processing with limited execution (FABLE)
    (1976) Emin, Patric, P.
    FABLE is a sub-tasking monitor which was designed originally to execute as a problem program under IBM's OS/MFT-II (with sub-tasking) operating system. It provides a facility for programmers at any HASP workstation, reader or RJE terminal, to submit programs or problems to a variety of compilers and processors, such as: WATFIV, PL/C, ALGOLW, WATBOL, and ASSIST, without the usual overhead required for job scheduling and resource allocation. Output is returned to the same terminal with very fast turnaround. Programs are submitted in batches of one or more problems, for one or more processors, in any order; the only job control language (JCL) required is one job card per batch.
  • Thumbnail Image
    Item
    Automatic job scheduling in hasp
    (1977) Gujar, Uday, G.; Fellows, David, M.
    Multiprogramming systems require that a fair, equitable algorithm be used for the scheduling of jobs. This paper discusses some of the problems associated with this and proposes an automatic job scheduling algorithm. The major parts of the algorithm have been implemented and have been in use for over one year. The user interface is simplified and the operational complexities are minimized. The parameters used for the algorithm are the estimates of the central processor time and the memory required by the job. All types of jobs including those requiring operator attention during execution are covered under the scheme. Operational data and the reactions from the users indicate that the results have been as expected.
  • Thumbnail Image
    Item
  • Thumbnail Image
    Item
    On the use of "fixed" data paths for assignment
    (1979) Middleton, Tony
  • Thumbnail Image
    Item
    A transformation approach to implementing aggregate operations
    (1979) Middleton, Tony
    Some of the expressive power of certain programming languages depends on the provision of convenient means of operating on collections, or "aggregates", of data values. This paper argues that certain aggregate operations could be implemented by applying transformations to fragments of program which access the elements of an aggregate. The proposals are considered to be a viable means of supporting "data abstractions" - i.e. for allowing certain operations in a language to be insensitive to the detailed implementation of a data structure.
  • Thumbnail Image
    Item
    Representing data paths by program structures
    (1979) Middleton, Tony
    This paper discusses an approach to using program fragments to characterise data aggregates (or "data paths"). The main topic of the paper is the use of this representation to specify assignments between data paths. The approach allows certain assignments between paths to be represented in a conceptually simpler manner than would be the case for conventional techniques.
  • Thumbnail Image
    Item
    oSCUBA a buffered core graphic system
    (1979) Gujar, Uday, G.; Nagesh, Aragam, R.
    The graphics community is recently taking a close look at graphics standardization prompted by issues such as portability of software, application program structure, diverse hardware, etc. Through these efforts, the Graphic Standards Planning Committee of ACM/SIGGRAPH has proposed a standard. This standard advocates four levels of the Core system, namely basic, buffered, interactive and complete. This paper describes a Level 2 (i.e. buffered) implementation of the Core system in APL, referred to as oSCUBA (APL BUffered Core System). The details of the structure and organization of oSCUBA are given. The implementation is highly modular in nature, provides both two and three dimensional capabilities with several types of projective transformations and supports full segmentation capabilities. Several examples illustrating the use of the system are included. The interactive nature of APL is found to be attractive. Some deviations from the Core system have been incorporated. These include a modular hardcopy interface to produce graphics on plotters etc. and a facility to retain world coordinates of the objects. The system, though appearing to be satisfactory, has to undergo further testing to gain user confidence.
  • Thumbnail Image
    Item
    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.