This book offers advanced parallel and distributed algorithms and experimental laboratory prototypes of unconventional shortest path solvers. In addition, it presents novel and unique algorithms of solving shortest problems in massively parallel cellular automaton machines. The shortest path problem is a fundamental and classical problem in graph theory and computer science and is frequently applied in the contexts of transport and logistics, telecommunication networks, virtual reality and gaming, geometry, and social networks analysis. Software implementations include distance-vector algorithms for distributed path computation in dynamics networks, parallel solutions of the constrained shortest path problem, and application of the shortest path solutions in gathering robotic swarms. Massively parallel algorithms utilise cellular automata, where a shortest path is computed either via matrix multiplication in automaton arrays, or via the representation of data graphs in automaton lattices and using the propagation of wave-like patterns. Unconventional shortest path solvers are presented in computer models of foraging behaviour and protoplasmic network optimisation by the slime mould Physarum polycephalum and fluidic devices, while experimental laboratory prototypes of path solvers using chemical media, flows and droplets, and electrical current are also highlighted. The book will be a pleasure to explore for readers from all walks of life, from undergraduate students to university professors, from mathematicians, computers scientists and engineers to chemists and biologists.

Algorithmic Learning in a Random World describes recent theoretical and experimental developments in building computable approximations to Kolmogorov's algorithmic notion of randomness. Based on these approximations, a new set of machine learning algorithms have been developed that can be used to make predictions and to estimate their confidence and credibility in high-dimensional spaces under the usual assumption that the data are independent and identically distributed (assumption of randomness). Another aim of this unique monograph is to outline some limits of predictions: The approach based on algorithmic theory of randomness allows for the proof of impossibility of prediction in certain situations. The book describes how several important machine learning problems, such as density estimation in high-dimensional spaces, cannot be solved if the only assumption is randomness.

hebookpresentedtothereaderisdevotedtotime-dependentscheduling. TScheduling problems, in general, consist in the allocation of resources over time in order to perform a set of jobs. Any allocation that meets all requirements concerning the jobs and resources is called a feasible schedule. The quality of a schedule is measured by a criterion function. The aim of scheduling is to ?nd, among all feasible schedules, a schedule that optimizes the criterion function. A solution to an arbitrary scheduling problem consists in giving a polynomial-time algorithm generating either an optimal schedule or a schedule that is close to the optimal one, if the given scheduling problem has been proved to be computationally intractable. The scheduling problems are subject of interest of the scheduling theory, originated in mid-?fties of the twentieth century. The theory has been developing dynamically and new research areas constantly come into existence. The subject of this book, ti- dependent scheduling, is one of such areas. In time-dependent scheduling, the processing time of a job is variable and depends on the starting time of the job. This crucial assumption allows us to apply the scheduling theory to a broader spectrum of problems. For example, in the framework of the time-dependent scheduling theory we may consider the problems of repayment of multiple loans, ?re ?ghting and maintenance assignments. In this book, we will discuss algorithms and complexity issues concerning various time-dependent scheduling problems.

Anyone browsing at the stationery store will see an incredible array of pop-up cards available for any occasion. The workings of pop-up cards and pop-up books can be remarkably intricate. Behind such designs lies beautiful geometry involving the intersection of circles, cones, and spheres, the movements of linkages, and other constructions. The geometry can be modelled by algebraic equations, whose solutions explain the dynamics. For example, several pop-up motions rely on the intersection of three spheres, a computation made every second for GPS location. Connecting the motions of the card structures with the algebra and geometry reveals abstract mathematics performing tangible calculations. Beginning with the nephroid in the 19th-century, the mathematics of pop-up design is now at the frontiers of rigid origami and algorithmic computational complexity. All topics are accessible to those familiar with high-school mathematics; no calculus required. Explanations are supplemented by 140+ figures and 20 animations.

This is a how-to book for solving geometric problems robustly or error free in actual practice. The contents and accompanying source code are based on the feature requests and feedback received from industry professionals and academics who want both the descriptions and source code for implementations of geometric algorithms. The book provides a framework for geometric computing using several arithmetic systems and describes how to select the appropriate system for the problem at hand. Key Features: A framework of arithmetic systems that can be applied to many geometric algorithms to obtain robust or error-free implementations Detailed derivations for algorithms that lead to implementable code Teaching the readers how to use the book concepts in deriving algorithms in their fields of application The Geometric Tools Library, a repository of well-tested code at the Geometric Tools website, https://www.geometrictools.com, that implements the book concepts

New generations of IT users are increasingly abstracted from the underlying devices and platforms that provide and safeguard their services. As a result they may have little awareness that they are critically dependent on the embedded security devices that are becoming pervasive in daily modern life. Secure Smart Embedded Devices, Platforms and Applications provides a broad overview of the many security and practical issues of embedded devices, tokens, and their operation systems, platforms and main applications. It also addresses a diverse range of industry/government initiatives and considerations, while focusing strongly on technical and practical security issues. The benefits and pitfalls of developing and deploying applications that rely on embedded systems and their security functionality are presented. A sufficient level of technical detail to support embedded systems is provided throughout the text, although the book is quite readable for those seeking awareness through an initial overview of the topics. This edited volume benefits from the contributions of industry and academic experts and helps provide a cross-discipline overview of the security and practical issues for embedded systems, tokens, and platforms. It is an ideal complement to the earlier work, Smart Cards Tokens, Security and Applications from the same editors.

Introductory courses in combinatorial optimization are popular at the upper undergraduate/graduate levels in computer science, industrial engineering, and business management/OR, owed to its wide applications in these fields. There are several published textbooks that treat this course and the authors have used many of them in their own teaching experiences. This present text fills a gap and is organized with a stress on methodology and relevant content, providing a step-by-step approach for the student to become proficient in solving combinatorial optimization problems. Applications and problems are considered via recent technology developments including wireless communication, cloud computing, social networks, and machine learning, to name several, and the reader is led to the frontiers of combinatorial optimization. Each chapter presents common problems, such as minimum spanning tree, shortest path, maximum matching, network flow, set-cover, as well as key algorithms, such as greedy algorithm, dynamic programming, augmenting path, and divide-and-conquer. Historical notes, ample exercises in every chapter, strategically placed graphics, and an extensive bibliography are amongst the gems of this textbook.

Elucidating the spatial and temporal dynamics of how things connect has become one of the most important areas of research in the 21st century. Network science now pervades nearly every science domain, resulting in new discoveries in a host of dynamic social and natural systems, including: how neurons connect and communicate in the brain, how information percolates within and among social networks, the evolution of science research through co-authorship networks, the spread of epidemics and many other complex phenomena. Over the past decade, advances in computational power have put the tools of network analysis in the hands of increasing numbers of scientists, enabling more explorations of our world than ever before possible. Information science, social sciences, systems biology, ecosystems ecology, neuroscience and physics all benefit from this movement, which combines graph theory with data sciences to develop and validate theories about the world around us. This book brings together cutting-edge research from the network science field and includes diverse and interdisciplinary topics such as: modeling the structure of urban systems, behavior in social networks, education and learning, data network architecture, structure and dynamics of organizations, crime and terrorism, as well as network topology, modularity and community detection.

In the late 1960s British mathematician John Conway invented a virtual mathematical machine that operates on a two-dimensional array of square cell. Each cell takes two states, live and dead. The cells' states are updated simultaneously and in discrete time. A dead cell comes to life if it has exactly three live neighbours. A live cell remains alive if two or three of its neighbours are alive, otherwise the cell dies. Conway's Game of Life became the most programmed solitary game and the most known cellular automaton. The book brings together results of forty years of study into computational, mathematical, physical and engineering aspects of The Game of Life cellular automata. Selected topics include phenomenology and statistical behaviour; space-time dynamics on Penrose tilling and hyperbolic spaces; generation of music; algebraic properties; modelling of financial markets; semi-quantum extensions; predicting emergence; dual-graph based analysis; fuzzy, limit behaviour and threshold scaling; evolving cell-state transition rules; localization dynamics in quasi-chemical analogues of GoL; self-organisation towards criticality; asynochrous implementations. The volume is unique because it gives a comprehensive presentation of the theoretical and experimental foundations, cutting-edge computation techniques and mathematical analysis of the fabulously complex, self-organized and emergent phenomena defined by incredibly simple rules.

Bioinformatics is the study of biological information and biological systems - such as of the relationships between the sequence, structure and function of genes and proteins. The subject has seen tremendous development in recent years, and there are ever-increasing needs for good understanding of quantitative methods in the study of proteins. "Protein Bioinformatics: An Algorithmic Approach to Sequence and Structure Analysis" takes the novel approach of covering both the sequence and structure analysis of proteins in one volume and from an algorithmic perspective. Provides a comprehensive introduction to the analysis of protein sequences and structures. Provides an integrated presentation of methodology, examples, exercises and applications. Emphasises the algorithmic rather than mathematical aspects of the methods described. Covers comparison and alignment of protein sequences and structures as well as protein structure prediction focusing on threading approaches. Written in an accessible yet rigorous style, suitable for biologists, mathematicians and computer scientists alike. Suitable both for developers and users of bioinformatics tools. Supported by a Web site featuring exercises, solutions, images, and computer programs.

"Protein Bioinformatics: An Algorithmic Approach to Sequence and Structure Analysis" is ideally suited for advanced undergraduate and graduate students of bioinformatics, statistics, mathematics and computer science. It also provides an excellent introduction and reference source on the subject for practitioners and researchers.

This book is the first systematic exposition on the emerging domain of wireless power transfer in ad hoc communication networks. It selectively spans a coherent, large spectrum of fundamental aspects of wireless power transfer, such as mobility management in the network, combined wireless power and information transfer, energy flow among network devices, joint activities with wireless power transfer (routing, data gathering and solar energy harvesting), and safety provisioning through electromagnetic radiation control, as well as fundamental and novel circuits and technologies enabling the wide application of wireless powering. Comprising a total of 27 chapters, contributed by leading experts, the content is organized into six thematic sections: technologies, communication, mobility, energy flow, joint operations, and electromagnetic radiation awareness. It will be valuable for researchers, engineers, educators, and students, and it may also be used as a supplement to academic courses on algorithmic applications, wireless protocols, distributed computing, and networking.

Techniques for Designing and Analyzing Algorithms Design and analysis of algorithms can be a difficult subject for students due to its sometimes-abstract nature and its use of a wide variety of mathematical tools. Here the author, an experienced and successful textbook writer, makes the subject as straightforward as possible in an up-to-date textbook incorporating various new developments appropriate for an introductory course. This text presents the main techniques of algorithm design, namely, divide-and-conquer algorithms, greedy algorithms, dynamic programming algorithms, and backtracking. Graph algorithms are studied in detail, and a careful treatment of the theory of NP-completeness is presented. In addition, the text includes useful introductory material on mathematical background including order notation, algorithm analysis and reductions, and basic data structures. This will serve as a useful review and reference for students who have covered this material in a previous course. Features The first three chapters provide a mathematical review, basic algorithm analysis, and data structures Detailed pseudocode descriptions of the algorithms along with illustrative algorithms are included Proofs of correctness of algorithms are included when appropriate The book presents a suitable amount of mathematical rigor After reading and understanding the material in this book, students will be able to apply the basic design principles to various real-world problems that they may encounter in their future professional careers.

Random Generation of Trees is about a field on the crossroads between computer science, combinatorics and probability theory. Computer scientists need random generators for performance analysis, simulation, image synthesis, etc. In this context random generation of trees is of particular interest. The algorithms presented here are efficient and easy to code. Some aspects of Horton--Strahler numbers, programs written in C and pictures are presented in the appendices. The complexity analysis is done rigorously both in the worst and average cases. Random Generation of Trees is intended for students in computer science and applied mathematics as well as researchers interested in random generation.

Graph algorithms is a well-established subject in mathematics and computer science. Beyond classical application fields, such as approximation, combinatorial optimization, graphics, and operations research, graph algorithms have recently attracted increased attention from computational molecular biology and computational chemistry. Centered around the fundamental issue of graph isomorphism, this text goes beyond classical graph problems of shortest paths, spanning trees, flows in networks, and matchings in bipartite graphs. Advanced algorithmic results and techniques of practical relevance are presented in a coherent and consolidated way. This book introduces graph algorithms on an intuitive basis followed by a detailed exposition in a literate programming style, with correctness proofs as well as worst-case analyses. Furthermore, full C++ implementations of all algorithms presented are given using the LEDA library of efficient data structures and algorithms.

A matroid is an abstract mathematical structure that captures combinatorial properties of matrices. This book offers a unique introduction to matroid theory, emphasizing motivations from matrix theory and applications to systems analysis.This book serves also as a comprehensive presentation of the theory and application of mixed matrices, developed primarily by the present author in the last decade. A mixed matrix is a convenient mathematical tool for systems analysis, compatible with the physical observation that "fixed constants" and "system parameters" are to be distinguished in the description of engineering systems.This book will be extremely useful to graduate students and researchers in engineering, mathematics and computer science.

Semidefinite programs constitute one of the largest classes of optimization problems that can be solved with reasonable efficiency - both in theory and practice. They play a key role in a variety of research areas, such as combinatorial optimization, approximation algorithms, computational complexity, graph theory, geometry, real algebraic geometry and quantum computing. This book is an introduction to selected aspects of semidefinite programming and its use in approximation algorithms. It covers the basics but also a significant amount of recent and more advanced material.

There are many computational problems, such as MAXCUT, for which one cannot reasonably expect to obtain an exact solution efficiently, and in such case, one has to settle for approximate solutions. For MAXCUT and its relatives, exciting recent results suggest that semidefinite programming is probably the ultimate tool. Indeed, assuming the Unique Games Conjecture, a plausible but as yet unproven hypothesis, it was shown that for these problems, known algorithms based on semidefinite programming deliver the best possible approximation ratios among all polynomial-time algorithms.

This book follows the "semidefinite side" of these developments, presenting some of the main ideas behind approximation algorithms based on semidefinite programming. It develops the basic theory of semidefinite programming, presents one of the known efficient algorithms in detail, and describes the principles of some others. It also includes applications, focusing on approximation algorithms."

Cryptographic Engineering is the first book that discusses the design techniques and methods. The material of this book is scattered in journal and conference articles, and authors lecture notes. This is a first attempt by top cryptographic engineers to bring this material in a book form and make it available to electrical engineering and computer science students and engineers working for the industry.

This book is intended for a graduate-level course in Cryptographic Engineering to be taught in Electrical Engineering, Computer Engineering, and Computer Science departments. Students will have to have the knowledge of basic cryptographic algorithms before taking this course which will teach them how to design cryptographic hardware (FPGA, ASIC, custom) and embedded software to be used in secure systems.

Additionally, engineers working in the industry will be interested in this book to learn how to design cryptographic chips and embedded software. Engineers working on the design of cellular phones, mobile computing and sensor systems, web and enterprise security systems which rely upon cryptographic hardware and software will be interested in this book. Essential and advanced design techniques for cryptography will be covered by this book."

The Fourier transform is one of the most fundamental tools for computing the frequency representation of signals. It plays a central role in signal processing, communications, audio and video compression, medical imaging, genomics, astronomy, as well as many other areas. Because of its widespread use, fast algorithms for computing the Fourier transform can benefit a large number of applications. The fastest algorithm for computing the Fourier transform is the Fast Fourier Transform (FFT), which runs in near-linear time making it an indispensable tool for many applications. However, today, the runtime of the FFT algorithm is no longer fast enough especially for big data problems where each dataset can be few terabytes. Hence, faster algorithms that run in sublinear time, i.e., do not even sample all the data points, have become necessary. This book addresses the above problem by developing the Sparse Fourier Transform algorithms and building practical systems that use these algorithms to solve key problems in six different applications: wireless networks; mobile systems; computer graphics; medical imaging; biochemistry; and digital circuits. This is a revised version of the thesis that won the 2016 ACM Doctoral Dissertation Award.

Algorithmic graph theory has been expanding at an extremely rapid rate since the middle of the twentieth century, in parallel with the growth of computer science and the accompanying utilization of computers, where efficient algorithms have been a prime goal. This book presents material on developments on graph algorithms and related concepts that will be of value to both mathematicians and computer scientists, at a level suitable for graduate students, researchers and instructors. The fifteen expository chapters, written by acknowledged international experts on their subjects, focus on the application of algorithms to solve particular problems. All chapters were carefully edited to enhance readability and standardize the chapter structure as well as the terminology and notation. The editors provide basic background material in graph theory, and a chapter written by the book's Academic Consultant, Martin Charles Golumbic (University of Haifa, Israel), provides background material on algorithms as connected with graph theory.

This book provides a valuable combination of relevant research works on developing smart city ecosystem from the artificial intelligence (AI) and Internet of things (IoT) perspective. The technical research works presented here are focused on a number of aspects of smart cities: smart mobility, smart living, smart environment, smart citizens, smart government, and smart waste management systems as well as related technologies and concepts. This edited book offers critical insight to the key underlying research themes within smart cities, highlighting the limitations of current developments and potential future directions.

This book compares the performance of various evolutionary computation (EC) techniques when they are faced with complex optimization problems extracted from different engineering domains. Particularly focusing on recently developed algorithms, it is designed so that each chapter can be read independently. Several comparisons among EC techniques have been reported in the literature, however, they all suffer from one limitation: their conclusions are based on the performance of popular evolutionary approaches over a set of synthetic functions with exact solutions and well-known behaviors, without considering the application context or including recent developments. In each chapter, a complex engineering optimization problem is posed, and then a particular EC technique is presented as the best choice, according to its search characteristics. Lastly, a set of experiments is conducted in order to compare its performance to other popular EC methods.

The book presents a comprehensive treatment on a novel design theory that fosters innovative thinking and creativity essential for addressing wicked problems. Wicked problems are ill-defined, ambiguous in both aims and solutions, and complex with interconnected and intertwined (coupled) factors. While being ubiquitous and difficult, however, wicked problems share characteristics common to science and design in three regards, namely agent finitude, system complexity, and problem normativity. These fundamental attributes allow a core cognitive process common to design and science to be identified and a strategic problem-solving conception of methodology be formulated as a result. The theory facilitates new opportunities for synergetic cross-disciplinary research and practice by incorporating the essences of Extenics to axiomatic design. Innovative thinking is enabled by exploring Extenics for problem reframing, paradigm shift, and abductive reasoning and by engaging axiomatic design in the co-evolution (iteration) of the need and viable design concept. The theory is unique in that it is a framework for quantifying imprecise and vague design information available during the conceptual design stage as mathematical expression and algorithm early in the design effort and enables the objective evaluation and emergence of an optimal design concept from among multitude of viable ones. The book is conceived for students and real-world practitioners in engineering, natural and social sciences, business, and fine arts who seek to develop powerful design thinking for solving problems in a creative and innovative way.

This book gives a comprehensive view of graph theory in informational retrieval (IR) and natural language processing(NLP). This book provides number of graph techniques for IR and NLP applications with examples. It also provides understanding of graph theory basics, graph algorithms and networks using graph. The book is divided into three parts and contains nine chapters. The first part gives graph theory basics and graph networks, and the second part provides basics of IR with graph-based information retrieval. The third part covers IR and NLP recent and emerging applications with case studies using graph theory. This book is unique in its way as it provides a strong foundation to a beginner in applying mathematical structure graph for IR and NLP applications. All technical details that include tools and technologies used for graph algorithms and implementation in Information Retrieval and Natural Language Processing with its future scope are explained in a clear and organized format.

The objective of the book is to provide materials to demonstrate the development of TOPSIS and to serve as a handbook. It contains the basic process of TOPSIS, numerous variant processes, property explanations, theoretical developments, and illustrative examples with real-world cases. Possible readers would be graduate students, researchers, analysts, and professionals who are interested in TOPSIS, a distance-based algorithm, and who would like to compare TOPSIS with other MCDM methods. The book serves as a research reference as well as a self-learning book with step-by-step illustrations for the MCDM community.