Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons™

Open Access. Powered by Scholars. Published by Universities.®

Computer Sciences

Institution
Keyword
Publication Year
Publication
Publication Type
File Type

Articles 54271 - 54300 of 57997

Full-Text Articles in Physical Sciences and Mathematics

On The Complexity Of Manpower Shift Scheduling, Hoong Chuin Lau Jan 1996

On The Complexity Of Manpower Shift Scheduling, Hoong Chuin Lau

Research Collection School Of Computing and Information Systems

We consider the shift assignment problem in manpower scheduling, and show that a restricted version of it is NP-hard by a reduction from 3SAT. We then present polynomial algorithms to solve special cases of the problem and show how they can be deployed to solve more complex versions of the shift assignment problem. Our work formally defines the computational intractibility of manpower shift scheduling and thus justifies existing works in developing manpower scheduling systems using combinatorial and heuristic techniques.

Go to article

Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang Jan 1996

Time- And Cost-Optimal Parallel Algorithms For The Dominance And Visibility Graphs, D. Bhagavathi, H. Gurla, S. Olariu, J. L. Schwing, J. Zhang

Computer Science Faculty Publications

The compaction step of integrated circuit design motivates associating several kinds of graphs with a collection of non-overlapping rectangles in the plane. These graphs are intended to capture various visibility relations amongst the rectangles in the collection. The contribution of this paper is to propose time- and cost-optimal algorithms to construct two such graphs, namely, the dominance graph (DG, for short) and the visibility graph (VG, for short). Specifically, we show that with a collection of n non-overlapping rectangles as input, both these structures can be constructed in θ (log n) time using n processors in the CREW model.

Go to article

Analysis Of (Iso)Surface Reconstructions: Quantitative Metrics And Methods, Tracey Allen Beauchat Jan 1996

Analysis Of (Iso)Surface Reconstructions: Quantitative Metrics And Methods, Tracey Allen Beauchat

Dissertations, Theses, and Masters Projects

Due to sampling processes volumetric data is inherently discrete and most often knowledge of the underlying continuous model is not available. Surface rendering techniques attempt to reconstruct the continuous model, using isosurfaces, from the discrete data. Therefore, it natural to ask how accurate the reconstructed isosurfaces are with respect to the underlying continuous model. A reconstructed isosurface may look impressive when rendered ("photorealism"), but how well does it reflect reality ("physical realism")?;The users of volume visualization packages must be aware of the short-comings of the algorithms used to produce the images so that they may properly interpret, and interact with, …

Go to article

A Grammar-Based Technique For Genetic Search And Optimization, Clayton Matthew Johnson Jan 1996

A Grammar-Based Technique For Genetic Search And Optimization, Clayton Matthew Johnson

Dissertations, Theses, and Masters Projects

The genetic algorithm (GA) is a robust search technique which has been theoretically and empirically proven to provide efficient search for a variety of problems. Due largely to the semantic and expressive limitations of adopting a bitstring representation, however, the traditional GA has not found wide acceptance in the Artificial Intelligence community. In addition, binary chromosones can unevenly weight genetic search, reduce the effectiveness of recombination operators, make it difficult to solve problems whose solution schemata are of high order and defining length, and hinder new schema discovery in cases where chromosome-wide changes are required.;The research presented in this dissertation …

Go to article

A Family Of Parallel Runge-Kutta Pairs, P. Bogacki Jan 1996

A Family Of Parallel Runge-Kutta Pairs, P. Bogacki

Mathematics & Statistics Faculty Publications

Increasing availability of parallel computers has recently spurred a substantial amount of research concerned with designing explicit Runge-Kutta methods to be implemented on such computers. Here, we discuss a family of methods that require fewer processors than methods presently available do, still achieving a similar speed-up. In particular, (5,6) and (6,7) pairs are derived, that require a minimum number of function evaluations on two and three processors, respectively.

Go to article

Arbitrary Views Of High-Dimensional Space And Data, Andrew Ellerton Jan 1996

Arbitrary Views Of High-Dimensional Space And Data, Andrew Ellerton

Theses : Honours

Computer generated images of three dimensional scenes objects are the result of parallel/perspective projections of the objects onto a two dimensional plane. The computational techniques may be extended to project n-dimensional hyperobjects onto (n-1) dimensions, for n > 3. Projection to one less dimension may be applied recursively for data of any high dimension until that data is two-dimensional, when it may be directed to a computer screen or to some other two-dimensional output device. Arbitrary specification of eye location, target location, field-of-view angles and other parameters provide flexibility, so that data may be viewed-and hence perceived-in previously unavailable ways. However, …

Go to article

The Design And Implementation Of A Toolkit For The Creation Of Virtual Environments, Jesse Kinross-Smith Jan 1996

The Design And Implementation Of A Toolkit For The Creation Of Virtual Environments, Jesse Kinross-Smith

Theses : Honours

Virtual Reality is a field that is steadily increasing in popularity and interest. New developments in both hardware and software have empowered developers with new devices allowing faster and better quality interaction with virtual environments. However, the emphasis of research in virtual environments has been more concerned with development of new display and input devices, as opposed to the investigation of different methods of interaction that a three-dimensional environment offers. This project designs and implements a three-dimensional, interactive, virtual environment development system upon an existing three-dimensional rendering engine. The aim of the project is to allow users to generate virtual …

Go to article

Simulator For The Performance Analysis Of Cpm Schemes In An Indoor Wireless Environment, Ronald Chua Jan 1996

Simulator For The Performance Analysis Of Cpm Schemes In An Indoor Wireless Environment, Ronald Chua

Theses : Honours

A software simulator for characterising Continuous Phase Modulation (CPM) schemes in an indoor multipath environment has been developed using SIMULINK and MATLAB. The simulator is capable of simulating a wide range of CPM schemes to determine bandwidth efficiency and robustness to additive white Gaussian noise (AWGN) and Rician fading. Initial trials of the simulator indicate that the simulator is functioning correctly. Eventually, the simulator will be used to determine the most suitable modulation scheme for the development of an actual indoor wireless system.

Go to article

Towards A Model For Software Project Estimating, Stuart Hope Jan 1996

Towards A Model For Software Project Estimating, Stuart Hope

Theses : Honours

The use and development of software is an integral and critical part of modern industrial society. The outcomes of many software development and maintenance projects have been less than satisfactory with significant numbers being over schedule, lacking in functionality and over budget. These problems are the result of poor management of both the process and the product. One of the major problems to overcome in the management of software development projects is the ability to predict the outcomes early in the project when there are a large number of unknowns. The ability to reliably predict the outcomes in a repeatable …

Go to article

An Investigation Into An Effective Method Of Automatically Analysing Oracle Applications To Count Function Points, J. L. Wong Jan 1996

An Investigation Into An Effective Method Of Automatically Analysing Oracle Applications To Count Function Points, J. L. Wong

Theses : Honours

Function Point Analysis (FPA) is a synthetic software estimation metric used for computing the size and complexity of applications. It was first introduced by Allan. J. Albrecht during the mid-seventies, as a result of a lengthy research based on applications that were developed using COBOL and PL/1 programming languages. The purpose of this research· is to investigate the possibility, and the most effective method, of automatically performing a Function Point Analysis on Oracle applications that consist of Oracle Forms and Oracle Reports. The research revealed a seemingly lack of other researches on this topic. As FPA was invented a few …

Go to article

Evolution Of Musical Organisms, Bruno Degazio Jan 1996

Evolution Of Musical Organisms, Bruno Degazio

Publications and Scholarship

The development of software for musical applications has led to a proliferation of elaborate control paradigms with extremely large parameter spaces. These spaces can be daunting to explore interactively because of their vastness. Furthermore, parameters often interact in ways not made explicit by the control panel, effectively increasing the complexity of the space even further. Application of genetic algorithms (GAs) can be used to search through these vast spaces in a highly efficient manner. Coordinated control of interacting parameters is handled automatically by this system. Even for control paradigms that are well understood, the genetic algorithm can efficiently search out …

Go to article

Design Of Nonblocking Atm Networks, J. Andrew Fingerhut, Rob Jackson, Subhash Suri, Jonathan S. Turner Jan 1996

Design Of Nonblocking Atm Networks, J. Andrew Fingerhut, Rob Jackson, Subhash Suri, Jonathan S. Turner

All Computer Science and Engineering Research

This paper considers the problem of designing ATM networks that are nonblocking with respect to virtual circuit requests, subject to specified constraints on the traffic. In this paper, we focus on global traffic constraints that simply limit the total entering and exiting traffic at each switching system. After reviewing prior results for linear link costs, we introduce a more realistic link cost model, and develop a number of results using it. We also describe a technique for converting tree-structured networks to nonblocking hierarchical networks satisfying limits on the capacity of any single switch.

Go to article

Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner Jan 1996

Designing Minimum Cost Nonblocking Communication Networks, J. Andrew Fingerhut, Subhash Suri, Jonathan S. Turner

All Computer Science and Engineering Research

This paper addresses the problem of topological design of ATM (and similar) communication networks. We formulate the problem from a worst-case point of view, seeking network desings that, subject to specified traffic constraints, are nonblocking for point-to-point and multicast virtual circuits. Within this model we give various conditions under which star networks are optimal or near-optimal. These conditions are approximately satisfied in many common situations making the results of practical significance. An important consequence of these results is that, where they apply, there is no added cost for nonblocking multicast communication, relative to networks that are nonblocking for point-to-point traffic …

Go to article

Design Of A Gigabit Atm Switch, Tom Chaney, Andrew Fingerhut, Margaret Flucke, Jonathan S. Turner Jan 1996

Design Of A Gigabit Atm Switch, Tom Chaney, Andrew Fingerhut, Margaret Flucke, Jonathan S. Turner

All Computer Science and Engineering Research

This report describes the design and implementation of a gigabit ATM switching system supporting link rates from 150 Mb/s to 2.4 Gb/s, with a uniquely efficient multicast switch architecture that enables the construction of systems with essentially constant per port costs for configurations ranging from 8 to 4096 ports and system capacities approaching 1- Tb.s. The system design supports many-to-one and many-to-many forms of multicast, in addition to the usual one-to-many. It also provides multicast virtual paths, constant time configuration of multicast connections and an efficient packet-level discard method, that can achieve 100% link efficiencies, without large buffers.

Go to article

Reconsidering Fragmentation And Reassembly, Girish P. Chandranmenon, George Varghese Jan 1996

Reconsidering Fragmentation And Reassembly, Girish P. Chandranmenon, George Varghese

All Computer Science and Engineering Research

We reconsider several issues related to fragmentation and reassembly in IP. We first reconsider reassembly. We describe a simple expected case optimization that improves reassembly performance to 38 instructions per fragment if the fragments arrive in FIFO order (the same assumption made in header prediction) which has been implemented in the NetBSD kernel. Next, we introduce the new idea of Graceful Intermediate Reassembly (GIR), which is a generalization of the existing IP mechanisms of destination and hop-by-hop reassembly. In GIR, we coalesce the fragments at an intermediate router in order to use the largest sized packets on its outgoing interface. …

Go to article

On The Performance Of Early Packet Discard, Maurizio Casoni, Jonathan S. Turner Jan 1996

On The Performance Of Early Packet Discard, Maurizio Casoni, Jonathan S. Turner

All Computer Science and Engineering Research

In a previous paper [3], one of the authors, gave a worst-case analysis for the Early Packet Discard (EPD) technique for maintaining packet integrity during overload in ATM switches. This analysis showed that to ensure 100% goodput during overload under worst-case conditions, requires a buffer with enough storage for one maximum length packet from every active virtual circuit. This paper refines that analysis, using assumptions that are closer to what we expect to see in practice and examines how EPD performs when the buffer is not large enough to achieve 100% goodput. We show that 100% goodput can be achieved …

Go to article

Continuous Compilation For Software Development And Mobile Computing, Michael P. Plezbert Jan 1996

Continuous Compilation For Software Development And Mobile Computing, Michael P. Plezbert

All Computer Science and Engineering Research

Software developers typically must choose between interpreted and compiled environments for their programming activities. However, the current trends toward mobile computing and platform independence suggest moving to a new continuous compilation paradigm that integrates the advantages of each environment. Movement in this direction can already be seen in the development of Sun Microsystems' Java environment. The resulting continuous compiler operates not as a prelude to, but rather in tandem with, program execution. In this thesis we present the results of experiments that compare the performance of the continuous compilation model with a more traditional model and show that a performance …

Go to article

Negotiation As A Resource Allocation Process, Fernando Tohme Jan 1996

Negotiation As A Resource Allocation Process, Fernando Tohme

All Computer Science and Engineering Research

The main economic-theoretic approcahes to the problem of resource allocation make little if any reference to negotiation processes. These processes are fundamentally linguistic, based on the exchange of messages among agents. Communication being so fundamental in the characterization of negotiation processes, the analysis of negotiation must emphasize on the structure of the language in which the negotiations take place. Computer science and particularly Artificial Intelligence have provided interesting insights about that linguistic structure. In the first part of this work we present a brief survey of the literature on resource allocation processes in which communication among agents plays a relevant …

Go to article

New Results On Generalized Caching, Saied Hosseini-Khayat Jan 1996

New Results On Generalized Caching, Saied Hosseini-Khayat

All Computer Science and Engineering Research

We report a number of new results in generalized caching. This problem arises in modern computer networks in which data objects of various sizes are transmitted frequently. First it is shown that its optimal solution is NP-complete. Then we explore two methods of obtaining nearly optimal answers based on the dynamic programming algorithm that we provided in [5]. These methods enable a trade-off between optimality and speed. It is also shown that LFD (the longest forward distance algorithm which is the optimal policy in the classical case), is no longer optimal but is competitive. We also prove that LRU remains …

Go to article

Building Distributed Applications With Design Patterns, Gruia-Catalin Roman, James C. Hu Jan 1996

Building Distributed Applications With Design Patterns, Gruia-Catalin Roman, James C. Hu

All Computer Science and Engineering Research

Design patterns are a topic of great current interest within the object-oriented programming community. The motivation is both economical and intellectual. On one hand, there is the hope of establishing a common culture and language that fosters communicatino and growth in the software engineering field. While a community dominated by empiricism is seeking to achieve higher levels of formality by capturing its experiences in the form of catalogs of design patterns, another community, deeply rooted in formal thinking, is seeking to make its mark on the every day workings of the software engineering process. Distributed algorithms and the heuristics used …

Go to article

Data Compression Based On The Cubic B-Spline Wavelet With Uniform Two-Scale Relation, S. K. Yang, C. H. Cooke Jan 1996

Data Compression Based On The Cubic B-Spline Wavelet With Uniform Two-Scale Relation, S. K. Yang, C. H. Cooke

Mathematics & Statistics Faculty Publications

The aim of this paper is to investigate the potential artificial compression which can be achieved using an interval multiresolution analysis based on a semiorthogonal cubic B-spline wavelet. The Chui-Quak [1] spline multiresolution analysis for the finite interval has been modified [2] so as to be characterized by natural spline projection and uniform two-scale relation. Strengths and weaknesses of the semiorthogonal wavelet as regards artificial compression and data smoothing by the method of thresholding wavelet coefficients are indicated.

Go to article

Customer Feedback Information System For Quality Improvement, Ke Wang Jan 1996

Customer Feedback Information System For Quality Improvement, Ke Wang

Masters Theses

This research addressed the basic needs for an effective customer feedback information system and the database technology to develop the system. It discussed the system concept and configuration of a typical customer feedback information system, database management technology, programming flow charts, program functions and capabilities. A proposed customer feedback information system consists of customer data inputs, database management system and outputs to various departments in an organization. With a user-friendly interface, database management system serves as an information management tool. It can process the feedback from customers and use the information in decision making. Thus, customer feedback can be promptly …

Go to article

Introduction To Multiprocessor I/O Architecture, David Kotz Jan 1996

Introduction To Multiprocessor I/O Architecture, David Kotz

Dartmouth Scholarship

The computational performance of multiprocessors continues to improve by leaps and bounds, fueled in part by rapid improvements in processor and interconnection technology. I/O performance thus becomes ever more critical, to avoid becoming the bottleneck of system performance. In this paper we provide an introduction to I/O architectural issues in multiprocessors, with a focus on disk subsystems. While we discuss examples from actual architectures and provide pointers to interesting research in the literature, we do not attempt to provide a comprehensive survey. We concentrate on a study of the architectural design issues, and the effects of different design alternatives.

Go to article

System For Synchronizing Execution By A Processing Element Of Threads Within A Process Using A State Indicator Us:5553305, Robert Iannucci, Steven Gregor Dec 1995

System For Synchronizing Execution By A Processing Element Of Threads Within A Process Using A State Indicator Us:5553305, Robert Iannucci, Steven Gregor

Robert A Iannucci

No abstract provided.

Go to article

How Can Software Reliability Engineering (Sre) Help System Engineers And Software Architects?, Robert Yacobellis Dec 1995

How Can Software Reliability Engineering (Sre) Help System Engineers And Software Architects?, Robert Yacobellis

Robert H Yacobellis

No abstract provided.

Go to article

Brain Activation Modulated By Sentence Comprehension, Marcel Adam Just, Patricia A. Carpenter, Timothy A. Keller, William F. Eddy, Keith R. Thulborn Dec 1995

Brain Activation Modulated By Sentence Comprehension, Marcel Adam Just, Patricia A. Carpenter, Timothy A. Keller, William F. Eddy, Keith R. Thulborn

Marcel Adam Just

No abstract provided.

Go to article

A Control Basis For Multilegged Walking, Manfred Huber, Willard S. Macdonald, Roderic Grupen Dec 1995

A Control Basis For Multilegged Walking, Manfred Huber, Willard S. Macdonald, Roderic Grupen

Roderic Grupen

This paper presents a distributed control approach to legged locomotion that constructs behavior on-line by activating combinations of reusable feedback control laws drawn from a control basis. Sequences of such controller activations result in flexible aperiodic step sequences based on local sensory information. Different tasks are achieved by varying the composition functions over the same basis controllers, rather than by geometric planning of leg placements or the design of new task-specific behaviors. In addition, the device-independent nature of the control basis allows its generalization not only over task domains, but also over different hardware platforms. To show the applicability of …

Go to article

Achieving Balance In Software Engineering Curricula, Tim Comber, Bruce Lo, Richard Watson Dec 1995

Achieving Balance In Software Engineering Curricula, Tim Comber, Bruce Lo, Richard Watson

Tim Comber

Achieving balance is an issue that faces all curriculum designers. The complexity of the software process demands a pluralistic approach to systems development. This pluralism must also be reflected in the education and training of future software engineers. How can we integrate the diverse views into a unified curriculum framework? How can we cover all topics that are deemed essential for the discipline. We must balance specialised software engineering topics with fundamental topics in computer science and we must also balance the variety of software engineering topics amongst themselves within the relatively short three-year undergraduate curriculum. Very often, what is …

Go to article

Information Engineering Facility (Ief) Computer Aided Software Engineering (Case) For Church Management System, Cynthia T. Dubose Dec 1995

Information Engineering Facility (Ief) Computer Aided Software Engineering (Case) For Church Management System, Cynthia T. Dubose

Electronic Dissertations and Theses

No abstract provided.

Go to article

Simulations Between Programs As Cellular Automata, Howard A. Blair, Fred Dushin, Polar Humenn Dec 1995

Simulations Between Programs As Cellular Automata, Howard A. Blair, Fred Dushin, Polar Humenn

Electrical Engineering and Computer Science - Technical Reports

We present cellular automata on appropriate digraphs and show that any covered normal logic program is a cellular automaton. Seeing programs as cellular automata shifts attention from classes of Herbrand models to orbits of Herbrand interpretations. Orbits capture both the declarative, model-theoretic meaning of programs as well as their inferential behavior. Logically and intentionally different programs can produce orbits that simulate each other. Simple examples of such behavior are compellingly exhibited with space-time diagrams of the programs as cellular automata. Construing a program as a cellular automaton leads to a general method for simulating any covered program with a Horn …

Go to article

First Prev Next Last