Average Case Analysis of Algorithms on Sequences

by Wojciech Szpankowski

A timely book on a topic that has witnessed a surge of interest over the last decade, owing in part to several novel applications, most notably in data compression and computational molecular biology. It describes methods employed in average case analysis of algorithms, combining both analytical and probabilistic tools in a single volume.

• Tools are illustrated through problems on words with applications to molecular biology, data compression, security, and pattern matching.
• Includes chapters on algorithms and data structures on words, probabilistic and analytical models, inclusion-exclusion principles, first and second moment methods, subadditive ergodic theorem and large deviations, elements of information theory, generating functions, complex asymptotic methods, Mellin transform and its applications, and analytic poissonization and depoissonization.
• Written by an established researcher with a strong international reputation in the field.

Click to Read More

Planning Algorithms

By Steven M. LaValle

This book presents a unified treatment of many different kinds of planning algorithms. The subject lies at the crossroads between robotics, control theory, artificial intelligence, algorithms, and computer graphics. The particular subjects covered include motion planning, discrete planning, planning under uncertainty, sensor-based planning, visibility, decision-theoretic planning, game theory, information spaces, reinforcement learning, nonlinear systems, trajectory planning, nonholonomic planning, and kinodynamic planning.

Planning to Plan
Planning is a term that means different things to different groups of people. Robotics addresses the automation of mechanical systems that have sensing, actuation, and computation capabilities (similar terms, such as autonomous systems are also used). A fundamental need in robotics is to have algorithms that convert high-level specifications of tasks from humans into low-level descriptions of how to move. The terms motion planning and trajectory planning are often used for these kinds of problems. A classical version of motion planning is sometimes referred to as the Piano Mover’s Problem. Imagine giving a precise computer-aided design (CAD) model of a house and a piano as input to an algorithm. The algorithm must determine how to move the piano from one room to another in the house without hitting anything. Most of us have encountered similar problems when moving a sofa or mattress up a set of stairs. Robot motion planning usually ignores dynamics and other differential constraints and focuses primarily on the translations and rotations required to move the piano. Recent work, however, does consider other aspects, such as uncertainties, differential constraints, modeling errors, and optimality. Trajectory planning usually refers to the problem of taking the solution from a robot motion planning algorithm and determining how to move along the solution in a way that respects the mechanical limitations of the robot.

Click to Read More/Download

Data Structures And Algorithms

CSEd Tools

This book covers some commonly used data structures (such as arrays, linked-lists, trees, and graphs) and algorithms (such as sorting, searching, and various graph algorithms) that are used in Computer Science. The book is intended primarily for the readers who are already familiar with these data structures and algorithms, but would like to get some information on how to perform some advanced or non-trivial operations on/using them. Hence, for each data structure and algorithm, I have generally given a lighter treatment to the basic issues (since they are generally already covered elsewhere) and given more attention to more advanced issues related to them.

The book is actually still in writing, and I will add more material to it. So make sure to check this Web site from time-to-time to see the latest updates.

Note: This book contains several psuedocodes. Implementing these psuedocodes using a programming language will require rewriting them appropriately using language-specific constructs. The pseudocodes may also make some simplifying assumptions, may not check some boundary conditions such as nil input values, and may not check for invalid input values. The solutions provided here may not be the best possible solutions. In fact, simpler and more practical solutions have often been preferred over theoretically-better but more complicated solutions.

Click to Read More