NU Learning Resource Center OPAC catalog › Details for: A guide to algorithm design : paradigms, methods, and complexity analysis /

Normal view MARC view ISBD view

A guide to algorithm design : paradigms, methods, and complexity analysis / Anne Benoit, Yves Robert, and Frédérick Vivien.

By: Benoit, Anne [author]Contributor(s): Robert, Yves [co-author] | Vivien, Frédérick [co-author]Material type: Text

TextSeries: Chapman & Hall/CRC Applied Algorithms and Data Structures seriesPublication details: Boca Raton : CRC Press, 2014Description: xvii, 362 pages : illustrations ; 24 cmISBN: 9781439825648Subject(s): COMPUTER ALGORITHMS | COMPUTATIONAL COMPLEXITYLOC classification: QA 76.9 .B46 2014

Contents:

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

Summary: Polynomial-Time Algorithms: Exercises Introduction to Complexity On the complexity to compute xnAsymptotic notations: O, o, Θ, and ΩDivide-and-Conquer Strassen's algorithm Master theorem Solving recurrencesGreedy Algorithms Motivating example: the sports hall Designing greedy algorithms Graph coloringTheory of matroidsDynamic Programming The coin changing problem The knapsack problem Designing dynamic-programming algorithmsAmortized AnalysisMethods for amortized analysisExercises, Solutions, and Bibliographic Notes appear at the end of each chapter in this section. NP-Completeness and Beyond NP.

Item type:

Books

Tags from this library: No tags from this library for this title. Log in to add tags.

Average rating: 0.0 (0 votes)

Holdings ( 1 )
Title notes ( 3 )
Comments ( 0 )

Item type	Current library	Home library	Collection	Shelving location	Call number	Copy number	Status	Date due	Barcode
Books	National University - Manila	National University - Manila	Computer Science	General Circulation	GC QA 76.9 .B46 2014 (Browse shelf (Opens below))	c.1	Available		NULIB000013749

Browsing National University - Manila shelves, Shelving location: General Circulation, Collection: Computer Science Close shelf browser (Hides shelf browser)

Previous								Next
Previous	GC QA 76.9 .A45 2010 Visual Basic and Access : visual guide /	GC QA 76.9 .A45 2017 Advanced penetration testing : hacking the world's most secure networks /	GC QA 76.9 .A76 2015 Analysis and design of algorithms /	GC QA 76.9 .B46 2014 A guide to algorithm design : paradigms, methods, and complexity analysis /	GC QA 76.9 .C66 2010 Database systems : a practical approach to design, implementation, and management /	GC QA 76.9 .C67 2011 Database Principles : fundamentals of design, implementation, and management /	GC QA 76.9 .C68 2012 Distributed systems : concepts and design /	Next

Includes bibliographical references and index.

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

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

Polynomial-Time Algorithms: Exercises Introduction to Complexity On the complexity to compute xnAsymptotic notations: O, o, Θ, and ΩDivide-and-Conquer Strassen's algorithm Master theorem Solving recurrencesGreedy Algorithms Motivating example: the sports hall Designing greedy algorithms Graph coloringTheory of matroidsDynamic Programming The coin changing problem The knapsack problem Designing dynamic-programming algorithmsAmortized AnalysisMethods for amortized analysisExercises, Solutions, and Bibliographic Notes appear at the end of each chapter in this section. NP-Completeness and Beyond NP.

There are no comments on this title.

to post a comment.