Algorithm Design,9780321295354

Algorithm Design

by ;
Edition: 1st
ISBN13: 9780321295354
ISBN10: 0321295358
Format: Paperback
Pub. Date: 2005-03-16
Publisher(s): Pearson
  • Complimentary 7-Day eTextbook Access - Read more
    When you rent or buy this book, you will receive complimentary 7-day online access to the eTextbook version from your PC, Mac, tablet, or smartphone. Feature not included on Marketplace Items.
List Price: $226.65

Buy New

In Stock
$225.52
Add to Cart

Buy Used

Usually Ships in 24-48 Hours
$170.81
Add to Cart

Rent Textbook

Select for Price
Add to Cart
There was a problem. Please try again later.

Rent Digital

Rent Digital Options
Online:1825 Days access
Downloadable:Lifetime Access
$113.99
*To support the delivery of the digital material to you, a digital delivery fee of $3.99 will be charged on each digital item.
$113.99*
Add to Cart
Buy from our Marketplace starting at $61.87

How Marketplace Works:

  • This item is offered by an independent seller and not shipped from our warehouse
  • Item details like edition and cover design may differ from our description; see seller's comments before ordering.
  • Sellers much confirm and ship within two business days; otherwise, the order will be cancelled and refunded.
  • Marketplace purchases cannot be returned to eCampus.com. Contact the seller directly for inquiries; if no response within two days, contact customer service.
  • Additional shipping costs apply to Marketplace purchases. Review shipping costs at checkout.

Summary

Algorithm Designintroduces algorithms by looking at the real-world problems that motivate them. The book teaches 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.

Author Biography

Eva Tardos is a professor of Computer Science at Cornell University.

Table of Contents

About the Authors v
Preface xiii
Introduction: Some Representative Problems
1(28)
A First Problem: Stable Matching
1(11)
Five Representative Problems
12(17)
Solved Exercises
19(3)
Exercises
22(6)
Notes and Further Reading
28(1)
Basics of Algorithm Analysis
29(44)
Computational Tractability
29(6)
Asymptotic Order of Growth
35(7)
Implementing the Stable Matching Algorithm Using Lists and Arrays
42(5)
A Survey of Common Running Times
47(10)
A More Complex Data Structure: Priority Queues
57(16)
Solved Exercises
65(2)
Exercises
67(3)
Notes and Further Reading
70(3)
Graphs
73(42)
Basic Definitions and Applications
73(5)
Graph Connectivity and Graph Traversal
78(9)
Implementing Graph Traversal Using Queues and Stacks
87(7)
Testing Bipartiteness: An Application of Breadth-First Search
94(3)
Connectivity in Directed Graphs
97(2)
Directed Acyclic Graphs and Topological Ordering
99(16)
Solved Exercises
104(3)
Exercises
107(5)
Notes and Further Reading
112(3)
Greedy Algorithms
115(94)
Interval Scheduling: The Greedy Algorithm Stays Ahead
116(9)
Scheduling to Minimize Lateness: An Exchange Argument
125(6)
Optimal Caching: A More Complex Exchange Argument
131(6)
Shortest Paths in a Graph
137(5)
The Minimum Spanning Tree Problem
142(9)
Implementing Kruskal's Algorithm: The Union-Find Data Structure
151(6)
Clustering
157(4)
Huffman Codes and Data Compression
161(16)
Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm
177(32)
Solved Exercises
183(5)
Exercises
188(17)
Notes and Further Reading
205(4)
Divide and Conquer
209(42)
A First Recurrence: The Mergesort Algorithm
210(4)
Further Recurrence Relations
214(7)
Counting Inversions
221(4)
Finding the Closest Pair of Points
225(6)
Integer Multiplication
231(3)
Convolutions and the Fast Fourier Transform
234(17)
Solved Exercises
242(4)
Exercises
246(3)
Notes and Further Reading
249(2)
Dynamic Programming
251(86)
Weighted Interval Scheduling: A Recursive Procedure
252(6)
Principles of Dynamic Programming: Memoization or Iteration over Subproblems
258(3)
Segmented Least Squares: Multi-way Choices
261(5)
Subset Sums and Knapsacks: Adding a Variable
266(6)
RNA Secondary Structure: Dynamic Programming over Intervals
272(6)
Sequence Alignment
278(6)
Sequence Alignment in Linear Space via Divide and Conquer
284(6)
Shortest Paths in a Graph
290(7)
Shortest Paths and Distance Vector Protocols
297(4)
Negative Cycles in a Graph
301(36)
Solved Exercises
307(5)
Exercises
312(23)
Notes and Further Reading
335(2)
Network Flow
337(114)
The Maximum-Flow Problem and the Ford-Fulkerson Algorithm
338(8)
Maximum Flows and Minimum Cuts in a Network
346(6)
Choosing Good Augmenting Paths
352(5)
The Preflow-Push Maximum-Flow Algorithm
357(10)
A First Application: The Bipartite Matching Problem
367(6)
Disjoint Paths in Directed and Undirected Graphs
373(5)
Extensions to the Maximum-Flow Problem
378(6)
Survey Design
384(3)
Airline Scheduling
387(4)
Image Segmentation
391(5)
Project Selection
396(4)
Baseball Elimination
400(4)
A Further Direction: Adding Costs to the Matching Problem
404(47)
Solved Exercises
411(4)
Exercises
415(33)
Notes and Further Reading
448(3)
NP and Computational Intractability
451(80)
Polynomial-Time Reductions
452(7)
Reductions via ``Gadgets'': The Satisfiability Problem
459(4)
Efficient Certification and the Definition of NP
463(3)
NP-Complete Problems
466(7)
Sequencing Problems
473(8)
Partitioning Problems
481(4)
Graph Coloring
485(5)
Numerical Problems
490(5)
Co-NP and the Asymmetry of NP
495(2)
A Partial Taxonomy of Hard Problems
497(34)
Solved Exercises
500(5)
Exercises
505(24)
Notes and Further Reading
529(2)
Pspace: A Class of Problems beyond NP
531(22)
Pspace
531(2)
Some Hard Problems in Pspace
533(3)
Solving Quantified Problems and Games in Polynomial Space
536(2)
Solving the Planning Problem in Polynomial Space
538(5)
Proving Problems Pspace-Complete
543(10)
Solved Exercises
547(3)
Exercises
550(1)
Notes and Further Reading
551(2)
Extending the Limits of Tractability
553(46)
Finding Small Vertex Covers
554(4)
Solving NP-Hard Problems on Trees
558(5)
Coloring a Set of Circular Arcs
563(9)
Tree Decompositions of Graphs
572(12)
Constructing a Tree Decomposition
584(15)
Solved Exercises
591(3)
Exercises
594(4)
Notes and Further Reading
598(1)
Approximation Algorithms
599(62)
Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem
600(6)
The Center Selection Problem
606(6)
Set Cover: A General Greedy Heuristic
612(6)
The Pricing Method: Vertex Cover
618(6)
Maximization via the Pricing Method: The Disjoint Paths Problem
624(6)
Linear Programming and Rounding: An Application to Vertex Cover
630(7)
Load Balancing Revisited: A More Advanced LP Application
637(7)
Arbitrarily Good Approximations: The Knapsack Problem
644(17)
Solved Exercises
649(2)
Exercises
651(8)
Notes and Further Reading
659(2)
Local Search
661(46)
The Landscape of an Optimization Problem
662(4)
The Metropolis Algorithm and Simulated Annealing
666(5)
An Application of Local Search to Hopfield Neural Networks
671(5)
Maximum-Cut Approximation via Local Search
676(3)
Choosing a Neighbor Relation
679(2)
Classification via Local Search
681(9)
Best-Response Dynamics and Nash Equilibria
690(17)
Solved Exercises
700(2)
Exercises
702(3)
Notes and Further Reading
705(2)
Randomized Algorithms
707(88)
A First Application: Contention Resolution
708(6)
Finding the Global Minimum Cut
714(5)
Random Variables and Their Expectations
719(5)
A Randomized Approximation Algorithm for MAX 3-SAT
724(3)
Randomized Divide and Conquer: Median-Finding and Quicksort
727(7)
Hashing: A Randomized Implementation of Dictionaries
734(7)
Finding the Closest Pair of Points: A Randomized Approach
741(9)
Randomized Caching
750(8)
Chernoff Bounds
758(2)
Load Balancing
760(2)
Packet Routing
762(7)
Background: Some Basic Probability Definitions
769(26)
Solved Exercises
776(6)
Exercises
782(11)
Notes and Further Reading
793(2)
Epilogue: Algorithms That Run Forever 795(10)
References 805(10)
Index 815

An electronic version of this book is available through VitalSource.

This book is viewable on PC, Mac, iPhone, iPad, iPod Touch, and most smartphones.

By purchasing, you will be able to view this book online, as well as download it, for the chosen number of days.

Digital License

You are licensing a digital product for a set duration. Durations are set forth in the product description, with "Lifetime" typically meaning five (5) years of online access and permanent download to a supported device. All licenses are non-transferable.

More details can be found here.

A downloadable version of this book is available through the eCampus Reader or compatible Adobe readers.

Applications are available on iOS, Android, PC, Mac, and Windows Mobile platforms.

Please view the compatibility matrix prior to purchase.