Sorting by Short Block-Moves

Sorting permutations by operations such as reversals and block-moves has received much interest because of its applications in the study of genome rearrangements and in the design of interconnection networks. A short block-move is an operation on a permutation that moves an element at most two positions away from its original position. This paper investigates the problem of finding a minimum-length sorting sequence of short block-moves for a given permutation. A 4/3 -approximation algorithm for this problem is presented. Woven double-strip permutations are defined and a polynomial-time algorithm for this class of permutations is devised that employs graph matching techniques. A linear-time maximum matching algorithm for a special class of grid graphs improves the time complexity of the algorithm for woven double-strip permutations. Received June 1, 1997; revised July 25, 1998.     

A Framework for Providing User Level Quality of Service Guarantees in Multi-Class Rate Adaptive Systems

The problem of channel sharing by rate adaptive streams belonging to various classes is considered. Rate adaptation provides the opportunity for accepting more connections by adapting the bandwidth of connections that are already in the system. However, bandwidth adaptation must be employed in a careful manner in order to ensure that (a) bandwidth is allocated to various classes in a fair manner (system perspective) and (b) bandwidth adaptation does not affect adversely the perceived user quality of the connection (user quality). The system perspective aspect has been studied earlier. This paper focuses on the equally important user perspective. It is proposed to quantify user Quality of Service (QoS) through measures capturing short and long-term bandwidth fluctuations that can be implemented with the mechanisms of traffic regulators, widely used in networking for the purpose of controlling the traffic entering or exiting a network node. Furthermore, it is indicated how to integrate the user perspective metrics with the optimal algorithms for system performance metrics developed earlier by the authors. Simulation results illustrate the effectiveness of the proposed framework.

Empirical validation of referential integrity metrics

Databases are the core of Information Systems (IS). It is, therefore, necessary to ensure the quality of the databases in order to ensure the quality of the IS. Metrics are useful mechanisms for controlling database quality. This paper presents two metrics related to referential integrity, number of foreign keys (NFK) and depth of the referential tree (DRT) for controlling the quality of a relational database. However, to ascertain the practical utility of the metrics, experimental validation is necessary. This validation can be carried out through controlled experiments or through case studies. The controlled experiments must also be replicated in order to obtain firm conclusions. With this objective in mind, we have undertaken different empirical work with metrics for relational databases. As a part of this empirical work, we have conducted a case study with some metrics for relational databases and a controlled experiment with two metrics presented in this paper. The detailed experiment described in this paper is a replication of the later one. The experiment was replicated in order to confirm the results obtained from the first experiment.

As a result of all the experimental works, we can conclude that the NFK metric is a good indicator of relational database complexity. However, we cannot draw such firm conclusions regarding the DRT metric.     

Gaining Confidence in Software Inspection Using a Bayesian Belief Model

In this paper I describe how confidence in a software inspection can be obtained through calculating an estimate of its effectiveness. The method uses a Bayesian Belief Network to model the software inspection process and calculates the inference on how effective a particular inspection was. This technique was selected as it provides a means of initialising the model with inspectors' experience and has the ability to learn and optimise performance. This technique provides answers to some of the questions and limitations raised by current models used to predict inspection effectiveness. The application of the model to a major software project is discussed, covering the initial practitioner survey, model initialisation, model calibration and verification results obtained.     

Factors affecting user performance in haptic assembly

Current computer-aided assembly systems provide engineers with a variety of spatial snapping and alignment techniques for interactively defining the positions and attachments of components. With the advent of haptics and its integration into virtual assembly systems, users now have the potential advantage of tactile information. This paper reports research that aims to quantify how the provision of haptic feedback in an assembly system can affect user performance. To investigate human–computer interaction processes in assembly modeling, performance of a peg-in-hole manipulation was studied to determine the extent to which haptics and stereovision may impact on task completion time. The results support two important conclusions: first, it is apparent that small (i.e. visually insignificant) assembly features (e.g. chamfers) affect the overall task completion at times only when haptic feedback is provided; and second, that the difference is approximately similar to the values reported for equivalent real world peg-in-hole assembly tasks.     

Subjective evaluation of software evolvability using code smells: An empirical study

This paper presents the results of an empirical study on the subjective evaluation of code smells that identify poorly evolvable structures in software. We propose use of the term software evolvability to describe the ease of further developing a piece of software and outline the research area based on four different viewpoints. Furthermore, we describe the differences between human evaluations and automatic program analysis based on software evolvability metrics. The empirical component is based on a case study in a Finnish software product company, in which we studied two topics. First, we looked at the effect of the evaluator when subjectively evaluating the existence of smells in code modules. We found that the use of smells for code evaluation purposes can be difficult due to conflicting perceptions of different evaluators. However, the demographics of the evaluators partly explain the variation. Second, we applied selected source code metrics for identifying four smells and compared these results to the subjective evaluations. The metrics based on automatic program analysis and the human-based smell evaluations did not fully correlate. Based upon our results, we suggest that organizations should make decisions regarding software evolvability improvement based on a combination of subjective evaluations and code metrics. Due to the limitations of the study we also recognize the need for conducting more refined studies and experiments in the area of software evolvability.

One-dimensional and multi-dimensional substring selectivity estimation

With the increasing importance of XML, LDAP directories, and text-based information sources on the Internet, there is an ever-greater need to evaluate queries involving (sub)string matching. In many cases, matches need to be on multiple attributes/dimensions, with correlations between the multiple dimensions. Effective query optimization in this context requires good selectivity estimates. In this paper, we use pruned count-suffix trees (PSTs) as the basic data structure for substring selectivity estimation. For the 1-D problem, we present a novel technique called MO (Maximal Overlap). We then develop and analyze two 1-D estimation algorithms, MOC and MOLC, based on MO and a constraint-based characterization of all possible completions of a given PST. For the k-D problem, we first generalize PSTs to multiple dimensions and develop a space- and time-efficient probabilistic algorithm to construct k-D PSTs directly. We then show how to extend MO to multiple dimensions. Finally, we demonstrate, both analytically and experimentally, that MO is both practical and substantially superior to competing algorithms. Received April 28, 2000 / Accepted July 11, 2000     

Balancing Misclassification Rates in Classification-Tree Models of Software Quality

Software product and process metrics can be useful predictorsof which modules are likely to have faults during operations.Developers and managers can use such predictions by softwarequality models to focus enhancement efforts before release.However, in practice, software quality modeling methods in theliterature may not produce a useful balance between the two kindsof misclassification rates, especially when there are few faultymodules.This paper presents a practical classificationrule in the context of classification tree models that allowsappropriate emphasis on each type of misclassification accordingto the needs of the project. This is especially important whenthe faulty modules are rare.An industrial case study using classification trees, illustrates the tradeoffs.The trees were built using the TREEDISC algorithm whichis a refinement of the CHAID algorithm. We examinedtwo releases of a very large telecommunications system, and builtmodels suited to two points in the development life cycle: theend of coding and the end of beta testing. Both trees had onlyfive significant predictors, out of 28 and 42 candidates, respectively.We interpreted the structure of the classification trees, andwe found the models had useful accuracy.     

3-硝基吡唑的合成

以吡唑为原料，经硝化、转位两步反应合成了3-硝基吡唑、吡唑在硝酸-硫酸介质中硝化，反应温度不超过15℃，反应3．5小时得到N-硝基吡唑，收率为86．6％，再将N-硝基吡唑溶于正辛醇中在185℃-190℃加热回流，得到转位产物3-硝基吡唑，收率为87．8％。硝化反应的创新处是用硫酸代替醋酸和醋酐，作为溶剂的正辛醇可不经处理循环使用。