O'Reilly logo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

A Guide to Algorithm Design

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