Algorithms And Data Structures

Asymptotic algorithm analysis is a methodology which has been given a lot of attention recently. Several methods of asymptotic analysis are considered to estimate the resource consumption of an algorithm, giving an assessment if a proposed algorithm can meet the resource constraints for a problem before the implementation. Processing nodes of the binary and non-binary trees in an organized manner is investigated using various algorithms. Several methods for implementing binary trees and their nodes are given. Issues relating to the design of algorithms and data structures for disk-based applications are solved, as well as problems of searching data stored in lists and tables. Algorithms for solving some problems related to finding shortest routes in a graph and the minimum-cost spanning tree, are applied to determine lowest-cost connectivity in a network.

The initial five chapters of this book considers asymptotic algorithm analysis and provide various algorithms, such as modification of LMS algorithm, a direct search algorithm is proposed for minimizing an arbitrary function, etc. The following nine chapters present generative algorithms for random graphs, trees and big data. The remaining content of this book focuses on the advances of specific methods and algorithms in the field of data structures, especially in graph theory.

The mean square convergence of the LMS algorithm is investigated for the large class of linearly filtered random driving processes, containing the following contributions: (i) The parameter error vector covariance matrix can be decomposed into two parts, (ii) The impact of additive noise is shown to contribute only to the modal space of the driving process independently from the noise statistic and thus defines the steady state of the filter.

The certain and uncertain neutral systems with time-delay and saturating actuator are considered. In order to analyse and optimize the system, auxiliary functions are presented based on additive decomposition approach and the relationship among them is discussed. As the novel stability criterion, two sufficient conditions are obtained for asymptotic stability of the neutral systems. Furthermore, the stability analysis algorithm and optimality algorithm are introduced to optimize the result.

A direct search algorithm is proposed for minimizing an arbitrary real valued function. The algorithm uses a new function transformation and three simplex-based operations. The function transformation provides global exploration features, while the simplex-based operations guarantees the termination of the algorithm and provides global convergence to a stationary point if the cost function is differentiable and its gradient is Lipschitz continuous. The algorithm’s performance has been extensively tested using benchmark functions and compared to some well-known global optimization algorithms.

In the pursuit of finding subclasses of the makespan minimization problem on unrelated parallel machines that have approximation algorithms with approximation ratio better than 2, the graph balancing problem has been of current interest. In the graph balancing problem each job can be non-preemptively scheduled on one of at most two machines with the same processing time on either machine. A 3/2 -approximation algorithm for the graph balancing problem is presented.

Recently manifold learning has received extensive interest in the community of pattern recognition. Despite their appealing properties, most manifold learning algorithms are not robust in practical applications. This problem is addressed in the context of the Hessian locally linear embedding (HLLE) algorithm and propose a more robust method, called RHLLE, which aims to be robust against both outliers and noise in the data. Specifically, a fast outlier detection method for high-dimensional datasets is proposed. Then, a local smoothing method is employed to reduce noise.

Nowadays, a leading instance of big data is represented by Web data that lead to the definition of so-called big Web data. In order to process such kind of big data, MapReduce, an open source computational framework specifically tailored to big data processing, has emerged during the last years as the reference implementation for this critical setting. In line with this trend, an approach is presented for efficiently implementing traversals of large-scale Resource Description Framework (RDF) graphs over MapReduce that is based on the Breadth First Search (BFS) strategy for visiting (RDF) graphs to be decomposed and processed according to the MapReduce framework.

Big data are everywhere as high volumes of varieties of valuable precise and uncertain data can be easily collected or generated at high velocity in various real-life applications. Embedded in these big data are rich sets of useful information and knowledge. To mine these big data and to discover useful information and knowledge, a data analytic algorithm is presented. This algorithm manages, queries, and processes uncertain big data in cloud environments. More specifically, it manages transactions of uncertain big data, allows users to query these big data by specifying constraints expressing their interests, and processes the user-specified constraints to discover useful information and knowledge from the uncertain big data.

Generative algorithms for random graphs have yielded insights into the structure and evolution of real-world networks. A generative model for random graphs with discrete vertex labels and numeric edge weights is developed. The weights are represented as a set of Beta Mixture Models (BMMs) with an arbitrary number of mixtures, which are learned from real-world networks. Therefore, a Bayesian Variational Inference (VI) approach is proposed, which yields an accurate estimation while keeping computation times tractable.Aggregation delay is the minimum number of time slots required to aggregate data along the edges of a data gathering tree (DG tree) spanning all the nodes in a wireless sensor network (WSN). A benchmarking algorithm is proposed to determine the minimum possible aggregation delay for DG trees in a WSN. It is shown that the minimum aggregation delay for a DG tree depends on the underlying design choices (bottleneck node-weight based or bottleneck link-weight based) behind its construction. Some properties of a graph which is constructed from the equivalence classes of nonzero zero-divisors determined by the annihilator ideals of a poset are studied. In particular, it is demonstrated how this graph helps in identifying the annihilator prime ideals of a poset that satisfies the ascending chain condition for its proper annihilator ideals.

An m-distant tree T is a tree in which there is a path of maximum length such that every vertex in is at the most distance from. This path is called a central path. For every tree, there is an integer such that is an m-distant tree. The radio number of some m-distant trees is determined for any positive integer, and as a consequence of it, the radio number of a class of 1-distant trees is found.

The concept of distance degree regular (DDR) graphs denotes the graphs for which all vertices have the same distance degree sequence. By definition, a DDR graph must be a regular graph, but a regular graph may not be DDR. A graph is distance degree injective (DDI) graph if no two vertices have the same distance degree sequence. DDI graphs are highly irregular, in comparison with the DDR graphs. In this book, an exhaustive review of the two concepts of DDR and DDI graphs is conducted, starting with an insight into all distance related sequences and their applications. All the related open problems are listed.