A guide to algorithm design : paradigms, methods, and complexity analysis /: paradigms, methods, and complexity analysis. ([2014])

• Record Type: Book
• Further Information: Note: Anne Benoit, Yves Robert, and Frédérick Vivien.
• Authors: Benoit, Anne; Robert, Yves, 1938-; Vivien, Frédéric
• Contents: Polynomial-Time Algorithms: Exercises; Introduction to Complexity; On the complexity to compute xn ; 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
• Publisher Details: Boca Raton : CRC Press
• Publication Date: 2014
• Extent: 1 online resource
• Subjects: 005.1; Computer algorithms; Computational complexity; Computational complexity; Computer algorithms; Electronic books
• Languages: English
• ISBNs: 9781439898130; 1439898138; 9781439825648; 1439825645; 9781439898147; 1439898146; 9781466533875; 1466533870; 9781439825655; 1439825653
• Notes: Note: Includes bibliographical references and index.
• Access Rights: Legal Deposit; Only available on premises controlled by the deposit library and to one user at any one time; The Legal Deposit Libraries (Non-Print Works) Regulations (UK).
• Access Usage: Restricted: Printing from this resource is governed by The Legal Deposit Libraries (Non-Print Works) Regulations (UK) and UK copyright law currently in force.