Browsing Faculty & Staff Research by Issue Date
Now showing 1 - 20 of 785
Results Per Page
ItemA new spanning tree algorithm(1974) Wasson, W., D.; McIssaac, RobertThe 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. ItemRemote 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. ItemA search algorithm for finding the simple cycles of a directed graph(1974) Johnson, LeRoyTwo 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. ItemDetermining Cliques of a Graph(1975) Johnson, Leroy, F.A generalization of the neighborhood of a vertex  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). ItemQuadrature formulae for functions of two variables and applications(1975) Garey, Lawrence; LeBlanc, Marcella ItemSubroutines 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. ItemBlock methods for nonlinear Volterra integral equations(1975) Garey, Lawrence, E.An adaptation of a method by Boland  leading to a generalization of the block methods of Linz  are presented in this paper. Conditions for such methods to be convergent and A-stable are given along with some numerical examples. ItemComments on "A General Fortran Emulator for IBM 360/370 Random Number Generator 'Randu' 1"(1975) Fellows, David, M. ItemAn 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. ItemA 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. ItemA 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. ItemA 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. ItemStep by step methods for the numerical solution of Volterra integro-differential equations(1976) Garey, Lawrence, E. ItemAutomatic 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. ItemA priori estimation of variance for surveying observables(1978) Nickerson, B. G. ItemA transformation approach to implementing aggregate operations(1979) Middleton, TonySome 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. ItemRepresenting data paths by program structures(1979) Middleton, TonyThis 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. ItemOn assignment between data paths(1979) Middleton, TonyThis paper discusses an approach to the manipulation of "data paths". In particular, assignment between data paths is discussed. The notion of a "data path" is somewhat similar to that of an "abstract data structure" except that there is greater emphasis on the fact that elements are processed sequentially. The work is part of a broader effort to allow higher-level operations to be applicable to a wider range of data paths. The aim is to specify higher-level operations in such a manner that the nature of the data paths being manipulated is conveyed explicitly, and naturally, along with the specification of the operations being performed. Only simple cases are dealt with, but that is considered to reflect "work done so far" rather than inherent limitations of the approach. ItemoSCUBA 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.