没有合适的资源?快使用搜索试试~ 我知道了~
Algorithm Design
需积分: 10 11 下载量 119 浏览量
2014-01-18
05:12:30
上传
评论
收藏 42.79MB PDF 举报
温馨提示
试读
432页
Algorithm Design By Jon Kleinberg, Eva Tardos 双开面的不太爽
资源推荐
资源详情
资源评论
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
2005000401
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
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
Introduction: Some Representative Problems
I. 1 A First Problem: Stable Matching,
1).
19
Exercises
Notes and Further Reading )‘8
2
Basics
2.1
2.2
2.3
2.4
2.5
of Algorithm Analysis
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
57
65
Exercises 67
Notes and Fm-ther Reading 70
3
Graphs
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
Connectivity in Directed Graphs 97
v
29
73
94
Contents
4
3.6
Directed Acyclic Graphs and Topological Ordering
104
Exercises 107
Notes and Further Reading 112
99
Greedy Algorithms
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
Huffman Codes and Data Compression 161
Minimum-Cost Arborescences: A Multi-Phase Greedy
Algorithm 177
183
Exercises 188
Notes and Further Reading 205
4.7
4.8
*4.9
116
125
131
5
Divide
5.1
5.2
5.3
5.4
5.5
5.6
and Conquer
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
209
6
2S1
6.1
Weighted Interval Scheduling: A Recursive Procedure 252
6.2
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.)
6.4
6.5
6.6
6.7
6.8
6.9
* 6.10
7
7.2
7.3
* 7.4
7.5
7.6
7.7
7.8
7.9
7.!0
7.11
7.12
"7.!3
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
Contents
337
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
373
378
Survey Design 384
Airline Scheduling 387
Image Segmentation 391
\
Baseball Elimination 400
Adding Costs to the Matching Problem,~) 404
A
Further Direction:
Solved Exercises 411
Exercises 415
Notes and Further Reading 448
451
459
8.1
Polynomial-Time Reductions 452
8.2
Reductions via "Gadgets": The Satisfiabflity Problem
8.3
Efficient Certification and the Definition of NP
463
8.4
NP-Complete Problems 466
8.5
Sequencing,,Problems 473
8.6
Partitioning Problems 481
8.7
Graph Coloring 485
剩余431页未读,继续阅读
资源评论
foressay
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功