Search

Computer science (CS) is becoming an increasingly diverse domain. This paper reports on an initiative designed to introduce underrepresented populations to computing using an eclectic, multifaceted approach. As part of a yearlong computing course, students engage in Maker activities, participatory simulations, and computing projects that foreground the social and collaborative aspects of CS. Collectively, these activities are designed to introduce learners to the growing diversity of what CS looks like in the 21st century. This paper lays out the practical and theoretical motivations for the Computational Thinking for Girls (CT4G) project, specifically highlighting the use of Making through physical and social computing as ways to engage students in CS. A snapshot of one activity from the program is provided—Wearing the Web—in which students use open-hardware programmable badges to explore the underlying structure and technology that enables the Internet. Data from the first year of the CT4G program are presented to show the positive effects that this diverse introduction to CS is having on the students with respect to their attitudes toward CS. [ABSTRACT FROM PUBLISHER]

This paper explores the use of a constructivist 21st-century learning model to implement a week-long workshop, delivered as a “hackathon,” to encourage preuniversity teenagers to pursue careers in STEM, with a particular emphasis on computer science. For Irish preuniversity students, their experience of computing can vary from word processing to foundational programming, and while many schools are looking to introduce more ICT into the classroom, many students are left with a narrow view of what computer science is all about. Twenty-one students participated in the workshop and completed pre- and post-surveys, and a free word association exercise in the areas of computing and careers in computing. Analysis revealed that students’ motivation to learn about the design process, programming, inputs and outputs, and wearable technology (wearables)/Internet of Things (IoT) increased following participation. There were also increases in confidence in inputs and outputs and wearables/IoT following participation, as well as changes in the computing word associations, with students associating computing more with computer programming terms rather than general terms such as the Internet. The findings suggest that the combination of a hackathon event and a model for 21st century learning can be effective in motivating and increasing the self-efficacy of preuniversity teenagers in a number of emerging technological contexts such as IoT and wearables. [ABSTRACT FROM PUBLISHER]

The issue of plagiarism is discussed in the context of university education in disciplines related to computing. The focus is therefore mainly on software plagiarism. First, however, a case is made for the claim that the most important reason that plagiarism cannot be tolerated lies in the essence of the concept of a university as it is rooted in the Western cultural tradition. The main contribution of this paper is in providing firsthand insight into students' views on some of the delicate questions related to student plagiarism. However, this paper presents views from both sides of the question, including the views of staff members. This paper is quite unique in that it is coauthored by students who provide independent comments and recommendations. [ABSTRACT FROM PUBLISHER]

Low retention rates in third-level computing courses, despite continuing research into new and improved computer teaching methods, present a worrying concern. For some computing students learning programming is intimidating, giving rise to lack of confidence and anxiety. The noncognitive domain of anxiety with regard to learning computer programming is investigated in this paper and programming anxiety, a constituent component of computer anxiety, is defined. The paper describes a longitudinal research study that has been conducted, which investigates the variance of anxiety amongst undergraduate computing students, with specific emphasis upon their !earning programming during their first year in higher education. [ABSTRACT FROM AUTHOR]

In this paper, we first present an exploratory analysis of the aspects of multiple-version software diversity using 36,123 programs written to the same specification. We do so within the framework of the theories of Eckhardt and Lee and Littlewood and Miller. We analyze programming faults made, explore failure regions and difficulty functions, and show how effective 1-out-of-2 diversity is and how language diversity increases this effectiveness. The second part of this paper generalizes the findings about 1-out-of-2 diversity and its special case language diversity by performing statistical analyses of 89,402 programs written to 60 specifications. Most observations in the exploratory analysis are confirmed; however, although the benefit of language diversity can be observed, its effectiveness-appears to be low. [ABSTRACT FROM AUTHOR]

Given a distributed computation and a global predicate, predicate detection involves determining whether there exists at least one consistent cut (or global state) of the computation that satisfies the predicate. On the other hand, computation slicing is concerned with computing the smallest subcomputation (with the least number of consistent cuts) that contains all consistent cuts of the computation satisfying the predicate. In this paper, we investigate the relationship between predicate detection and computation slicing and show that the two problems are actually equivalent. Specifically, given an algorithm to detect a predicate b in a computation C, we derive an algorithm to compute the slice of C with respect to b. The time complexity of the (derived) slicing algorithm is O(n∣E∣T), where n is the number of processes, E is the set of events, and O(T) is the time complexity of the detection algorithm. We discuss how the "equivalence" result of this paper can be utilized to derive a faster algorithm for solving the genera/predicate detection problem in many cases. Slicing algorithms described in our earlier papers are all offline in nature. In this paper, we also present two online algorithms for computing the slice. The first algorithm can be used to compute the slice for a general predicate. Its amortized time complexity is O(n(c+n)T) per event, where c is the average concurrency in the computation and O(T) is the time complexity of the detection algorithm. The second algorithm can be used to compute the slice for a regular predicate. Its amortized time complexity is only O(n2) per event. [ABSTRACT FROM AUTHOR]

Emerging network technologies have complex network interfaces that have renewed concerns about network reliability. In this paper, we present an effective low-overhead fault tolerance technique to recover from network interface failures. Failure detection is based on a software watchdog timer that detects network processor hangs and a self-testing scheme that detects interface failures other than processor hangs. The proposed self-testing scheme achieves failure detection by periodically directing the control flow to go through only active software modules in order to detect errors that affect instructions in the local memory of the network interface. Our failure recovery is achieved by restoring the state of the network interface using a small backup copy containing just the right amount of information required for complete recovery. The paper shows how this technique can be made to minimize the performance impact to the host system and be completely transparent to the user. [ABSTRACT FROM AUTHOR]

Most weak memory consistency models are incapable of supporting a solution to mutual exclusion using only read and write operations to shared variables. Processor Consistency-Goodman's version (PC-G) is an exception. Ahamad et al. showed that Peterson's mutual exclusion algorithm is correct for PC-G, but Lamport's bakery algorithm is not. This paper derives a lower bound on the number of and type of (single or multiwriter) variables that a mutual exclusion algorithm must use in order to be correct for PC-G. Specifically, any such solution for n processes must use at least one multiwriter variable and n single-writer variables. Peterson's algorithm for two processes uses one multiwriter and two single-writer variables, and therefore establishes that this bound is tight for two processes. This paper presents a new n-process algorithm for mutual exclusion that is correct for PC-G and achieves the bound for any n. While Peterson's algorithm is fair, this extension to arbitrary n is not fair. Six known algorithms that use the same number and type of variables are shown to fail to guarantee mutual exclusion when the memory consistency model is only PC-G, as opposed to the Sequential Consistency model for which they were designed. A corollary of our investigation is that, in contrast to Sequential Consistency, multiwriter variables cannot be implemented from single-writer variables in a PC-G system. [ABSTRACT FROM AUTHOR]

This paper considers the role of run-time diagnostic checking in enforcing the rules of the Pascal programming language. Run- time diagnostic checks must be both complete (covering all language requirements) and efficient. Further, such checks should be implemented so that the cost of enforcing the correct use of a given construct is borne by users of that construct. This paper describes simple and efficient mechanisms currently in use with a diagnostic Pascal compiler that monitor the run-time behavior of such sensitive Pascal constructs as pointers, variant records, reference (i.e., vat) parameters, and with statements. The use of these mechanisms with related constructs in other languages is considered. Language modifications that simplify run-time checking are also noted. [ABSTRACT FROM AUTHOR]

In this paper we: 1) discuss the need for quantitatively reproducible experiments in the study of top-down design; 2) propose the design and writing of tutorial papers as a suitably general and in- expensive vehicle; 3) suggest the software science parameters as appropriate metrics; 4) report two experiments validating the use of these metrics on outlines and prose; and 5) demonstrate that the experiments tended toward the same optimal modularity. The last point appears to offer a quantitative approach to the estimation of the total length or volume (and the mental effort required to produce it) from an early stage of the top-down design process. If results of these experiments are validated elsewhere, then they will provide basic guidelines for the design process. [ABSTRACT FROM AUTHOR]

Embedded assertions have been recognized as a potentially powerful tool for automatic runtime detection of software faults during debugging, testing, maintenance and even production versions of software systems. Yet despite the richness of the notations and the maturity of the techniques and tools that have been developed for programming with assertions, assertions are a development tool that has seen little widespread use in practice. The main reasons seem to be that (1) previous assertion processing tools did not integrate easily with existing programming environments, and (2) it is not well understood what kinds of assertions are most effective at detecting software faults. This paper describes experience using an assertion processing tool that was built to address the concerns of ease-of-use and effectiveness. The tool is called APP, an Annotation PreProcessor for C programs developed in UNIX-based development environments. APP has been used in the development of a variety of software systems over the past five years. Based on this experience, the paper presents a classification of the assertions that were most effective at detecting faults. While the assertions that are described guard against many common kinds of faults and errors, the very commonness of such faults demonstrates the need for an explicit, high-level, automatically checkable specification of required behavior. It is hoped that the classification presented in this paper will prove to be a useful first step in developing a method of programming with assertions. [ABSTRACT FROM AUTHOR]

Computer science courses typically incorporate integrated training in software engineering, which includes learning how to reuse existing code libraries in new programs. This commonly presents a need to use the libraries' application programming interfaces (APIs) during project-based learning activities. The students learn these APIs with little support from the instructor. Instead, they primarily learn from whatever code examples they find on the Web—a scattershot approach that is slow, frustrating, and sometimes fruitless. Preliminary work investigated an improved approach that provides students with intelligent API tutors. This interactive educational content walks students through code examples selectively harvested from the Web. This approach increased students' knowledge of API method names, but a key pedagogical challenge remained: Students still lacked an understanding of common problems and surprises that they might encounter when using APIs in practice. Perhaps even more crucially, the prior statistical study provided no information about how students would perceive and accept the intelligent tutor approach, when given a choice. Therefore, this paper presents an enhanced approach that augments intelligent tutors with selected information from online FAQs and online open-source code, thereby providing more explanation and context about how to use APIs in practice. A qualitative study assessed student perceptions of the system's usability as well as suggestions for improvement, revealing that 100% of students considered the approach to be useful. A key implication is that providing information from online FAQs, related articles, and open-source code could facilitate computer science students' learning how to use APIs. [ABSTRACT FROM AUTHOR]

In testing from a Finite State Machine (FSM), the generation of test suites which guarantee full fault detection, known as complete test suites, has been a long-standing research topic. In this paper, we present conditions that are sufficient for a test suite to be complete. We demonstrate that the existing conditions are special cases of the proposed ones. An algorithm that checks whether a given test suite is complete is given. The experimental results show that the algorithm can be used for relatively large FSMs and test suites. [ABSTRACT FROM AUTHOR]

Hard real-time systems always choose not to use garbage collection in order to avoid its unpredictable executions. Much effort has been expended trying to build predictable garbage collectors which can provide both temporal and spatial guarantees. Unfortunately, most existing work leads to systems that cannot easily achieve a balance between temporal and spatial performances. Moreover, the scheduling of garbage collectors has not been integrated into modern real-time scheduling frameworks, which makes the benefits provided by the advancement of scheduling techniques very difficult to obtain. This paper argues that the existing design criteria for real-time garbage collectors do not reflect the unique requirements of flexible hard real-time systems. As a part of our design criteria, a new performance indicator is proposed to describe the capability of a real-time garbage collector to achieve a better balance between temporal and spatial performances. A hybrid garbage collection algorithm is designed accordingly which also uses dual priority scheduling algorithm to reclaim spare capacity while guaranteeing deadlines. [ABSTRACT FROM AUTHOR]

The article offers information on the planning of the course titled "TRACES-Themes Still Relevant At Current Software Engineering Studies." It is implied that the course's structure resembles that of a seminar which ventures on computer science. One of the aims of the course is inculcating the historical aspects of the discipline into a computer science or informatics curriculum. The course's design and structure are presented in details in the article. Topics of papers chosen for the course are also included in the article.

Laboratory work assignments are very important for computer science learning. Over the last 12 years many students have been involved in solving such assignments in the authors' department, having reached a figure of more than 400 students doing the same assignment in the same year. This number of students has required teachers to pay special attention to conceivable plagiarism cases. A plagiarism detection tool has been developed as part of a full toolset for helping in the management of the laboratory work assignments. This tool defines and uses four similarity criteria to measure how similar two assignment implementations are. The paper describes the plagiarism detection tool and the experience of using it over the last 12 years in four different programming assignments, from microprogramming a CPU to system programming in C. [ABSTRACT FROM AUTHOR]

A novel serial-in parallel-out finite field multiplier using redundant representation is proposed. It is shown that the proposed architecture has either a significantly lower complexity and comparable critical path delay or a significantly smaller critical path delay and comparable complexity in comparison to the previously proposed architectures using the same representation. For the class of fields where there exists a type I optimal normal basis, the proposed multiplier compares favorably to the normal basis multipliers. A digit-level version for the new multiplier is also presented in this paper. [ABSTRACT FROM AUTHOR]

UCS is a supervised learning classifier system that was introduced in 2003 for classification in data mining tasks. The representation of a rule in UCS as a univariate classification rule is straightforward for a human to understand. However, the system may require a large number of rules to cover the input space. Artificial neural networks (NNs), on the other hand, normally provide a more compact representation. However, it is not a straightforward task to understand the network. In this paper, we propose a novel way to incorporate NNs into UCS. The approach offers a good compromise between compactness, expressiveness, and accuracy. By using a simple artificial NN as the classifier's action, we obtain a more compact population size, better generalization, and the same or better accuracy while maintaining a reasonable level of expressiveness. We also apply negative correlation learning (NCL) during the training of the resultant NN ensemble. NCL is shown to improve the generalization of the ensemble. [ABSTRACT FROM AUTHOR]

Current artificial immune system (AIS) classifiers have two major problems: 1) their populations of B-cells can grow to huge proportions, and 2) optimizing one B-cell (part of the classifier) at a time does not necessarily guarantee that the B-cell pool (the whole classifier) will be optimized. In this paper, the design of a new AIS algorithm and classifier system called simple AIS is described. It is different from traditional AIS classifiers in that it takes only one B-cell, instead of a B-cell pool, to represent the classifier. This approach ensures global optimization of the whole system, and in addition, no population control mechanism is needed. The classifier was tested on seven benchmark data sets using different classification techniques and was found to be very competitive when compared to other classifiers. [ABSTRACT FROM AUTHOR]

The crossover operator has been considered "the centre of the storm" in genetic programming (GP). However, many existing GP approaches to object recognition suggest that the standard GP crossover is not sufficiently powerful in producing good child programs due to the totally random choice of the crossover points. To deal with this problem, this paper introduces an approach with a new crossover operator in GP for object recognition, particularly object classification. In this approach, a local hill-climbing search is used in constructing good building blocks, a weight called looseness is introduced to identify the good building blocks in individual programs, and the looseness values are used as heuristics in choosing appropriate crossover points to preserve good building blocks. This approach is examined and compared with the standard crossover operator and the head- less chicken crossover (HCC) method on a sequence of object classification problems. The results suggest that this approach outperforms the HCC, the standard crossover, and the standard crossover operator with hill climbing on all of these problems in terms of the classification accuracy. Although this approach spends a bit longer time than the standard crossover operator, it significantly improves the system efficiency over the HCC method. [ABSTRACT FROM AUTHOR]

An important conceptual modeling activity in the development of database, object-oriented and agent-oriented systems is the capture and expression of domain constraints governing underlying data and object states. UML is increasingly used for capturing conceptual models, as it supports conceptual modeling of arbitrary domains, and has extensible notation allowing capture of invariant constraints both in the class diagram notation and in the separately denoted OCL syntax. However, a need exists for increased formalism in constraint capture that does not sacrifice ease of use for the analyst. In this paper, we codify a set of invariant patterns formalized here for capturing a rich category of propositional constraints on class diagrams. We use tools of Boolean logic to set out the distinction between these patterns, applying them in modeling by way of example. We use graph notation to systematically uncover constraints hidden in the diagrams. We present data collected from applications across different domains, supporting the importance of "pattern-finding" for n-variable propositional constraints using general graph theoretic methods. This approach enriches UML-based conceptual modeling for greater completeness, consistency, and correctness by formalizing the syntax and semantics of these constraint patterns, which has not been done in a comprehensive manner before now. [ABSTRACT FROM AUTHOR]

The recent Maximum Weighted Likelihood (MWL) [18], [19] has provided a general learning paradigm for density-mixture model selection and learning, in which weight design, however, is a key issue. This paper will therefore explore such a design, and through which a heuristic extended Expectation-Maximization (X-EM) algorithm is presented accordingly. Unlike the EM algorithm [1], the X-EM algorithm is able to perform model selection by fading the redundant components out from a density mixture, meanwhile estimating the model parameters appropriately. The numerical simulations demonstrate the efficacy of our algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we present a bit-parallel multiplier for GF(2m) defined by an irreducible pentanomial ixm + xk3 + xk2 + xk1 + 1, where 1 ≤ k1 < k2 < k3 ≤ m/2. In order to design an efficient bit-parallel multiplier, we introduce a shifted polynomial basis and modify a reduction matrix presented by Reyhani-Masoleh and Hasan. As a result, the time complexity of the proposed multiplier is TA + (3 + [log2(m - 1)])Tx, where TA and Tx are the delay of one AND and one XOR gate, respectively. This result matches or outperforms the previously known results. On the other hand, the proposed multiplier has the same space complexity as the previously known multipliers except for special types of irreducible pentanomials. Note that its hardware architecture is similar to that presented by Reyhani-Masoleh and Hasan. [ABSTRACT FROM AUTHOR]

A Taylor Expansion Diagram (TED) is a compact, word-level, canonical representation for data flow computations that can be expressed as multivariate polynomials. TEDs are based on a decomposition scheme using Taylor series expansion that allows one to model word-level signals as algebraic symbols. This power of abstraction, combined with the canonicity and compactness of TED, makes it applicable to equivalence verification of dataflow designs. The paper describes the theory of TEDs and proves their canonicity. It shows how to construct a TED from an HDL design specification and discusses the application of TEDs in proving the equivalence of such designs. Experiments were performed with a variety of designs to observe the potential and limitations of TEDs for dataflow design verification. Application of TEDs to algorithmic and behavioral verification is demonstrated. [ABSTRACT FROM AUTHOR]

Design by contract is a lightweight technique for embedding elements of formal specification (such as invariants, pre and postconditions) into an object-oriented design. When Contracts are made executable, they can play the role of embedded, online oracles. Executable contracts allow components to be responsive to erroneous states and, thus, may help in detecting and locating faults. In this paper, we define Vigilance as the degree to which a program is able to detect an erroneous state at runtime. Diagnosability represents the effort needed to locate a fault once it has been detected. In order to estimate the benefit of using Design by Contract, we formalize both notions of Vigilance and Diagnosability as software quality measures. The main steps of measure elaboration are given, from informal definitions of the factors to be measured to the mathematical model of the measures. As is the standard in this domain, the parameters are then fixed through actual measures, based on a mutation analysis in our case. Several measures are presented that reveal and estimate the contribution of contracts to the overall quality of a system in terms of vigilance and diagnosability. [ABSTRACT FROM AUTHOR]

Given a user-specified minimum correlation threshold θ and a market-basket database with N items and T transactions, an all-strong-pairs correlation query finds all item pairs with correlations above the threshold θ. However, when the number of items and transactions are large, the computation cost of this query can be very high. The goal of this paper is to provide computationally efficient algorithms to answer the all-strong-pairs correlation query. Indeed, we identify an upper bound of Pearson's correlation coefficient for binary variables. This upper bound is not only much cheaper to compute than Pearson's correlation coefficient, but also exhibits special monotone properties which allow pruning of many item pairs even without computing their upper bounds. A Two-step All- strong-Pairs corElation queRy (TAPER) algorithm is proposed to exploit these properties in a filter-and-refine manner. Furthermore, we provide an algebraic cost model which shows that the computation savings from pruning is independent of or improves when the number of items is increased in data sets with Zipf-like or linear rank-support distributions. Experimental results from synthetic and real-world data sets exhibit similar trends and show that the TAPER algorithm can be an order of magnitude faster than brute-force alternatives. Finally, we demonstrate that the algorithmic ideas developed in the TAPER algorithm can be extended to efficiently compute negative correlation and uncentered Pearson's correlation coefficient. [ABSTRACT FROM AUTHOR]

This paper describes an experience of designing and implementing a portal to support transparent remote access to supercomputing facilities to students enrolled in an undergraduate parallel programming course. As these facilities are heterogeneous, are located at different sites, and belong to different institutions, grid computing technologies have been used to overcome these issues. The result is a grid portal based on a modular and easily extensible software architecture that provides a uniform and user-friendly interface for students to work on their programming laboratory assignments. [ABSTRACT FROM AUTHOR]

This paper describes two versions of a novel approach to developing binary classifiers, based on two evolutionary computation paradigms: cellular programming and genetic programming. Such an approach achieves high computation efficiency both during evolution and at runtime. Evolution speed is optimized by allowing multiple solutions to be computed in parallel. Runtime performance is optimized explicitly using parallel computation in the case of cellular programming or implicitly taking advantage of the intrinsic parallelism of bitwise operators on standard sequential architectures in the case of genetic programming. The approach was tested on a digit recognition problem and compared with a reference classifier. [ABSTRACT FROM AUTHOR]

This paper proposes a new method to model partially connected feed forward neural networks (PCFNNs) from the identified input type (IT) which refers to whether each input is coupled with or uncoupled from other inputs in generating output. The identification is done by analyzing input sensitivity changes as amplifying the magnitude of inputs. The sensitivity changes of the uncoupled inputs are not correlated with the variation on any, other input, while those of the coupled inputs are correlated with the variation on any one of the coupled inputs. According to the identified ITs, a PCFNN can be structured. Each uncoupled input does not share the neurons in the hidden layer with other inputs in order to contribute to output in an independent manner, while the coupled inputs share the neurons with one another. After deriving the mathematical input sensitivity analysis for each IT, several experiments, as well as a real example (blood pressure (BP) estimation), are described to demonstrate how well our method works. [ABSTRACT FROM AUTHOR]

This paper presents an asymmetric subset- hood-product fuzzy neural inference system (ASuPFuNIS) that directly extends the SuPFuNIS model [1] by permitting signal and weight fuzzy sets to be modeled by asymmetric Gaussian membership functions. The asymmetric subsethood-product network admits both numeric as well as linguistic inputs. Input nodes, which act as tunable feature fuzzifiers, fuzzify numeric inputs with asymmetric Gaussian fuzzy sets; and linguistic inputs are presented as is. The antecedent and consequent labels of standard fuzzy if-then rules are represented as asymmetric Gaussian fuzzy connection weights of the network. The model uses mutual subsethood based activation spread and a product aggregation operator that works in conjunction with volume defuzzification in a gradient descent learning framework. Despite the increase in the number of free parameters, the proposed model performs better than SuPFuNIS, on various benchmarking problems, both in terms of the performance accuracy and architectural economy and compares excellently with other various existing models with a performance better than most of them. [ABSTRACT FROM AUTHOR]

In this paper, we present an FP-like approach, named Class Point, which was conceived to estimate the size of object-oriented products. In particular, two measures are proposed, which are theoretically validated showing that they satisfy well-known properties necessary for size measures. An initial empirical validation is also performed, meant to assess the usefulness and effectiveness of the proposed measures to predict the development effort of object-oriented systems. Moreover, a comparative analysis is carried out, taking into account several other size measures. [ABSTRACT FROM AUTHOR]

Information Systems are situated in and are representations of some business or organizational domain. Hence, understanding the application domain is critical to the success of information systems development. To support domain understanding, the application domain is represented in conceptual models. The correctness of conceptual models can affect the development outcome and prevent costly rework during later development stages. This paper proposes a method to restrict the syntax of a modeling language to ensure that only possible configurations of a domain can be modeled, thus increasing the likelihood of creating correct domain models. The proposed method, based on domain ontologies, captures relationships among domain elements via constraints on the language metamodel, thus restricting the set of statements about the domain that can be generated with the language. In effect, this method creates domain specific modeling languages from more generic ones. The method is demonstrated using the Unified Modeling Language (UML). Specifically, it is applied to the subset of UML dealing with object behavior and its applicability is demonstrated on a specific modeling example. [ABSTRACT FROM AUTHOR]

In this paper, we develop a framework for reconfiguration of a discrete event system (DES) controller, which has a dynamic event observation set We will show the designed reconfiguration yields a more tolerable controller than the one designed in [5] Starting with a maximally permissive controller that has a full observation of its DES, we design a me ga-controller that monitors the observation set of the DES controller and its state continuously. Upon a change in the observation set, the mega-controller reconfigures the controller by a aggregation or disaggregation of the controller states. The mega-controller is also responsible for feedback function adjustments in the available observation set causes a conflict in control. We illustrate the reconfiguration procedures by an example. [ABSTRACT FROM AUTHOR]

A motivated student is more likely to be a successful learner. Interesting assignments encourage student learning by actively engaging them in the material. Active student learning is especially important in an introductory data structures course where students learn the fundamentals of programming. In this paper, the author describes a project for a data structures course based on the idea of competitive programming. Competitive programming motivates student learning by allowing students to evaluate and improve their programs throughout an assignment by competing their code against instructor-defined code and the code of other students in a tournament environment. Pedagogical results indicate that the combination of game development and friendly student competition is a significant motivator for increased student performance. [ABSTRACT FROM AUTHOR]

While empirical studies in software engineering are beginning to gain recognition in the research community, this subarea is also entering a new level of maturity by beginning to address the human aspects of software development. This added focus has added a new layer of complexity to an already challenging area of research. Along with new research questions, new research methods are needed to study nontechnical aspects of software engineering. In many other disciplines, qualitative research methods have been developed and are commonly used to handle the complexity of issues involving human behavior. This paper presents several qualitative methods for data collection and analysis and describes them in terms of how they might be incorporated into empirical studies of software engineering, in particular how they might be combined with quantitative methods. To illustrate this use of qualitative methods, examples from real software engineering studies are used throughout. [ABSTRACT FROM AUTHOR]

Although prior research has compared modeling performance using different systems development methods, there has been little research examining the comprehensibility of models generated by those methods. In this paper, we report the results of an empirical study comparing user comprehension of object-oriented (OO) and process-oriented (PO) models. The fundamental difference is that while OO models tend to focus on structure, PO models tend to emphasize behavior or processes. Proponents of the OO modeling approach argue that it lends itself naturally to the way humans think. However, evidence from research in cognitive psychology and human factors suggests that human problem solving is innately procedural. Given these conflicting viewpoints, we investigate empirically if OO models are in fact easier to understand than PO models. But, as suggested by the theory of cognitive fit, model comprehension may be influenced by task-specific characteristics. We, therefore, compare OO and PO models based on whether the comprehension activity involves: 1) only structural aspects, 2) only behavioral aspects, or 3) a combination of structural and behavioral aspects. We measure comprehension through subjects' responses to questions designed along these three dimensions. Two experiments were conducted, each with a different application and a different group of subjects. Each subject was first trained in both methods, and then participated in one of the two experiments, answering several questions relating to his or her comprehension of an OO or a PO model of a business application. The comprehension questions ranged in complexity from relatively simple (addressing either structural or behavioral aspects) to more complex ones (addressing both structural and behavioral aspects). Results show that for most of the simple questions, no significant difference was observed insofar as model comprehension is concerned. For most of the complex questions, however, the PO model was found to be easier to understand than the OO model. In addition to describing the process and the outcomes of the experiments, we present the experimental method employed as a viable approach for conducting research into various phenomena related to the efficacy of alternative systems analysis and design methods. We also identify areas where future research is necessary, along with a recommendation of appropriate research methods for empirical examination. [ABSTRACT FROM AUTHOR]

It is well known that algebraic specification methods are promising for specifying programs and for verifying their various properties formally. In this paper, an algebraic specification of information transfer procedures of high-level data link control (HDLC) procedures is presented and some of the main properties of the specification arc shown. First, we introduce abstract states, state transition functions, and output functions corresponding to elementary notions extracted from the description of HDLC procedures in ISO 3309-1979 (F) and ISO 4335-1979 (E). Second, we show axioms which represent the relations between the values of functions before and after the state transitions. Then, it is proved that the specification is "consistent," "sufficiently complete," and "nonredundant." Also it is shown that an implementation which realizes the specification is naturally derived. In the last section, verification of various properties of HDLC procedures is formulated in the same framework as the algebraic specification, and some verification examples are presented. [ABSTRACT FROM AUTHOR]

An experimental data flow analyzer for PL/I programs has been implemented within the PROBE system developed at the GM Research Laboratories. PROSE is an experimental software package that examines the internal structure of PL/I programs in order to expose error-prone design and programming features. This paper describes 1) the algorithms and data structures used by the data flow analyzer, 2) the salient aspects of PL/I usage in the analyzed production-level programs, and 3) the results of the data. flow analysis. [ABSTRACT FROM AUTHOR]

An abstract requirements specification states system requirements precisely without describing a real or a paradigm implementation. Although such specifications have important advantages, they are difficult to produce for complex systems and hence are seldom seen in the "real" programming world. This paper introduces an approach to producing abstract requirements specifications that applies to a significant class of real-world systems, including any system that must reconstruct data that have undergone a sequence of transformations. It also describes how the approach was used to produce a requirements document for SCP, a small, but nontrivial Navy communications system. The specification techniques used in the SCP requirements document are introduced and illustrated with examples. [ABSTRACT FROM AUTHOR]

The purpose of this paper is to develop a method for designing and verifying data abstractions using the functional approach. Before doing so, the existing techniques for designing and verifying procedure and data abstractions will be surveyed briefly. These techniques will then be modified and extended to verify data abstractions. By using the concept of a mathematical function, one can model the behavior of a procedure abstraction and give a more uniform and clearer meaning to the stepwise refinement and verification of procedure abstractions. The concept of a state machine is then used as a basis to specify data abstractions. Using state machine specification, a technique for expressing the design of a data abstraction is then given. A method is then developed to verify the design of a data abstraction with respect to its specifications. [ABSTRACT FROM AUTHOR]

The need for programming environments which support different phases of the software life cycle using responsive tools is well established. This paper presents a method for developing automatic analyzers which analyze programs and provide programmers with a variety of messages for the purpose of validating these programs in the early stages of program development. We show using an example, that such analyzers can be systematically constructed using an extension of the Attribute Grammar model which reflects the fact that a prop-am analyzer should perform a static analysis of the program as well as monitor its dynamic behavior efficiently. One of the advantages of the model is that a systematic interaction is allowed between the static and dynamic attributes of the program. We illustrate that an advantage of this interaction is selective program instrumentation. That is, the analyzer is responsive to the programmer's needs by providing a selective analysis of the program's behavior rather than an exhaustive analysis which is difficult to comprehend. [ABSTRACT FROM AUTHOR]

It is known that not all paths are possible in the run time control flow of many programs. It is also known that data flow analysis cannot restrict attention to exactly those paths that are possible. It is, therefore, usual for analytic methods to consider all paths. Sharper information can be obtained by considering a recursive set of paths that is large enough to include all possible paths, but small enough to exclude many of the impossible ones. This paper presents a simple uniform methodology for sharpening data flow information by considering certain recursive path sets of practical importance. Associated with each control flow arc there is a relation on a finite set C). The paths that qualify to be considered are (essentially) those for which the com- position of the relations encountered is nonempty. For example, Q might be the set of all assignments of values to each of several bit variables used by a program to remember some facts about the past and branch accordingly in the future. Given any data flow problem together with qualifying relations on Q associated with the control flow arcs, we construct a new problem. Considering all paths in the new problem is equivalent to considering only qualifying paths in the old one. Preliminary experiments (with a small set of real programs) Indicate that qualified analysis is feasible and substantially more informative than ordinary analysis. The methodology also ban beneficial feedback effect on the delicate task of passing from programs to meaningful data flow analysis problems. Even when all paths qualify, unusually sharp information can be obtained by passing from programs to problems in ways suggested by theorems proved here. [ABSTRACT FROM AUTHOR]

Modula is a new programming language for implementing dedicated, parallel systems. Following a systematic design technique, this paper illustrates the use of Modula for the design of a message switching communication system. A message switching system poses a number of interesting problems: a high degree of concurrent activity exists, a variety of I/O devices need to be controlled, messages can have multiple destinations, and messages can be preempted. The strengths and weaknesses of Modula with respect to these specific problems and its utility as a general purpose language are evaluated. [ABSTRACT FROM AUTHOR]

This paper discusses the problem of allocating storage for the activation records of procedure calls within a system of parallel processes. A compile time storage allocation scheme is given, which determines the relative address within the memory segment of a process for the activation records of all procedures called by the process. This facilitates the generation of an efficient run-time code. The allocation scheme applies to systems in which data and procedures can be shared among several processes. However, recursive procedure calls are not supported. [ABSTRACT FROM AUTHOR]

A method for formal description of programming principles is presented in this paper. Programming principles, such as sequential search can be defined and proven even in the absence of an application. We represent a principle as a program scheme which has partially interpreted functions in it. The functions must obey certain input constraints. Use of these ideas in program proving is illustrated with examples. [ABSTRACT FROM AUTHOR]

In this paper we introduce a general, extensible diagrammatic syntax for expressing software architectures based on typed nodes and connections and formalized using set theory. The syntax provides a notion of abstraction corresponding to the concept of a subsystem, and exploits this notion in a general mechanism for pattern matching over architectures. We demonstrate these ideas using a small example architecture language with a limited number of types of nodes and connectors, and a small taxonomy of architectures characterized as sets of patterns in the language. [ABSTRACT FROM AUTHOR]

As distributed configurations of high-powered workstations connected by networks become prevalent, tools for writing distributed programs take on increasing importance. This paper describes our experience implementing CES, a distributed Collaborative Editing System. CES was written in Argus, a language that was designed to support the construction of reliable distributed programs,and exhibits a number of requirements typical of distributed applications. Our experience illustrates numerous areas in which the support provided by Argus for meeting those requirements was quite helpful, but also identifies several areas in which the support provided by Argus was inadequate. Some of the problems arise because of the distinction in Argus (and in other systems) between locally and remotely accessible data and the mechanisms provided for implementing each. Others arise because of limitations of the mechanisms for building user-defined data types. We discuss the problems we encountered, including their implications for other systems. We also suggest solutions to the problems, or in some cases further research directed at finding solutions. [ABSTRACT FROM AUTHOR]

In this paper, we describe an approach for addressing the important problem of how long to test and debug software before it is released. Our approach is based on the principles of decision making under uncertainty, and involves a maximization of expected utility. We suggest two plausible forms for the utility function, one based on costs alone and the other involving the realized reliability of the software. Using results from the literature on probabilistic models for software failure, we outline, for the case of single state testing, the ensuing optimization problem which can be addressed using numerical techniques. The sensitivity of our results to the various input parameters is discussed and some directions for future research outlined. [ABSTRACT FROM AUTHOR]

An efficient digital search algorithm is presented in this paper by introducing a new internal array structure, called a double- array, that combines the fast access of a matrix form with the compactness of a list form. Each arc of a digital search tree, called a DS- tree, can be computed from the double-array in O(1) time; that is to say, the worst-case time complexity for retrieving a key becomes O(k) for the length k of that key. The double-array is modified to make the size compact while maintaining fast access and algorithms for retrieval, insertion and deletion are presented. Suppose that the size of the double-array is n + cm, n being the number of nodes of the DS-tree, m being the number of input symbols, and c a constant depending on each double-array. Then it is theoretically proved that the worst-case times of deletion and insertion are proportional to cm and cm², respectively, independent of ii. From the experimental results of building the double-array incrementally for various sets of keys, it is shown that the constant c has an extremely small value, ranging from 0.17 to 1.13. [ABSTRACT FROM AUTHOR]

An orphan in a distributed transaction system is an activity executing on behalf of an aborted transaction. Orphans are undesirable because they waste system resources and because they may observe inconsistent data. This paper proposes a new method for managing orphans created by crashes and by aborts. The method ensures that orphans are detected and eliminated in a timely manner, and it prevents them from observing inconsistent states. A major ad- vantage of this method is simplicity: it is easy to understand, to implement, and to prove correct. An "eager" version of this method uses approximately synchronized real-time clocks to ensure that orphans are eliminated within a fixed duration, and a "lazy" version uses logical clocks to ensure that orphans are eventually eliminated as information propagates through the system. The method is fail-safe: unsynchronized clocks and lost messages may affect performance, but they cannot produce inconsistencies or protect orphans from eventual elimination. [ABSTRACT FROM AUTHOR]