A survey on algorithmic debugging strategies

Algorithmic debugging is a debugging technique that has been extended to practically all programming paradigms. Roughly speaking, the technique constructs an internal representation of all (sub)computations performed during the execution of a buggy program; and then, it asks the programmer about the correctness of such computations. The answers of the programmer guide the search for the bug until it is isolated by discarding correct parts of the program. After twenty years of research in algorithmic debugging many different techniques have appeared to improve the original proposal. Surprisingly, no study exists that joins together all these techniques and compares their advantages and their performance. This article presents a study that compares all current algorithmic debugging techniques and analyzes their differences and their costs. The research identifies the dimensions on which each strategy relies. This information allows us to combine the strong points of different strategies.     

Theory blending: extended algorithmic aspects and examples

In Cognitive Science, conceptual blending has been proposed as an important cognitive mechanism that facilitates the creation of new concepts and ideas by constrained combination of available knowledge. It thereby provides a possible theoretical foundation for modeling high-level cognitive faculties such as the ability to understand, learn, and create new concepts and theories. Quite often the development of new mathematical theories and results is based on the combination of previously independent concepts, potentially even originating from distinct subareas of mathematics. Conceptual blending promises to offer a framework for modeling and re-creating this form of mathematical concept invention with computational means. This paper describes a logic-based framework which allows a formal treatment of theory blending (a subform of the general notion of conceptual blending with high relevance for applications in mathematics), discusses an interactive algorithm for blending within the framework, and provides several illustrating worked examples from mathematics.     

Tree decomposition and discrete optimization problems: A survey

The paper considers tree decomposition methods as applied to discrete optimization and presents relevant mathematical results. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 102–118, July–August 2007.     

Practical aspects of algorithmic solutions to gas pulsation problems of pipeline systems

Experiences gained in the field of program development for acoustic pressure and velocity pulsation calculation of reciprocating compressor pipeline systems are discussed. An interactive personal computer program package based on the acoustic plane wave model has been elaborated. Using graph and matrix interpretation of the system, tree-structure pipeline networks are handled by generalized algorithms which make it possible to realize pulsation calculations on two levels, with general logical operations of structure recognition being separated from structure dependent numerical calculations. Economical time and memory usage, as well as program structure and data flow design are detailed.     

A survey on benders decomposition applied to fixed-charge network design problems

Network design problems concern the selection of arcs in a graph in order to satisfy, at minimum cost, some flow requirements, usually expressed in the form of origin–destination pair demands. Benders decomposition methods, based on the idea of partition and delayed constraint generation, have been successfully applied to many of these problems. This article presents a review of these applications.     

Task decomposition and modular single-hidden-layer perceptron classifiers for multi-class learning problems

One of keys for multilayer perceptrons (MLPs) to solve the multi-class learning problems is how to make them get good convergence and generalization performances merely through learning small-scale subsets, i.e., a small part of the original larger-scale data sets. This paper first decomposes an n-class problem into n two-class problems, and then uses n class-modular MLPs to solve them one by one. A class-modular MLP is responsible for forming the decision boundaries of its represented class, and thus can be trained only by the samples from the represented class and some neighboring ones. When solving a two-class problem, an MLP has to face with such unfavorable situations as unbalanced training data, locally sparse and weak distribution regions, and open decision boundaries. One of solutions is that the samples from the minority classes or in the thin regions are virtually reinforced by suitable enlargement factors. And next, the effective range of an MLP is localized by a correction coefficient related to the distribution of its represented class. In brief, this paper focuses on the formation of economic learning subsets, the virtual balance of imbalanced training sets, and the localization of generalization regions of MLPs. The results for the letter and the extended handwritten digital recognitions show that the proposed methods are effective.     

LAR: A logic of algorithmic reasoning

Summary Reasoning about programs involves some logical framework which seems to go beyond classical predicate logic. LAR is an extension of predicate logic by additional concepts which are to formalize our natural reasoning about algorithms. Semantically, this extension introduces an underlying time scale on which formulas are considered and time shifting connectives. Besides a full model-theoretic treatment, a consistent and complete formal system for LAR is given. The pure logical system can serve as a basis for various theories. As an example, a theory of while program schemes is developed which contains Hoare's correctness proof system.     

Some aspects of standardising performance characteristics for modular data acquisition systems

To estimate the measurement uncertainty using a modular DAQ system, factors influencing the quality of A/D modules have to be determined. While integral and differential non-linearities describe the static quality of an ADC, the effective number of bits or SINAD are typical integral parameters characterising the dynamic quality of an A/D module. The paper analyses how individual disturbing factors and imperfections of the A/D module influence the quality of digitalisation, and how they could be specified for a future standardisation. It is shown that (in the case of a time-variable input signal) the factors mentioned above induce disturbing undesirable components in the digital output and so they influence the value of SINAD of the investigated A/D module.     

Security and privacy aspects in MapReduce on clouds: A survey

MapReduce is a programming system for distributed processing of large-scale data in an efficient and fault tolerant manner on a private, public, or hybrid cloud. MapReduce is extensively used daily around the world as an efficient distributed computation tool for a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and analysis of social networks. Security and privacy of data and MapReduce computations are essential concerns when a MapReduce computation is executed in public or hybrid clouds. In order to execute a MapReduce job in public and hybrid clouds, authentication of mappers–reducers, confidentiality of data-computations, integrity of data-computations, and correctness–freshness of the outputs are required. Satisfying these requirements shields the operation from several types of attacks on data and MapReduce computations. In this paper, we investigate and discuss security and privacy challenges and requirements, considering a variety of adversarial capabilities, and characteristics in the scope of MapReduce. We also provide a review of existing security and privacy protocols for MapReduce and discuss their overhead issues.     

Algebraic, topological and categorical aspects of pattern recognition: A survey

Mathematical foundations of pattern recognition are considered here. After presenting a sketch of algebraic syntactic and of topological approaches, we propose a unifying categorical formalism. Special attention is given to skeletons, and several theorems are stated.     

A series of algorithmic results related to the iterated hairpin completion

In this paper we propose efficient algorithmic solutions for the computation of the hairpin completion distance between two given words, for the computation of a minimum-distance common hairpin completion ancestor of two given words (i.e., a word from which we can obtain the two given words by iterated hairpin completion, such that the sum of the hairpin completion distances from this word to the two given words is minimum), and, respectively, for the computation of an arbitrary hairpin completion ancestor of two given words. In all the cases we improve the upper bounds known for time complexity of solving these problems. Then we show how the algorithms designed for these three initial problems can be modified to solve a series of related problems.     

Combinatorial and computational aspects of graph packing and graph decomposition

Packing and decomposition of combinatorial objects such as graphs, digraphs, and hypergraphs by smaller objects are central problems in combinatorics and combinatorial optimization. Their study combines probabilistic, combinatorial, and algebraic methods. In addition to being among the most fascinating purely combinatorial problems, they are often motivated by algorithmic applications. There is a considerable number of intriguing fundamental problems and results in this area, and the goal of this paper is to survey the state-of-the-art.     

Unified Approach for Developing EfficientAlgorithmic Programs

A unified approach called partition-and-recur for developing efficient and correct algorithmic programs is presented.An algorithm(represented by recurrence and initiation)is separated from program,and special attention is paid to algorithm manipulation rather than proram calculus.An algorithm is exactly a set of mathematical formulae.It is easier for formal erivation and proof.After getting efficient and correct algorithm,a trivial transformation is used to get a final rogram,The approach covers several known algorithm design techniques,e.g.dynamic programming,greedy,divide-and-conquer and enumeration,etc.The techniques of partition and recurrence are not new.Partition is a general approach for dealing with complicated objects and is typically used in divide-and-conquer approach.Recurrence is used in algorithm analysis,in developing loop invariants and dynamic programming approach.The main contribution is combining two techniques used in typical algorithm development into a unified and systematic approach to develop general efficient algorithmic programs and presenting a new representation of algorithm that is easier for understanding and demonstrating the correctness and ingenuity of algorithmicprograms.     

A modular systolic linearization of the Warshall-Floyd algorithm

In this paper, we use a variant of the geometric method to derive efficient modular linear systolic algorithms for the transitive closure and shortest path problems. Furthermore, we show that partially-pipelined modular linear systolic algorithms with an output operation, for matrix multiplication, can be as fast as the fully-pipelined existing ones and, moreover, they need less cells     

A hybrid algorithmic model for the minimum weight dominating set problem

Iterated greedy algorithms belong to the class of stochastic local search methods. They are based on the simple and effective principle of generating a sequence of solutions by iterating over a constructive greedy heuristic using destruction and construction phases. This paper, first, presents an efficient randomized iterated greedy approach for the minimum weight dominating set problem, where—given a vertex-weighted graph—the goal is to identify a subset of the graphs’ vertices with minimum total weight such that each vertex of the graph is either in the subset or has a neighbor in the subset. Our proposed approach works on a population of solutions rather than on a single one. Moreover, it is based on a fast randomized construction procedure making use of two different greedy heuristics. Secondly, we present a hybrid algorithmic model in which the proposed iterated greedy algorithm is combined with the mathematical programming solver CPLEX. In particular, we improve the best solution provided by the iterated greedy algorithm with the solution polishing feature of CPLEX. The simulation results obtained on a widely used set of benchmark instances shows that our proposed algorithms outperform current state-of-the-art approaches.     

Surrogate-assisted reliability-based design optimization: a survey and a unified modular framework

Structural and Multidisciplinary Optimization - Reliability-based design optimization (RBDO) is an active field of research with an ever increasing number of contributions. Numerous methods have...     

A survey of smart product-service systems: Key aspects,challenges and future perspectives

The rapid development of information and communication technologies (ICT) has enabled the prevailing digital transformation (i.e. digitalization), where physical products can be readily digitized in the virtual space and seamlessly interconnected. Meanwhile, industries are ever increasingly adopting service business models (i.e. servitization), so as to offer not only physical products but also services as a solution bundle to meet individual customer needs. Such convergence of both digitalization and servitization (i.e. digital servitization) has triggered an emerging IT-driven business paradigm, smart product-service systems (Smart PSS). As a novel paradigm coined in 2014, to the authors’ knowledge, only 2 conference papers have provided some literature review to date, and many issues remain uncovered or not comprehensively investigated. Aiming to fill this gap, this paper has conducted a systematic review of Smart PSS or related papers published ever since its first brought up to date (30/06/2019), and selected 97 representative items together with other 37 supplementary works to summarize the tendency towards Smart PSS, its business and technical aspects, current challenges, and future perspectives. From the survey, it is found that several hybrid concerns are the key challenges faced, and self-adaptiveness with sustainability, advanced IT infrastructure, human-centric perspectives, and circular lifecycle management are the core future perspectives to explore. It is hoped that this work can attract more open discussions and provide useful insights to both academics and industries in their exploration and implementation of Smart PSS.     

AnO(n 2) incremental algorithm for modular decomposition of graphs and 2-structures

This paper gives anO(n ²) incremental algorithm for computing the modular decomposition of 2-structures [1], [2]. A 2-structure is a type of edge-colored graph, and its modular decomposition is also known as the prime tree family. Modular decomposition of 2-structures arises in the study of relational systems. The modular decomposition of undirected graphs and digraphs is a special case, and has applications in a number of combinatorial optimization problems. This algorithm generalizes elements of a previousO(n ²) algorithm of Muller and Spinrad [3] for the decomposition of undirected graphs. However, Muller and Spinrad's algorithm employs a sophisticated data structure that impedes its generalization to digraphs and 2-structures, and limits its practical use. We replace this data structure with a scheme that labels each edge with at most one node, thereby obtaining an algorithm that is both practical and general to 2-structures.