Algorithm Design

AvJon Kleinberg,Eva Tardos

Häftad, Engelska, 2005

3 513 kr

Beställningsvara. Skickas inom 3-6 vardagar. Fri frakt över 249 kr.

Fler format och utgåvor

Häftad

1 361 kr

Beskrivning

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

Utgivningsdatum:2005-05-04
Mått:210 x 240 x 34 mm
Vikt:1 570 g
Format:Häftad
Språk:Engelska
Antal sidor:864
Upplaga:1
Förlag:Pearson Education
ISBN:9780321295354

Utforska kategorier

Programmeringsböcker inom Data och IT

Innehållsförteckning

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

Betyg & recensioner

5/5

Mer från samma författare

Algorithm Design

Eva Tardos, Jon Kleinberg

E-bok

2013

797 kr

Networks, Crowds, and Markets

David Easley, Jon Kleinberg

Inbunden, 2010

838 kr

Networks, Crowds, and Markets

Jon Kleinberg, David Easley

E-bok

2010

975 kr

Networks, Crowds, and Markets

Jon Kleinberg, David Easley

E-bok

2010

975 kr

Programming Language Ada. Reference Manual

David Hutchison, Takeo Kanade, Josef Kittler, Jon Kleinberg, Alfred Kobsa, Friedemann Mattern, John C. Mitchell, Moni Naor, Oscar M. Nierstrasz, C. Pandu Rangan, Bernhard Steffen, Sudan Madhu, Demetri Terzopoulos, J. Doug Tygar, Gerhard Weikum