A Guide to Algorithm Design : Paradigms, Methods, and Complexity Analysis / by Anne Benoit, Yves Robert and Frédéric Vivien.

Format:

Book

Author/Creator:

Benoit, Anne, author.

Robert, Yves, author.

Vivien, Frédéric, author.

Series:

Chapman & Hall/CRC applied algorithms and data structures series.

Chapman & Hall/CRC applied algorithms and data structures series

Language:

English

Subjects (All):

Computational complexity.

Computer algorithms.

Physical Description:

1 online resource (xvii, 362 pages) : illustrations.

Edition:

1st edition

Place of Publication:

Boca Raton, FL : Taylor and Francis, an imprint of CRC Press, [2013].

System Details:

text file

Summary:

Presenting a complementary perspective to standard books on algorithms, A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis provides a roadmap for readers to determine the difficulty of an algorithmic problem by finding an optimal solution or proving complexity results. It gives a practical treatment of algorithmic complexity and guides readers in solving algorithmic problems. Divided into three parts, the book offers a comprehensive set of problems with solutions as well as in-depth case studies that demonstrate how to assess the complexity of a new problem. Part I helps readers understand the main design principles and design efficient algorithms. Part II covers polynomial reductions from NP-complete problems and approaches that go beyond NP-completeness. Part III supplies readers with tools and techniques to evaluate problem complexity, including how to determine which instances are polynomial and which are NP-hard. Drawing on the authors’ classroom-tested material, this text takes readers step by step through the concepts and methods for analyzing algorithmic complexity. Through many problems and detailed examples, readers can investigate polynomial-time algorithms and NP-completeness and beyond.

Contents:

Polynomial-Time Algorithms: Exercises Introduction to Complexity On the complexity to compute xnAsymptotic notations: O, o,, and

Divide-and-Conquer Strassens algorithm Master theorem Solving recurrences

Greedy Algorithms Motivating example: the sports hall Designing greedy algorithms Graph coloringTheory of matroids

Dynamic Programming The coin changing problem The knapsack problem Designing dynamic-programming algorithms

Amortized AnalysisMethods for amortized analysis

Exercises, Solutions, and Bibliographic Notes appear at the end of each chapter in this section.

NP-Completeness and Beyond NP-Completeness A practical approach to complexity theory Problem classesNP-complete problems and reduction theory Examples of NP-complete problems and reductionsImportance of problem definition Strong NP-completeness Why does it matter?

Exercises on NP-Completeness Easy reductionsAbout graph coloringScheduling problemsMore involved reductions2-PARTITION is NP-complete

Beyond NP-Completeness Approximation resultsPolynomial problem instancesLinear programmingRandomized algorithms Branch-and-bound and backtracking

Exercises Going beyond NP-Completeness Approximation resultsDealing with NP-complete problems

Reasoning on Problem Complexity Reasoning to Assess a Problem Complexity Basic reasoning Set of problems with polynomial-time algorithms Set of NP-complete problems

Chains-on-Chains Partitioning Optimal algorithms for homogeneous resources Variants of the problem Extension to a clique of heterogeneous resourcesConclusion

Replica Placement in Tree Networks Access policies Complexity resultsVariants of the replica placement problem Conclusion

Packet Routing MEDP: Maximum edge-disjoint pathsPRVP: Packet routing with variable-pathsConclusion

Matrix Product, or Tiling the Unit Square Problem motivation NP-completeness A guaranteed heuristicRelated problems

Online Scheduling Flow time optimization Competitive analysisMakespan optimizationConclusion

Bibliography

Index.

Notes:

Includes bibliographical references and index.

Description based on print version record.

ISBN:

9780429644115

0429644116

9780429428890

0429428898

9781439898130

1439898138

OCLC:

870251386