A Guide to Algorithm Design

A Guide to Algorithm Design

by Anne Benoit, Yves Robert, Frédéric Vivien
Released August 2013
Publisher(s): CRC Press
ISBN: 9781439898130

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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

  1. Front Cover
  2. Contents (1/2)
  3. Contents (2/2)
  4. Preface
  5. Part I: Polynomial-time algorithms: Exercises
  6. Chapter 1: Introduction to complexity (1/6)
  7. Chapter 1: Introduction to complexity (2/6)
  8. Chapter 1: Introduction to complexity (3/6)
  9. Chapter 1: Introduction to complexity (4/6)
  10. Chapter 1: Introduction to complexity (5/6)
  11. Chapter 1: Introduction to complexity (6/6)
  12. Chapter 2: Divide-and-conquer (1/4)
  13. Chapter 2: Divide-and-conquer (2/4)
  14. Chapter 2: Divide-and-conquer (3/4)
  15. Chapter 2: Divide-and-conquer (4/4)
  16. Chapter 3: Greedy algorithms (1/6)
  17. Chapter 3: Greedy algorithms (2/6)
  18. Chapter 3: Greedy algorithms (3/6)
  19. Chapter 3: Greedy algorithms (4/6)
  20. Chapter 3: Greedy algorithms (5/6)
  21. Chapter 3: Greedy algorithms (6/6)
  22. Chapter 4: Dynamic programming (1/5)
  23. Chapter 4: Dynamic programming (2/5)
  24. Chapter 4: Dynamic programming (3/5)
  25. Chapter 4: Dynamic programming (4/5)
  26. Chapter 4: Dynamic programming (5/5)
  27. Chapter 5: Amortized analysis (1/4)
  28. Chapter 5: Amortized analysis (2/4)
  29. Chapter 5: Amortized analysis (3/4)
  30. Chapter 5: Amortized analysis (4/4)
  31. Part II: NP-completeness and beyond
  32. Chapter 6: NP-completeness (1/5)
  33. Chapter 6: NP-completeness (2/5)
  34. Chapter 6: NP-completeness (3/5)
  35. Chapter 6: NP-completeness (4/5)
  36. Chapter 6: NP-completeness (5/5)
  37. Chapter 7: Exercises on NP-completeness (1/6)
  38. Chapter 7: Exercises on NP-completeness (2/6)
  39. Chapter 7: Exercises on NP-completeness (3/6)
  40. Chapter 7: Exercises on NP-completeness (4/6)
  41. Chapter 7: Exercises on NP-completeness (5/6)
  42. Chapter 7: Exercises on NP-completeness (6/6)
  43. Chapter 8: Beyond NP-completeness (1/7)
  44. Chapter 8: Beyond NP-completeness (2/7)
  45. Chapter 8: Beyond NP-completeness (3/7)
  46. Chapter 8: Beyond NP-completeness (4/7)
  47. Chapter 8: Beyond NP-completeness (5/7)
  48. Chapter 8: Beyond NP-completeness (6/7)
  49. Chapter 8: Beyond NP-completeness (7/7)
  50. Chapter 9: Exercises going beyond NP-completeness (1/6)
  51. Chapter 9: Exercises going beyond NP-completeness (2/6)
  52. Chapter 9: Exercises going beyond NP-completeness (3/6)
  53. Chapter 9: Exercises going beyond NP-completeness (4/6)
  54. Chapter 9: Exercises going beyond NP-completeness (5/6)
  55. Chapter 9: Exercises going beyond NP-completeness (6/6)
  56. Part III: Reasoning on problem complexity
  57. Chapter 10: Reasoning to assess a problem complexity (1/2)
  58. Chapter 10: Reasoning to assess a problem complexity (2/2)
  59. Chapter 11: Chains-on-chains partitioning (1/3)
  60. Chapter 11: Chains-on-chains partitioning (2/3)
  61. Chapter 11: Chains-on-chains partitioning (3/3)
  62. Chapter 12: Replica placement in tree networks (1/6)
  63. Chapter 12: Replica placement in tree networks (2/6)
  64. Chapter 12: Replica placement in tree networks (3/6)
  65. Chapter 12: Replica placement in tree networks (4/6)
  66. Chapter 12: Replica placement in tree networks (5/6)
  67. Chapter 12: Replica placement in tree networks (6/6)
  68. Chapter13: Packet routing (1/4)
  69. Chapter13: Packet routing (2/4)
  70. Chapter13: Packet routing (3/4)
  71. Chapter13: Packet routing (4/4)
  72. Chapter 14: Matrix product, or tiling the unit square (1/4)
  73. Chapter 14: Matrix product, or tiling the unit square (2/4)
  74. Chapter 14: Matrix product, or tiling the unit square (3/4)
  75. Chapter 14: Matrix product, or tiling the unit square (4/4)
  76. Chapter 15: Online scheduling (1/6)
  77. Chapter 15: Online scheduling (2/6)
  78. Chapter 15: Online scheduling (3/6)
  79. Chapter 15: Online scheduling (4/6)
  80. Chapter 15: Online scheduling (5/6)
  81. Chapter 15: Online scheduling (6/6)
  82. References (1/2)
  83. References (2/2)
  84. Back Cover

Product information

  • Title: A Guide to Algorithm Design
  • Author(s): Anne Benoit, Yves Robert, Frédéric Vivien
  • Release date: August 2013
  • Publisher(s): CRC Press
  • ISBN: 9781439898130