Cornell University
Boston San Francisco NewYork
London Toronto Sydney Tokyo Singapore Madrid
Mexico City Munich Paris Cape Toxvn Hong Kong Montreal
Copyright By PowCoder代写 加微信 powcoder
Acquisitions Editor: Project Editor: -Rivus Production Supervisor: MariIyn Lloyd Marketing Manager: MichelIe Brown Marketing Coordinator:
Project Management: Windfall Sofi-tvare Composition: Windfall Software, using ZzTEX
Copyeditor:
Technical Illustration: Dartmouth Publishing
Proofreader: Clain
Cover Design: Wells
Cover Photo: © 2005 / National Geographic. A pair of weaverbirds work
together on their nest in Africa. Prepress and Manufacturing:
Printer: Courier West~ord
Access the latest information about Addison-Wesley rifles from our World Wide Web
site: http://www.aw-bc.com/computing
Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been
printed in initial caps or all caps.
The programs and applications presented in this book have been included for their instructional value. They have been tested with care, but are not guaranteed for any
particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs or applications.
Library of Congress Cataloging-in-Publication Data
Kleinberg, Jon.
Algorithm design / , l~va Tardos.–lst ed.
Includes bibliographical references and index.
ISBN 0-321-29535-8 (alk. paper)
1. Computer algorithms. 2. Data structures (Computer science) I. Tardos, l~va.
About the Authors
3on Kleinberg is a professor of Computer Science at Cornell University. He received his Ph.D. from M.I.T. in 1996. He is the recipient of an NSF Career Award, an ONR Young Investigator Award, an IBM Outstand- ing Innovation Award, the National Academy of Sci- ences Award for Initiatives in Research, research fel- lowships from the Packard and , and teaching awards from the Cornell Engineering College and Computer Science Department.
Kleinberg’s research is centered around algorithms, particularly those con- cerned with the structure of networks and information, and with applications
to information science, optimization, data mining, and computational biol- ogy. His work on network analysis using hubs and authorities helped form the
foundation for the current generation of Internet search engines.
fiva Tardos is a professor of Computer Science at Cor- nell University. She received her Ph.D. from E6tv6s University in Budapest, Hungary in 1984. She is a member of the American Academy of Arts and Sci- ences, and an ACM Fellow; she is the recipient of an NSF Presidential Young Investigator Award, the Fulk- erson Prize, research fellowships from the Guggen- helm, Packard, and , and teach- ing awards from the Cornell Engineering College and
Computer Science Department.
Tardos’s research interests are focused on the design and analysis of algorithms for problems on graphs or networks. She is most known for her work on network-flow algorithms and approximation algorithms for network problems. Her recent work focuses on algorithmic game theory, an emerging area concerned with designing systems and algorithms for selfish users.
II. Title.
QA76.9.A43K54 2005 005.1–dc22
Copyright © 2006 by , Inc.
2005000401
For information on obtaining permission for use of material in this work, please submit a written request to , Inc., Rights and Contract Department, 75 Arlington Street, Suite 300, Boston, MA 02116 or fax your request to (617) 848-7047.
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or any toher media embodiments now known or hereafter to become known, without the prior written permission of the publisher. Printed in the
United States of America.
ISBN 0-321-29535-8
2 3 4 5 6 7 8 9 10-CRW-08 07 06 05
About the Authors v Preface
Introduction: Some Representative Problems
I. 1 A First Problem: Stable Matching, 1).
Notes and Further Reading )‘8
2 Basics of Algorithm Analysis 29
2.1 2.2 2.3
Computational Tractability 29
Asymptotic Order of Growth 35
Implementing the Stable Matching Algorithm Using Lists and Arrays 42
A Survey of Common Running Times 47
Notes and Fm-ther Reading 70
Exercises 67
Basic Definitions and Applications 73
Graph Connectivity and Graph Traversal 78
Implementing Graph Traversal Using Queues and Stacks 87 Testing Bipartiteness: An Application of Breadth-First Search 94 Connectivity in Directed Graphs 97
3.6 Directed Acyclic Graphs and Topological Ordering 99 104
Exercises 107
Notes and Further Reading 112
Greedy Algorithms
6.9 * 6.10
Subset Sums and Knapsacks: Adding a.,~able 266
RNA Secondary Structure: Dynarmc~gramming over Intervals 272
Sequence Alignment 278
Sequence Alignment in Linear Space via Divide and Conquer 284
7.3 * 7.4 7.5 7.6 7.7 7.8 7.9
7.!0 7.11 7.12
8.1 8.2 8.3 8.4 8.5 8.6 8.7
The Maximum-Flow Problem and the Ford-FulkersOn Algorithm 338
Maximum Flows and Minimum Cuts in a Network 346 Choosing Good Augmenting Paths 352
The Preflow-Push Maximum-Flow Algorithm:, 357
A First Application: The Bipartite Matching Problem 367
Interval Scheduling: The Greedy Algorithm Stays Ahead Scheduling to Minimize Lateness: An Exchange Argument Optimal Caching: A More Complex Exchange Argument Shortest Paths in a Graph 137
The Minimum Spanning Tree ProbJem 142 Implementing Kruskal’s Algorithm: The Union-Find Data Structure 151
Clustering 157
and Data Compression 161 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm 177
Exercises 188
Notes and Further Reading 205
5 Divide and Conquer
5.1 5.2 5.3
5.4 5.5 5.6
* The star indicates an optional section. (See the Preface for more information about the relationships among the chapters and sections.)
Survey Design 384
Airline Scheduling 387 Image Segmentation 391
Weighted Interval Scheduling: A Recursive Procedure 252
A First Recurrence: The Mergesort Algorithm 210 Further Recurrence Relations 214
Counting Inversions 221
Finding the Closest Pair of Points 225
Integer Multiplication 231 242
Exercises 246
Notes and Further Reading 249
Baseball Elimination 400
A Further Direction:Adding Costs to the Matching Problem,~) 404
Principles of Dynamic Programming: Memoization or Iteration
over Subproblems 258
6.3 Segmented Least Squares: Multi-way Choices 26~
Shortest Paths in a Graph 290
Negative Cycles in a Graph 301 307
Exercises 312
Notes and Further Reading 335
Solved Exercises 411 Exercises 415
Notes and Further Reading 448
Polynomial-Time Reductions 452
Reductions via “Gadgets”: The Satisfiabflity Problem Efficient Certification and the Definition of NP 463 NP-Complete Problems 466 Sequencing,,Problems 473
Partitioning Problems 481
Graph Coloring 485
12.1 12.2 12.3 12.4 12.5 12.6 12.7
The Landscape of an Optimization Problem 662
The Metropolis Algorithm and Simulated Annealing 666 An Application of Local Se_arch to Hopfield Neural Networks
13.1 A First Application: Contention Resolution 708
13.2 Finding the Global Minimum Cut 714
13.3 Random Variables and Their Expectations 719
13.4 A Randomized Approximation Algorithm for MAX 3-SAT 724
13.5 Randomized Divide and Conquer: Median-Finding and
Quicksort 727
13.6 Hashing: A Randomized Implementation of Dictionaries 734
13.7 Finding the Closest Pair of Points: A Randomized Approach 741
13.8 Randomized Caching 750
13.9 Chernoff Bounds 758
13.10 Load Balancing 760
13.1! Packet Routing 762
13.12 Background: Some Basic ProbabiLity Definitions 769
Approximation Algorithms
8.8 Numerical Problems 490
8.9 Co-NP and the Asymmetry of NP 495
8.10 A Partial Taxonomy of Hard Problems 497
Arbitrarily Good Approximations: The Knapsack Problem 644 649
Exercises 651
Notes and Further Reading 659
Notes and Further Reading 529
PSPACE: A Class of Problems beyond NP PSPACE 531
Some Hard Problems in PSPACE 533
Solving Quantified Problems and Games in Polynomia! Space 536
9.4 Solving the Planning Problem in Polynomial Space 538 543
Exercises 550
Notes and Further Reading 551
Extending the Limits of Tractability
10.! 10.2 10.3
* 10.4 * 10.5
Finding Smal! Vertex Covers 554 Solving NP-Hard Problems on Trees 558
Exercises 505
Coloring a Set of Circular Arcs 563 Tree Decompositions of Graphs 572
Notes and Further Reading 598
Exercises 594
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem 600
Notes and Further Reading 793
11.3 11.4 11.5
11.6 * 11.7
The Pricing Method: Vertex Cover 618
Maximization via the Pricing Method: The Disioint Paths Problem 624
Linear Programming and Rounding: An Application to Vertex Cover 630
Load Balancing Revisited: A More Advanced LP Application 637
795 805 815
Set Cover: A General Greedy Heuristic 612
Exercises 782
12LocalSearch 661
Choosing a Neighbor Relation 679 Classification via Local Search 681
Notes and Further Reading 705
Exercises 702
Algorithmic !deas are pervasive, and their reach is apparent in examples both within computer science and beyond. Some of the major shifts in Internet
routing standards can be viewed as debates over the deficiencies of one shortest-path algorithm and the relative advantages of another. The basic
notions used by biologists to express similarities among genes and genomes have algorithmic definitions. The concerns voiced by economists over the feasibility of combinatorial auctions in practice are rooted partly in the fact that these auctions contain computationally intractable search problems as special cases. And algorithmic notions aren’t just restricted to well-known and long- standing problems; one sees the reflections of these ideas on a regular basis, in novel issues arising across a wide range of areas. The scientist from Yahoo! who told us over lunch one day about their system for serving ads to users was describing a set of issues that, deep down, could be modeled as a network flow problem. So was the former student, now a management consultant working on staffing protocols for large hospitals, whom we happened to meet on a trip to City.
The point is not simply that algorithms have many applications. The deeper issue is that the subject of algorithms is a powerful lens through which to view the field of computer science in general. Algorithmic problems form the heart of computer science, but they rarely arrive as cleanly packaged, mathematically precise questions. Rather, they tend to come bundled together with lots of messy, application-specific detail, some of,it essential, some of it extraneous. As a result, the algorithmic enterprise consists of two fundamental components: the task of getting to the mathematically clean core of a problem, and then the task of identifying the appropriate algorithm design techniques, based on the structure of the problem. These two components interact: the more comfortable one is with the full array of possible design techniques, the more one starts to recognize the clean formulations that lie within messy
problems out in the world. At their most effective, then, algorithmic ideas do
not just provide solutions to _well-posed problems; they form the language that lets you cleanly express the underlying questions.
The goal of our book is to convey this approach to algorithms, as a design process that begins with problems arising across the full range of computing applications, builds on an understanding of algorithm design techniques, and results in the development of efficient solutions to these problems. We seek to explore the role of algorithmic ideas in computer science generally, and relate these ideas to the range of precisely formulated problems for which we can design and analyze algorithms. In other words, what are the underlying issues that motivate these problems, and how did we choose these particular ways of formulating them? How did we recognize which design principles were appropriate in different situations?
In keeping with this, our goal is to offer advice on how to identify clean algorithmic problem formulations in complex issues from different areas of computing and, from this, how to design efficient algorithms for the resulting problems. Sophisticated algorithms are often best understood by reconstruct- ing the sequence of ideas–including false starts and dead ends–that led from simpler initial approaches to the eventual solution. The result is a style of ex- position that does not take the most direct route from problem statement to algorithm, but we feel it better reflects the way that we and our colleagues genuinely think about these questions.
The book is intended for students who have completed a programming- based two-semester introductory computer science sequence (the standard
“CS1/CS2” courses) in which they have written programs that implement basic algorithms, manipulate discrete structures such as trees and graphs, and apply basic data structures such as arrays, lists, queues, and stacks. Since the interface between CS1/CS2 and a first algorithms course is not entirely
standard, we begin the book with self-contained coverage of topics that at
some institutions a_re familiar to students from CS1/CS2, but which at other institutions are included in the syllabi of the first algorithms course. This material can thus be treated either as a review or as new material; by including it, we hope the book can be used in a broader array of courses, and with more flexibility in the prerequisite knowiedge that is assumed.
In keeping with the approach outlined above, we develop the basic algo- rithm design techniques by drawing on problems from across many areas of
computer science and related fields. To mention a few representative examples here, we include fairly detailed discussions of applications from systems and networks (caching, switching, interdomain routing on the Internet), artificial
intelligence (planning, game playing, Hopfield networks), computer vision (image segmentation), data mining (change-point detection, clustering), op-
erations research (airline scheduling), and computational biology (sequence alignment, RNA secondary structure).
The notion of computational intractability, and NP-completeness in par- ticular, plays a large role in the book. This is consistent with how we think about the overall process of algorithm design. Some of the time, an interest- ing problem arising in an application area will be amenable to an efficient solution, and some of the time it will be provably NP-complete; in order to fully address a new algorithmic problem, one should be able to explore both of these ol)tions with equal familiarity. Since so many natural problems in computer science are NP-complete, the development of methods to deal with intractable problems has become a crucial issue in the study of algorithms, and our book heavily reflects this theme. The discovery that a problem is NP- complete should not be taken as the end of the story, but as an invitation to begin looking for approximation algorithms, heuristic local search techniques, or tractable special cases. We include extensive coverage of each of these three approaches.
Problems and Solved Exercises
An important feature of the book is the collection of problems. Across all chapters, the book includes over 200 problems, almost a!l of them developed and class-tested in homework or exams as part of our teaching of the course
at Cornell. We view the problems as a crucial component of the book, and they are structured in keeping with our overall approach to the material. Most of them consist of extended verbal descriptions of a problem arising in an application area in computer science or elsewhere out in the world, and part of the problem is to practice what we discuss in the text: setting up the necessary notation and formalization, designing an algorithm, and then analyzing it and proving it correct. (We view a complete answer to one of these problems as consisting of all these components: a fl~y explained algorithm, an analysis of the nmning time, and a proof of correctness.) The ideas for these problems come in large part from discussions we have had over the years with people working in different areas, and in some cases they serve the dual purpose of recording an interesting (though manageable) application of algorithms that we haven’t seen written down anywhere else.
To help with the process of working on these problems, we include in
each chapter a section entitled “Solved Exercises,” where we take one or more problems and describe how to go about formulating a solution. The discussion devoted to each solved exercise is therefore significantly longer than what would be needed simply to write a complete, correct solution (in other words,
Preface xvii
significantly longer than what it would take to receive full credit if these were being assigned as homework problems). Rather, as with the rest of the text, the discussions in these sections should be viewed as trying to give a sense of the larger process by which one might think about problems of this type, culminating in the speci.fication of a precise solution.
It is worth mentioning two points concerning the use of these problems as homework in a course. First, the problems are sequenced roughly in order of increasing difficulty, but this is only an approximate guide and we advise against placing too much weight on it: since the bulk of the problems were designed as homework for our undergraduate class, large subsets of the problems in each chapter are really closely comparable in terms of difficulty. Second, aside from the lowest-numbered ones, the problems are designed to involve some investment of time, both to relate the problem description to the algorithmic techniques in the chapter, and then to actually design the necessary algorithm. In our undergraduate class, we have tended to assign roughly three of these problems per week.
Pedagogical Features and Supplements
In addition to the Problems and solved exercises, the book has a number of further pedagogical features, as well as additional supplements to facilitate its
use for teaching.
As noted earlier, a large number of the sections in the book axe devoted to the formulation of an algorithmic problem–including its background and underlying motivation–and the design and analysis of an algorithm for this problem. To reflect this style, these sections are consistently structured around a sequence of subsections: “The Problem,” where the problem is described and a precise formulation is worked out; “Designing the Algorithm,” where the appropriate design technique is employed to develop an algorithm; and “Analyzing the Algorithm,” which proves properties of the algorithm and analyzes its efficiency. These subsections are highlighted in the text with an icon depicting a feather. In cases where extensions to the problem or further analysis of the algorithm is pursued, there are additional subsections devoted to these issues. The goal of this structure is to offer a relatively uniform style of presentation that moves from the initial discussion of a problem arising in a computing application through to the detailed analysis of a method to solve it.
A number of supplements are available in support of the book itself. An instructor’s manual works through al! the problems, providing fi~ solutions to
each. A set of lecture
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com