eBook

- Provides exceptionally broad coverage of the field with the inclusion of all major techniques, ideas, and applications areas
- Presents important special topics, such as dynamic graph and external memory algorithms, not typically covered in similar books
- Takes an accessible approach to the material by starting with the basics and building up to more advanced topics
- Brings together contributions from top researchers and educators who offer valuable insight into key research issues
- Discusses both the state of knowledge and state of the practice
- Includes more than 20 new chapters

**Algorithms and Theory of Computation Handbook, Second Edition** provides an up-to-date compendium of fundamental computer science topics and techniques. It also illustrates how the topics and techniques come together to deliver efficient solutions to important practical problems.

*New to the Second Edition*Along with updating and revising many of the existing chapters, this second edition contains more than 20 new chapters. This edition now covers external memory, parameterized, self-stabilizing, and pricing algorithms as well as the theories of algorithmic coding, privacy and anonymity, databases, computational games, and communication networks. It also discusses computational topology, computational number theory, natural language processing, and grid computing and explores applications in intensity-modulated radiation therapy, voting, DNA research, systems biology, and financial derivatives.

This best-selling handbook continues to help computer professionals and engineers find significant information on various algorithmic topics. The expert contributors clearly define the terminology, present basic results and techniques, and offer a number of current references to the in-depth literature. They also provide a glimpse of the major research issues concerning the relevant topics.

**General Concepts and Techniques**

Algorithms Design and Analysis Techniques

Searching

Sorting and Order Statistics

Basic Data Structures

Topics in Data Structures

Multidimensional Data Structures for Spatial Applications

Basic Graph Algorithms

Advanced Combinatorial Algorithms

Dynamic Graph Algorithms

NEW! External Memory Algorithms and Data Structures

Average Case Analysis of Algorithms

Randomized Algorithms

Pattern Matching in Strings

Text Data Compression Algorithms

General Pattern Matching

NEW! Computational Number Theory

Algebraic and Numerical Algorithms

Applications of FFT and Structured Matrices

Basic Notions in Computational Complexity

Formal Grammars and Languages

Computability

Complexity Classes

Reducibility and Completeness

Other Complexity Classes and Measures

NEW! Parameterized Algorithms

Computational Learning Theory

NEW! Algorithmic Coding Theory

Parallel Computation: Models and Complexity Issues

Distributed Computing: A Glimmer of a Theory

Linear Programming

Integer Programming

Convex Optimization

Simulated Annealing Techniques

Approximation Algorithms for NP-Hard Optimization Problems

**Special Topics and Techniques**

Computational Geometry I

Computational Geometry II

NEW! Computational Topology

Robot Algorithms

Vision and Image Processing Algorithms

Graph Drawing Algorithms

NEW! Algorithmics in Intensity-Modulated Radiation Therapy

VLSI Layout Algorithms

Cryptographic Foundations

Encryption Schemes

Cryptanalysis

Crypto Topics and Applications I

Crypto Topics and Applications II

NEW! Secure Multiparty Computation

NEW! Voting Schemes

NEW! Auction Protocols

Pseudorandom Sequences and Stream Ciphers

NEW! Theory of Privacy and Anonymity

NEW! Database Theory: Query Languages

Scheduling Algorithms

NEW! Computational Game Theory: An Introduction

Artificial Intelligence Search Algorithms

NEW! Algorithmic Aspects of Natural Language Processing

Algorithmic Techniques for Regular Networks of Processors

Parallel Algorithms

NEW! Self-Stabilizing Algorithms

NEW! Theory of Communication Networks

NEW! Network Algorithmics

NEW! Algorithmic Issues in Grid Computing

NEW! Uncheatable Grid Computing

NEW! DNA Computing: A Research Snapshot

NEW! Computational Systems Biology

NEW! Pricing Algorithms for Financial Derivatives

Index

**Mikhail J. Atallah** is a distinguished professor of computer science at Purdue University.

**Marina Blanton** is an assistant professor in the computer science and engineering department at the University of Notre Dame.

… a compilation that will appeal to professionals and students alike; together with those engaged in research and especially those contemplating embarking upon research. … This second edition contains twenty-one new chapters and a thorough updating and revision of many of the chapters from the first edition. A consistent style has been adopted … the sections detailing research issues and sources for further information will ensure that this edition remains an excellent reference source for years to come. I recommend this text as both a teaching aid and a reference source whose utility can only but increase in the coming years.

—*International Statistical Review* (2011), 79, 1

The detailed treatment of algorithmic foundations for various subfields of computer science makes the handbook relevant for abroad community of researchers in computer science, operations research, and optimization ... the handbook is a useful reference and presents a broad outlook on the vast field of algorithms and the theory of computation.

—*Computing Reviews*, May 2010**Praise for the First Edition**… excellent survey of the state of the art … highly recommended for anyone interested in algorithms, data structures and the theory of computation … indispensable book of reference for all computer scientists, researchers and professional programmers.

—R. Kemp,