Note on the Structure of Kruskal’s Algorithm

We study the merging process when Kruskal’s algorithm is run with random graphs as inputs. Our aim is to analyze this process when the underlying graph is the complete graph on n vertices lying in [0,1] ^d , and edge set weighted with the Euclidean distance. The height of the binary tree explaining the merging process is proved to be Θ(n) on average. On the way to the proof, we obtain similar results for the complete graph and the d-dimensional square lattice with i.i.d. edge weights.     

A survey of recursive analysis and Moore’s notion of real computation

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore’s class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230–265, 1936), Grzegorczyk (Fundam Math 42:168–202, 1955), and Lacombe (Compt Rend l’Acad Sci Paris 241:151–153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore’s class and the relationships between them.     

Is Grover’s Algorithm a Quantum Hidden Subgroup Algorithm?

The arguments given in this paper suggest that Grover’s and Shor’s algorithms are more closely related than one might at first expect. Specifically, we show that Grover’s algorithm can be viewed as a quantum algorithm which solves a non-abelian hidden subgroup problem (HSP). But we then go on to show that the standard non-abelian quantum hidden subgroup (QHS) algorithm can not find a solution to this particular HSP. This leaves open the question as to whether or not there is some modification of the standard non-abelian QHS algorithm which is equivalent to Grover’s algorithm.      

Orthogonal Algorithm of Logic Probability and Syndrome-Testable Analysis

A new method,orthogonal algoritm,is presented to compute the logic probabilities(i.e.signal probabilities)accurately,The transfer properties of logic probabilities are studied first,which are useful for the calculation of logic probability of the circuit with random independent inputs.Then the orthogonal algoritm is described to compute the logic probability of Boolean function realized by a combinational circuit.This algorithm can make Boolean function “ORTHOGONAL”so that the logic probabilities can be easily calculated by summing up the logic probabilities of all orthogonal terms of the Booleam function.     

Analysis of YouTube’s traffic adaptation to dynamic environments

The popular Internet service, YouTube, has adopted by default the HyperText Markup Language version 5 (HTML5). With this adoption, YouTube has moved to Dynamic Adaptive Streaming over HTTP (DASH) as Adaptive BitRate (ABR) video streaming technology. Furthermore, rate adaptation in DASH is solely receiver-driven. This issue motivates this work to make a deep analysis of YouTube’s particular DASH implementation. Firstly, this article provides a state of the art about DASH and adaptive streaming technology, and also YouTube traffic characterization related work. Secondly, this paper describes a new methodology and test-bed for YouTube’s DASH implementation traffic characterization and performance measurement. This methodology and test-bed do not make use of proxies and, moreover, they are able to cope with YouTube traffic redirections. Finally, a set of experimental results are provided, involving a dataset of 310 YouTube’s videos. The depicted results show a YouTube’s traffic pattern characterization and a discussion about allowed download bandwidth, YouTube’s consumed bitrate and quality of the video. Moreover, the obtained results are cross-validated with the analysis of HTTP requests performed by YouTube’s video player. The outcomes of this article are applicable in the field of Quality of Service (QoS) and Quality of Experience (QoE) management. This is valuable information for Internet Service Providers (ISPs), because QoS management based on assured download bandwidth can be used in order to provide a target end-user’s QoE when YouTube service is being consumed.     

Proof Pearl: Mechanizing the Textbook Proof of Huffman’s Algorithm

Huffman’s algorithm is a procedure for constructing a binary tree with minimum weighted path length. Our Isabelle/HOL proof closely follows the sketches found in standard algorithms textbooks, uncovering a few snags in the process. Another distinguishing feature of our formalization is the use of custom induction rules to help Isabelle’s automatic tactics, leading to very short proofs for most of the lemmas. This work was supported by the DFG grant NI 491/11-1.     

Continuously Parameterized Symmetries and Buchberger’s Algorithm

Systems of polynomial equations often have symmetries. In solving such a system using Buchberger’s algorithm, the symmetries are neglected. Incorporating symmetries into the solution process enables us to solve larger problems than with Buchberger’s algorithm alone. This paper presents a method that shows how this can be achieved and also gives an algorithm that brings together continuously parameterized symmetries with Buchberger’s algorithm.     

Generalization of Krasnoshchekov’s Model for the Case of a Decomposable Matrix of Social Interactions

In this work, Krasnoshchekov’s model, which describes the behavior of people in a community under social and informational influences, is generalized to include the case of a system with a sophisticated structure of social interaction. In particular, the situation when an isolated group of people is formed who are not familiar with the rest of the community, which corresponds to a decomposable matrix of social interactions, is studied. The conditions for the solution of the system of equations describing the behavior of such a community to exist and be unique are considered. The problem of finding the relation between Krasnoshchekov’s and De Groot’s models is solved. The way this matrix of social interactions and the social independence of individuals affect the structure of the solution of this system, which describes in particularl how beliefs spread among people, is studied.     

Analysis of WLAN’s received signal strength indication for indoor location fingerprinting

An indoor positioning system that uses a location fingerprinting technique based on the received signal strength of a wireless local area network is an enabler for indoor location-aware computing. Data analysis of the received signal strength indication is very essential for understanding the underlying location-dependent features and patterns of location fingerprints. This knowledge can assist a system designer in accurately modeling a positioning system, improving positioning performance, and efficiently designing such a system. This study investigates extensively through measurements, the features of the received signal strength indication reported by IEEE 802.11b/g wireless network interface cards. The results of the statistical data analysis help in identifying a number of phenomena that affect the precision and accuracy of indoor positioning systems.     

Solving SAT by Algorithm Transform of Wu s Method

Recently algorithms for solving propositional satisfiability problem, or SAT,have aroused great interest,and more attention has been paid to transformation problem solving.The commonly used transformation is representation transform,but since its intermediate computing procedure is a black box from the viewpoint of the original problem,this approach has many limitations.In this paper,a new approach called algorithm transform is proposed and applied to solving SAT by Wu‘s method,a general algorithm for solving polynomial equations.B y establishing the correspondence between the primitive operation in Wu‘s method and clause resolution is SAT,it is shown that Wu‘s method,when used for solving SAT,,is primarily a restricted clause resolution procedure.While Wu‘s method introduces entirely new concepts.e.g.characteristic set of clauses,to resolution procedure,the complexity result of resolution procedure suggests an exponential lower bound to Wu‘s method for solving general polynomial equations.Moreover,this algorithm transform can help achieve a more efficient implementation of Wu‘s method since it can avoid the complex manipulation of polynomials and can make the best use of domain specific knowledge.     

On Smoothed Analysis of?Quicksort?and?Hoare’s Find

We provide a smoothed analysis of Hoare’s find algorithm, and we revisit the smoothed analysis of quicksort. Hoare’s find algorithm—often called quickselect or one-sided quicksort—is an easy-to-implement algorithm for finding the k-th smallest element of a sequence. While the worst-case number of comparisons that Hoare’s find needs is Θ(n ²), the average-case number is Θ(n). We analyze what happens between these two extremes by providing a smoothed analysis. In the first perturbation model, an adversary specifies a sequence of n numbers of [0,1], and then, to each number of the sequence, we add a random number drawn independently from the interval [0,d]. We prove that Hoare’s find needs $\Theta(\frac{n}{d+1} \sqrt{n/d} + n)$ comparisons in expectation if the adversary may also specify the target element (even after seeing the perturbed sequence) and slightly fewer comparisons for finding the median. In the second perturbation model, each element is marked with a probability of p, and then a random permutation is applied to the marked elements. We prove that the expected number of comparisons to find the median is $\Omega((1-p) \frac{n}{p} \log n)$ . Finally, we provide lower bounds for the smoothed number of comparisons of quicksort and Hoare’s find for the median-of-three pivot rule, which usually yields faster algorithms than always selecting the first element: The pivot is the median of the first, middle, and last element of the sequence. We show that median-of-three does not yield a significant improvement over the classic rule.     

Analysis of Multi-Sort Algorithm on Multi-Mesh of Trees (MMT) architecture

Various sorting algorithms using parallel architectures have been proposed in the search for more efficient results. This paper introduces the Multi-Sort Algorithm for Multi-Mesh of Trees (MMT) Architecture for N=n ⁴ elements with more efficient time complexity compared to previous architectures. The shear sort algorithm on Single Instruction Multiple Data (SIMD) mesh model requires \(4\sqrt{N}+O\sqrt{N}\) time for sorting N elements, arranged on a \(\sqrt{N}\times \sqrt{N}\) mesh, whereas Multi-Sort algorithm on the SIMD Multi-Mesh (MM) Architecture takes O(N ^1/4) time for sorting the same N elements, which proves that Multi-Sort is a better sorting approach. We have improved the time complexity of intrablock Sort. The Communication time complexity for 2D Sort in MM is O(n), whereas this time in MMT is O(log?n). The time complexity of compare–exchange step in MMT is same as that in MM, i.e., O(n). It has been found that the time complexity of the Multi-Sort on MMT has been improved as on Multi-Mesh architecture.     

Technological Gap： The Education Case of the State of Puebla,Mexico

The teaching-learning process may have several obstacles; one of those would be a cultural situation of students but also the ICT （information and communication technologies） resource distribution per children. When we refer to cultural situation, we mean the language or dialect that they speak. In the state of Puebla, Mexico, there are primary schools in which courses are taught to students who do not speak Spanish and they only speak their own dialect. On the other hand, the use of information and communication technologies in primary schools in Puebla is a fact but a main concern in schools is that the languages in which are operated is Spanish. The present article will also deal with the distribution of enciclomedia sets per children population in the 217 communities of the state of Puebla. To analyze this situation, we find that turns out to be very important and with a negative effect on both the implementation and acceptance of a multimedia program in these schools, generating a technological gap between students. The government efforts are being decimated because of this cultural divide prevalent in many communities in the state of Puebla, Mexico.     

Path-Value Functions for Which Dijkstra’s Algorithm Returns Optimal Mapping

Dijkstra’s algorithm (DA) is one of the most useful and efficient graph-search algorithms, which can be modified to solve many different problems. It is usually presented as a tool for finding a mapping which, for every vertex v, returns a shortest-length path to v from a fixed single source vertex. However, it is well known that DA returns also a correct optimal mapping when multiple sources are considered and for path-value functions more general than the standard path-length. The use of DA in such general setting can reduce many image processing operations to the computation of an optimum-path forest with path-cost function defined in terms of local image attributes. In this paper, we describe the general properties of a path-value function defined on an arbitrary finite graph which, provably, ensure that Dijkstra’s algorithm indeed returns an optimal mapping. We also provide the examples showing that the properties presented in a 2004 TPAMI paper on the image foresting transform, which were supposed to imply proper behavior of DA, are actually insufficient. Finally, we describe the properties of the path-value function of a graph that are provably necessary for the algorithm to return an optimal mapping.     

An Algorithm for Solving a Family of Fourth-Degree Diophantine Equations that Satisfy Runge’s Condition

Programming and Computer Software - This paper proposes an algorithmic implementation of the elementary version of Runge’s method for a family of fourth-degree Diophantine equations in two...     

Stability Analysis of an Underactuated Autonomous Underwater Vehicle Using Extended-Routh’s Stability Method

In this paper, a new approach to stability analysis of nonlinear dynamics of an underactuated autonomous underwater vehicle (AUV) is presented. AUV is a highly nonlinear robotic system whose dynamic model includes coupled terms due to the hydrodynamic damping factors. It is difficult to analyze the stability of a nonlinear dynamical system through Routh’s stability approach because it contains nonlinear dynamic parameters owing to hydrodynamic damping coefficients. It is also difficult to analyze the stability of AUVs using Lyapunov’s criterion and LaSalle’s invariance principle. In this paper, we proposed the extended-Routh’s stability approach to verify the stability of such nonlinear dynamic systems. This extended-Routh’s stability approach is much easier as compared to the other existing methods. Numerical simulations are presented to demonstrate the efficacy of the proposed stability verification of the nonlinear dynamic systems, e.g., an AUV system dynamics.     

A Perspective Analysis of the Proportions of Palladio’s Villa Rotonda: Making the Invisible Visible

Because of differences between Palladio’s architecture as built and the ideal architecture represented in the Quattro libri, many analyses have been performed in order to bring to light the proportions that underlie the beauty of the architecture. This present paper proposes a method of analysis based on perspective grids laid out on photographs to reveal how perspective is used to heighten the spectator’s perception of the forms.     

Algorithm for the discrete Weber’s problem with an accuracy estimate

We consider a relaxation of the quadratic assignment problem without the constraint on the number of objects assigned to a specific position. This problem is NP-hard in the general case. To solve the problem, we propose a polynomial algorithm with guaranteed posterior accuracy estimate; we distinguish a class of problems with special assignment cost functions where the algorithm is 2-approximate. We show that if the graph in question contains one simple loop, and the set of assignment positions is a metric space, the proposed algorithm is 2-approximate and guaranteed to be asymptotically exact. We conduct a computational experiment in order to analyze the algorithm’s errors and evaluate its accuracy.     

Structural optimization complexity: what has Moore’s law done for us?

Rapid increases in computer processing power, memory and storage space have not eliminated computational cost and time constraints on the use of structural optimization for design. This is due to the constant increase in the required fidelity (and hence complexity) of analysis models. Anecdotal evidence seems to indicate that analysis models of acceptable accuracy have required at least six to eight hours of computer time (an overnight run) throughout the last thirty years. This poses a severe challenge for global optimization or reliability-based design. In this paper, we review how increases in computer power were utilized in structural optimization. We resolve problem complexity into components relating to complexity of analysis model, analysis procedure and optimization methodology. We explore the structural optimization problems that we can solve at present and conclude that we can solve problems with the highest possible complexity in only two of the three components of model, analysis procedure or optimization. We use examples of optimum design of composite structures to guide the discussion due to our familiarity with such problems. However, these are supplemented with other structural optimization examples to illustrate the universality of the message.     

Analysis of a Multiobjective Evolutionary Algorithm on the 0–1 knapsack problem

Multiobjective Evolutionary Algorithms (MOEAs) are increasingly being used for effectively solving many real-world problems, and many empirical results are available. However, theoretical analysis is limited to a few simple toy functions. In this work, we select the well-known knapsack problem for the analysis. The multiobjective knapsack problem in its general form is NP-complete. Moreover, the size of the set of Pareto-optimal solutions can grow exponentially with the number of items in the knapsack. Thus, we formalize a (1+ε)$(1+\epsilon )$-approximate set of the knapsack problem and attempt to present a rigorous running time analysis of a MOEA to obtain the formalized set. The algorithm used in the paper is based on a restricted mating pool with a separate archive to store the remaining population; we call the algorithm a Restricted Evolutionary Multiobjective Optimizer (REMO). We also analyze the running time of REMO on a special bi-objective linear function, known as LOTZ (Leading Ones : Trailing Zeros), whose Pareto set is shown to be a subset of the knapsack. An extension of the analysis to the Simple Evolutionary Multiobjective Optimizer (SEMO) is also presented. A strategy based on partitioning of the decision space into fitness layers is used for the analysis.