WinWin is a system that aids in the capture and recording of system requirements. It also assists in negotiation. The WinWin system has been available for several years and is being used by dozens of software development groups. In this presentation we go over the capabilities of the system and discuss how it might be used on your software development project.

The current trend of constructing new systems from collections of pre-existing third-party software and commercial off-the-shelf (COTS) products presents serious challenges to existing integration technology. We present a flexible integration framework which has general applicability for pre-existing third-party and COTS software (often highly interactive, with graphical user interface, and without source code access), supports users by allowing them to easily change the way software interacts (thus supporting system evolution and component reusability), and is easily programmable by end-users. Specifically we describe the Tool Integration Language (TIL) and the Tool Integration Server System (TISS) which provide flexible integration mechanisms for our framework and show how they can be used to integrate a set of existing applications and COTS.

A major problem in requirements engineering is obtaining requirements that address the concerns of multiplestakeholders.An approach to such a problem is the Theory-W based Spiral Model.This paper focuses on the problem of developing a support system for such a model.In particular

No abstract available.

An investigation is presented of the relationship between external inputs and the demands imposed on the various resources in advanced sensor systems. This reveals the deficiency of the classical execution model for hard real-time systems, consisting of periodic and sporadic tasks, for modeling the workload in such systems. The classical model is extended with additional attributes for describing the behavior of tasks and with another type of task, adaptive tasks, which are repetitive but not strictly periodic. Notation is presented for specification of computational activities and the dynamic behavior of software in such systems. Also proposed is a multilevel scheduling structure for scheduling system resources (e.g. processors, sensors, and memory).>

Cbase 1.0 is a multilayered system which provides a common repository of both VLSI objects and their associated operations, a tool interface for writing new applications, and a user interface for invoking applications or viewing objects in the database. Preliminary experience indicates that using an object-oriented database provides features such as specialization/generalization, property and operation inheritance, and polymorphism among object types which are useful for modeling the hierarchical nature and multiple views of a circuit. >

This paper describes the data abstraction mechanisms used in SODOS (Software Documentation Support), a computerized system which supports the definition and manipulation of documents used in developing software. Our purpose is to show the generic definition of a document, to define precisely the operations of consistency, completeness, and traceability, and finally to show how the generic document and associated operations are mapped onto the relational model. The SODOS system differs from others in that it is built on top of a database management system (DBMS) and an object-based model of the Software Life Cycle (SLC). One advantage of this model is that it supports software documentation independent of any fixed methodology that the developers may be using. Another advantage of the system is that it permits traceability through all phases of the Software Life Cycle, thus facilitating the testing and maintenance phases. In this paper we define the document representation in terms of a graph model mapped into a relational data model.

A description is given of a computerized environment, SODOS (Software Documentation Support), which supports the definition and manipulation of documents used in developing software. An object-oriented environment is used as a basis for the SODOS interface. SODOS is built around a software life-cycle model that structures all access to the documents stored in the environment. This model supports software documentation independently of any fixed methodology that the developers may be using. The main advantage of the system is that it permits traceability through each phase of the life cycle, thus facilitating the test and maintenance phases. The effort involved in learning and using SODOS is simplified by a sophisticated, user-friendly interface.

Abstract The concepts of process and guarded command have become the basic building blocks in concurrent programming language design. In this paper we deal with many of the proposed communication and synchronization primitives and we compare them from the perspective of their implementability. Our evaluation treats four basic criteria: the length of synchronization, process termination, deadlock and protocol complexity.

The trie data structure has many properties which make it especially attractive for representing large files of data. These properties include fast retrieval time, quick unsuccessful search determination, and finding the longest match to a given identifier. The main drawback is the space requirement. In this paper the concept of trie compaction is formalized. An exact algorithm for optimal trie compaction and three algorithms for approximate trie compaction are given, and an analysis of the three algorithms is done. The analysis indicate that for actual tries, reductions of around 70 percent in the space required by the uncompacted trie can be expected. The quality of the compaction is shown to be insensitive to the number of nodes, while a more relevant parameter is the alphabet size of the key.

The present crisis in software development forces us to reconsider the fundamental ways in which programming is done. One often quoted solution is to exploit more fully the idea of reusable software. It is the purpose of this paper to examine this concept in all of its forms and to assess the current state of the art. In addition to its usual meaning of reusable code, reusability includes reusable design, various forms of specification systems. so-called application generators, and systems for prototyping. We examine each approach from the perspective of the practicing engineer, and we evaluate the work in terms of how it may ultimately improve the development process for large-scale software systems.

The well known divide-and-conquer paradigm has proved to be useful for deriving efficient algorithms for many problems. Several researchers have pointed out its usefulness for parallel processing; however, the problem of analyzing such parallel algorithms in a realistic setting has been largely overlooked. In this paper a realistic model for divide-and-conquer based algorithms is postulated; the efficiency of some algorithms is then analyzed, taking into account all relevant parameters of the model (time, data movement and number of processors.)

The binary tree is a natural way to organize complex computations by a computer. For problems that can be naturally divided into a tree structure, a great deal of parallelism may be employed. In this paper we examine several aspects of the binary tree structure as it relates to both multiprocessor systems and to VISI circuit design. First, we present an algorithm for mapping an arbitrary binary tree onto the plane. An analysis shows the density of this mapping. Second, we consider the problem of routing messages within a binary tree under the assumption that certain nodes may be faulty. Finally, we analyze the binary tree's capacity to transfer information between nodes and we compare it to the capacity of the linear array and the grid.

Exact and approximate algorithms are presented for scheduling independent tasks in a multiprocessor environment in which the processors have different speeds. Dynamic programming type algorithms are presented which minimize finish time and weighted mean flow time on two processors. The generalization to m processors is direct. These algorithms have a worst-case complexity which is exponential in the number of tasks. Therefore approximation algorithms of low polynomial complexity are also obtained for the above problems. These algorithms are guaranteed to obtain solutions that are close to the optimal. For the case of minimizing mean flow time on m -processors an algorithm is given whose complexity is O( n log mn ).

ABS'rRACT Given two polynomials with n nonzero terms and t terms in the product, 2n -1 < t < n 2, it Is shown that the conventmnal polynomml multiphcatmn algorithm can take as many as ~9(n 3) operations.An alternate algorithm which does a binary merge-sort is given which has a worst-case bound of 0(n~log~n) exponent comparisons but may require 0(n *) storage A new algorithm, based upon a sorting strategy for the exponents, is given which behaves as O(n21og2n) and requires only ~)(t) storage Moreover, the algorithm works in hnear time for several Important special cases, namely for completely dense and completely sparse polynommls KEY "WORDS AND PHRASES polynomml multiphcation, sparse polynomml multiplication, sorting, tableau sorting CR ('ATEGORI~S" 5 25, 5 31, 5 7 1.Introductwn Suppose that we have two polynomials of degrees n -1, m -1, respectively,an-1 ~ O, andand we are interested in algorithms for computing their product.A and B above constitute the usual model for which multiplication algorithms have been analyzed.This model naturally yields bounds which are a function of the two degrees.For example, the classical pencil and paper multiplication method apphed to A and B takes 0(rnn) arithmetic operations But one must draw the distinction between polynomials as above and more generally ~n and ~ term polynomials.We will see later that the classical multiplication algorithm applied to polynomials of this latter type does not take O(mn) but O(m2n) arithmetic operations.From an asymptotic viewpoint there are better methods for multiplication.The current best relies on the use of the discrete fast Fourier transform and its convolution property (see Knuth [5, p. 269]).The time for this method is ~9(m log2m) assuming m ~_ n.However, this method is entirely insensitive to sparsity.This is clear from its first step, which is to consider the coefficients of A and B as elements of a k-tuple where k is the smallest power of 2 greater than or equal to m ..{-n -1.After the transform is applied all of the resulting elements will, in general, become nonzero.For polynomials as given above where all or most of the a,, b, are nonzero this technique can be quite effective.However, it will suffer badly when nn and n are large, but many of the coefficients are zero.For a system which is a general polynomial manipulator it makes sense to represent only the nonzero coefficients, and this is precisely what is done in almost all instances.This

The problem of computing the determinant of a matrix of polynomials is considered.Four algorithms are compared-expansion by minors, Gausslan elimination over the integers, a method based on evaluation and interpolation, and a procedure which computes the characteristic polynomial of the matrix.Each method m analyzed with respect to its computing time and storage requirements using several models for polynomial growth.First, the asymptotic time and storage is developed for each method within each model.In addition to these asymptotm results, the analysis is done exactly for certain especially small, yet practical and important cases Then the results of empirical studies are given which support conclusions about which of the methods will work best within an actual computing environment.ca CATEGOalES" 5.14, 5.25

Recent results on the computation of powers of symbolic polynomials are reviewed in perspective. Then a new algorithm is given which computes the nth power of a completely sparse polynomial using a linear number of multiplications. This is followed by experimental results comparing the new algorithm to iteration using both completely sparse and completely dense polynomials as data.

Given r numbers s 1 , …, s r , algorithms are investigated for finding all possible combinations of these numbers which sum to M . This problem is a particular instance of the 0-1 unidimensional knapsack problem. All of the usual algorithms for this problem are investigated in terms of both asymptotic computing times and storage requirements, as well as average computing times. We develop a technique which improves all of the dynamic programming methods by a square root factor. Empirical studies indicate this new algorithm to be generally superior to all previously known algorithms. We then show how this improvement can be incorporated into the more general 0-1 knapsack problem obtaining a square root improvement in the asymptotic behavior. A new branch and search algorithm that is significantly faster than the Greenberg and Hegerich algorithm is also presented. The results of extensive empirical studies comparing these knapsack algorithms are given

Since their inception some 25 years ago, computers have become an all pervasive influence in society. Their impact has been felt not only in the sciences and social sciences, but in almost all fields of endeavor where there is a significant amount of information to be taken, stored and manipulated. Their use in the many spheres of business activity has contributed to the creation of a huge computer industry. In recognition of the immense social influences of computers and the concurrent influence of the technocrats who “control” the machines, computer science departments have recently tried to respond to the challenge by giving their students an awareness of these forces. Their response has taken basically 2 forms. The first approach has been to incorporate within existing courses a measure of social awareness and responsibility. This has been accomplished by examining, where appropriate case situations of computer related developments and trying to assess their implications in the social context. Experiments of this type have been reported by [NEI72]. The second approach has been to create a new course, often called Computers and Society, whose main goal is to expose the student to at least a subset of the relevant issues connected with computers. Though called by the same name, these courses often vary widely, and several proposals which describe various formats have appeared in the literature e.g. see [HOR72] and [LEE71]. This paper deals with a variation on this second approach.

Despite recent advances in speeding up many arithmetic and algebraic algorithms plus a general increase in algorithm analyses, no computing time study has ever been done for algorithms which perform the rational function arithmetic operations. Mathematical symbol manipulation systems which provide for operations on rational functions use algorithms which were initially given by P. Henrici in 1956. In this paper, these algorithms are precisely specified and their computing times analyzed. Then, new algorithms based on the use of modular arithmetic are developed and analyzed. It is shown that the computing time for adding and taking the derivative of rational functions is 2 orders of magnitude faster using the modular algorithms. Also, the computing time for rational function multiplication will be one order of magnitude faster using the modular algorithm.