Kleinberg - Algorithm Design (Pearson, 2006).pdf

(43807 KB) Pobierz
Cornell University
Boston San Francisco
NewYork
London Toronto Sydney Tokyo Singapore Madrid
Mexico City Munich Paris Cape Toxvn Hong Kong Montreal
Acquisitions Editor:
Matt Goldstein
Project Editor:
Maite Suarez-Rivus
Production Supervisor:
MariIyn Lloyd
Marketing Manager:
MichelIe Brown
Marketing Coordinator:
Yake Zavracky
Project Management:
Windfall Sofi-tvare
Composition:
Windfall Software, using ZzTEX
Copyeditor:
Carol Leyba
Technical Illustration:
Dartmouth Publishing
Proofreader:
Jennifer McClain
Indexer:
Ted Laux
Cover Design:
Yoyce Cosentino Wells
Cover Photo: © 2005
Tim Laman / National Geographic. A pair of weaverbirds work
together on their nest in Africa.
Prepress and Manufacturing:
Caroline Fell
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 / Jon Kleinberg, l~va Tardos.--lst ed.
p. cm.
Includes bibliographical references and index.
ISBN 0-321-29535-8 (alk. paper)
1. Computer algorithms. 2. Data structures (Computer science) I. Tardos, l~va.
II. Title.
QA76.9.A43K54 2005
005.1--dc22
Copyright © 2006 by Pearson Education, Inc.
For information on obtaining permission for use of material in this work, please
submit a written request to Pearson Education, 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
2005000401
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 Sloan Foundations,
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 Sloan Foundations, 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.
Contents
About the Authors
Preface
v
Introduction: Some Representative Problems
I. 1 A First Problem: Stable Matching,
1).
19
Exercises
Notes and Further Reading )‘8
2
Basics
of Algorithm Analysis
29
2.1
Computational Tractability 29
2.2
Asymptotic Order of Growth 35
2.3
Implementing the Stable Matching Algorithm Using Lists and
2.4
2.5
Arrays 42
A Survey of Common Running Times 47
57
65
Exercises 67
Notes and Fm-ther Reading 70
3
Graphs
73
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
Contents
Contents
6.4
6.5
6.6
6.7
6.8
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
Shortest Paths in a Graph 290
297
Negative Cycles in a Graph 301
307
Exercises 312
Notes and Further Reading 335
3.6
Directed Acyclic Graphs and Topological Ordering 99
104
Exercises 107
Notes and Further Reading 112
Interval Scheduling: The Greedy Algorithm Stays Ahead
116
Scheduling to Minimize Lateness: An Exchange Argument
125
Optimal Caching: A More Complex Exchange Argument
131
Shortest Paths in a Graph 137
The Minimum Spanning Tree ProbJem 142
Implementing Kruskal’s Algorithm: The Union-Find Data
Structure 151
Clustering 157
Huffman Codes and Data Compression 161
Minimum-Cost Arborescences: A Multi-Phase Greedy
Algorithm 177
183
Exercises 188
Notes and Further Reading 205
209
4
Greedy Algorithms
4.7
4.8
*4.9
7
The Maximum-Flow Problem and the Ford-FulkersOn
Algorithm 338
7.2
Maximum Flows and Minimum Cuts in a Network 346
7.3
Choosing Good Augmenting Paths 352
* 7.4
The Preflow-Push Maximum-Flow Algorithm:, 357
7.5
A First Application: The Bipartite Matching Problem 367
7.6
373
7.7
378
7.8
Survey Design 384
7.9
Airline Scheduling 387
7.!0
Image Segmentation 391
\
7.11
337
5
Divide
and Conquer
5.1
5.2
5.3
5.4
5.5
5.6
A First Recurrence: The Mergesort Algorithm 210
Further Recurrence Relations 214
Counting Inversions 221
Finding the Closest Pair of Points 225
Integer Multiplication 231
234
242
Exercises 246
Notes and Further Reading 249
7.12
Baseball Elimination 400
"7.!3
A Further Direction: Adding Costs to the Matching Problem,~) 404
Solved Exercises 411
Exercises 415
Notes and Further Reading 448
2S1
451
8.1
8.2
8.3
8.4
8.5
8.6
8.7
Polynomial-Time Reductions 452
Reductions via "Gadgets": The Satisfiabflity Problem
459
Efficient Certification and the Definition of NP 463
NP-Complete Problems 466
Sequencing,,Problems 473
Partitioning Problems 481
Graph Coloring 485
6
6.1
6.2
Weighted Interval Scheduling: A Recursive Procedure 252
Principles of Dynamic Programming: Memoization or Iteration
over Subproblems 258
6.3 Segmented Least Squares: Multi-way Choices 26~
* The star indicates an optional section. (See the Preface for more information about the relationships
among the chapters and sections.)

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin