Algorithm Design

Häftad, Engelska, 2005

Av Jon Kleinberg, Eva Tardos

4 499 kr

Beställningsvara. Skickas inom 3-6 vardagar

Fri frakt för medlemmar vid köp för minst 249 kr.

Finns i fler format (1)

Häftad

1 689 kr

Skickas inom 7-10 vardagar

Algorithm Design introduces algorithms by looking at the real-world problems that motivate them. The book teaches students a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

August 6, 2009 Author, Jon Kleinberg, was recently cited in the New York Times for his statistical analysis research in the Internet age.

Produktinformation

Utgivningsdatum2005-05-04
Mått210 x 240 x 34 mm
Vikt1 570 g
FormatHäftad
SpråkEngelska
Antal sidor864
Upplaga1
FörlagPearson Education
ISBN9780321295354

Tillhör följande kategorier

Programmeringsböcker inom Data och it

Table of Contents Algorithm Design Jon Kleinberg and Eva Tardos Introduction: Some Representative Problems 1.1 A First Problem: Stable Matching1.2 Five Representative ProblemsSolved ExercisesExcercisesNotes and Further ReadingBasics of Algorithms Analysis 2.1 Computational Tractability2.2 Asymptotic Order of Growth Notation2.3 Implementing the Stable Matching Algorithm using Lists and Arrays2.4 A Survey of Common Running Times2.5 A More Complex Data Structure: Priority QueuesSolved ExercisesExercisesNotes and Further ReadingGraphs 3.1 Basic Definitions and Applications3.2 Graph Connectivity and Graph Traversal3.3 Implementing Graph Traversal using Queues and Stacks3.4 Testing Bipartiteness: An Application of Breadth-First Search3.5 Connectivity in Directed Graphs3.6 Directed Acyclic Graphs and Topological OrderingSolved ExercisesExercisesNotes and Further ReadingGreedy Algorithms 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead4.2 Scheduling to Minimize Lateness: An Exchange Argument4.3 Optimal Caching: A More Complex Exchange Argument4.4 Shortest Paths in a Graph4.5 The Minimum Spanning Tree Problem4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure4.7 Clustering4.8 Huffman Codes and the Problem of Data Compression*4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy AlgorithmSolved ExercisesExcercisesNotes and Further ReadingDivide and Conquer 5.1 A First Recurrence: The Mergesort Algorithm5.2 Further Recurrence Relations5.3 Counting Inversions5.4 Finding the Closest Pair of Points5.5 Integer Multiplication5.6 Convolutions and The Fast Fourier TransformSolved ExercisesExercisesNotes and Further ReadingDynamic Programming 6.1 Weighted Interval Scheduling: A Recursive Procedure6.2 Weighted Interval Scheduling: Iterating over Sub-Problems6.3 Segmented Least Squares: Multi-way Choices6.4 Subset Sums and Knapsacks: Adding a Variable6.5 RNA Secondary Structure: Dynamic Programming Over Intervals6.6 Sequence Alignment6.7 Sequence Alignment in Linear Space6.8 Shortest Paths in a Graph6.9 Shortest Paths and Distance Vector Protocols*6.10 Negative Cycles in a GraphSolved ExercisesExercisesNotes and Further ReadingNetwork Flow 7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm7.2 Maximum Flows and Minimum Cuts in a Network7.3 Choosing Good Augmenting Paths*7.4 The Preflow-Push Maximum Flow Algorithm7.5 A First Application: The Bipartite Matching Problem7.6 Disjoint Paths in Directed and Undirected Graphs7.7 Extensions to the Maximum Flow Problem7.8 Survey Design7.9 Airline Scheduling7.10 Image Segmentation7.11 Project Selection7.12 Baseball Elimination*7.13 A Further Direction: Adding Costs to the Matching ProblemSolved ExercisesExercisesNotes and Further ReadingNP and Computational Intractability 8.1 Polynomial-Time Reductions8.2 Reductions via "Gadgets": The Satisfiability Problem8.3 Efficient Certification and the Definition of NP8.4 NP-Complete Problems8.5 Sequencing Problems8.6 Partitioning Problems8.7 Graph Coloring8.8 Numerical Problems8.9 Co-NP and the Asymmetry of NP8.10 A Partial Taxonomy of Hard ProblemsSolved ExercisesExercisesNotes and Further ReadingPSPACE: A Class of Problems Beyond NP 9.1 PSPACE9.2 Some Hard Problems in PSPACE9.3 Solving Quantified Problems and Games in Polynomial Space9.4 Solving the Planning Problem in Polynomial Space9.5 Proving Problems PSPACE-CompleteSolved ExercisesExercisesNotes and Further ReadingExtending the Limits of Tractability 10.1 Finding Small Vertex Covers10.2 Solving NP-Hard Problem on Trees10.3 Coloring a Set of Circular Arcs*10.4 Tree Decompositions of Graphs*10.5 Constructing a Tree DecompositionSolved ExercisesExercisesNotes and Further ReadingApproximation Algorithms 11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem11.2 The Center Selection Problem11.3 Set Cover: A General Greedy Heuristic11.4 The Pricing Method: Vertex Cover11.5 Maximization via the Pricing method: The Disjoint Paths Problem11.6 Linear Programming and Rounding: An Application to Vertex Cover*11.7 Load Balancing Revisited: A More Advanced LP Application11.8 Arbitrarily Good Approximations: the Knapsack ProblemSolved ExercisesExercisesNotes and Further ReadingLocal Search 12.1 The Landscape of an Optimization Problem12.2 The Metropolis Algorithm and Simulated Annealing12.3 An Application of Local Search to Hopfield Neural Networks12.4 Maximum Cut Approximation via Local Search12.5 Choosing a Neighbor Relation*12.6 Classification via Local Search12.7 Best-Response Dynamics and Nash EquilibriaSolved ExercisesExercisesNotes and Further ReadingRandomized Algorithms 13.1 A First Application: Contention Resolution13.2 Finding the Global Minimum Cut13.3 Random Variables and their Expectations13.4 A Randomized Approximation Algorithm for MAX 3-SAT13.5 Randomized Divide-and-Conquer: Median-Finding and Quicksort13.6 Hashing: A Randomized Implementation of Dictionaries13.7 Finding the Closest Pair of Points: A Randomized Approach13.8 Randomized Caching13.9 Chernoff Bounds13.10 Load Balancing*13.11 Packet Routing13.12 Background: Some Basic Probability DefinitionsSolved ExercisesExercisesNotes and Further ReadingEpilogue: Algorithms that Run Forever References Index