A Guide to Algorithm Design: Paradigms, Methods, and Complexity Analysis

✍ Scribed by Anne Benoit (Author); Yves Robert (Author); Frédéric Vivien (Author)

• Publisher: CRC Press
• Year: 2013
• Leaves: 382
• Edition: 1
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Polynomial-Time Algorithms: Exercises

Introduction to Complexity

On the complexity to compute xⁿ

Asymptotic notations: O, o, Θ, and Ω

Divide-and-Conquer

Strassen’s algorithm

Master theorem

Solving recurrences

Greedy Algorithms

Motivating example: the sports hall

Designing greedy algorithms

Graph coloring

Theory of matroids

Dynamic Programming

The coin changing problem

The knapsack problem

Designing dynamic-programming algorithms

Amortized Analysis

Methods 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 classes

NP-complete problems and reduction theory

Examples of NP-complete problems and reductions

Importance of problem definition

Strong NP-completeness

Why does it matter?

Exercises on NP-Completeness

Easy reductions

About graph coloring

Scheduling problems

More involved reductions

2-PARTITION is NP-complete

Beyond NP-Completeness

Approximation results

Polynomial problem instances

Linear programming

Randomized algorithms

Branch-and-bound and backtracking

Exercises Going beyond NP-Completeness

Approximation results

Dealing 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 resources

Conclusion

Replica Placement in Tree Networks

Access policies

Complexity results

Variants of the replica placement problem

Conclusion

Packet Routing

MEDP: Maximum edge-disjoint paths

PRVP: Packet routing with variable-paths

Conclusion

Matrix Product, or Tiling the Unit Square

Problem motivation

NP-completeness

A guaranteed heuristic

Related problems

Online Scheduling

Flow time optimization

Competitive analysis

Makespan optimization

Conclusion

Bibliography

Index

✦ Subjects

Computer Science;Algorithms & Complexity;Computation;Computer Science (General)