Algorithm Design.pdf

发布时间：2022-06-08 发布人：admin 分类：说明书资料大小：5.84M 资料格式：pdf 举报版权申诉

第1页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第2页.png

第2页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第3页.png

第3页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第4页.png

第4页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第5页.png

第5页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第6页.png

第6页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第7页.png

第7页 / 共864页

u013668028-6923881-570 Algorithm Design.pdf-第8页.png

第8页 / 共864页

Cover

Title Page

Contents

About the Authors

Preface

Acknowledgments

1 Introduction: Some Representative Problems

1.1 A First Problem: Stable Matching

1.2 Five Representative Problems

Solved Exercises

Exercises

Notes and Further Reading

2 Basics of Algorithm Analysis

2.1 Computational Tractability

2.2 Asymptotic Order of Growth

2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays

2.4 A Survey of Common Running Times

2.5 A More Complex Data Structure: Priority Queues

Solved Exercises

Exercises

Notes and Further Reading

3 Graphs

3.1 Basic Definitions and Applications

3.2 Graph Connectivity and Graph Traversal

3.3 Implementing Graph Traversal Using Queues and Stacks

3.4 Testing Bipartiteness: An Application of Breadth-First Search

3.5 Connectivity in Directed Graphs

3.6 Directed Acyclic Graphs and Topological Ordering

Solved Exercises

Exercises

Notes and Further Reading

4 Greedy Algorithms

4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead

4.2 Scheduling to Minimize Lateness: An Exchange Argument

4.3 Optimal Caching: A More Complex Exchange Argument

4.4 Shortest Paths in a Graph

4.5 The Minimum Spanning Tree Problem

4.6 Implementing Kruskal?s Algorithm: The Union-Find Data Structure

4.7 Clustering

4.8 Huffman Codes and Data Compression

*4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm

Solved Exercises

Exercises

Notes and Further Reading

5 Divide and Conquer

5.1 A First Recurrence: The Mergesort Algorithm

5.2 Further Recurrence Relations

5.3 Counting Inversions

5.4 Finding the Closest Pair of Points

5.5 Integer Multiplication

5.6 Convolutions and the Fast Fourier Transform

Solved Exercises

Exercises

Notes and Further Reading

6 Dynamic Programming

6.1 Weighted Interval Scheduling: A Recursive Procedure

6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems

6.3 Segmented Least Squares: Multi-way Choices

6.4 Subset Sums and Knapsacks: Adding a Variable

6.5 RNA Secondary Structure: Dynamic Programming over Intervals

6.6 Sequence Alignment

6.7 Sequence Alignment in Linear Space via Divide and Conquer

6.8 Shortest Paths in a Graph

6.9 Shortest Paths and Distance Vector Protocols

*6.10 Negative Cycles in a Graph

Solved Exercises

Exercises

Notes and Further Reading

7 Network Flow

7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

7.2 Maximum Flows and Minimum Cuts in a Network

7.3 Choosing Good Augmenting Paths

*7.4 The Preflow-Push Maximum-Flow Algorithm

7.5 A First Application: The Bipartite Matching Problem

7.6 Disjoint Paths in Directed and Undirected Graphs

7.7 Extensions to the Maximum-Flow Problem

7.8 Survey Design

7.9 Airline Scheduling

7.10 Image Segmentation

7.11 Project Selection

7.12 Baseball Elimination

*7.13 A Further Direction: Adding Costs to the Matching Problem

Solved Exercises

Exercises

Notes and Further Reading

8 NP and Computational Intractability

8.1 Polynomial-Time Reductions

8.2 Reductions via ?Gadgets?: The Satisfiability Problem

8.3 Efficient Certification and the Definition of NP

8.4 NP-Complete Problems

8.5 Sequencing Problems

8.6 Partitioning Problems

8.7 Graph Coloring

8.8 Numerical Problems

8.9 Co-NP and the Asymmetry of NP

8.10 A Partial Taxonomy of Hard Problems

Solved Exercises

Exercises

Notes and Further Reading

9 PSPACE: A Class of Problems beyond NP

9.1 PSPACE

9.2 Some Hard Problems in PSPACE

9.3 Solving Quanti.ed Problems and Games in Polynomial Space

9.4 Solving the Planning Problem in Polynomial Space

9.5 Proving Problems PSPACE-Complete

Solved Exercises

Exercises

Notes and Further Reading

10 Extending the Limits of Tractability

10.1 Finding Small Vertex Covers

10.2 Solving NP-Hard Problems on Trees

10.3 Coloring a Set of Circular Arcs

*10.4 Tree Decompositions of Graphs

*10.5 Constructing a Tree Decomposition

Solved Exercises

Exercises

Notes and Further Reading

11 Approximation Algorithms

11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem

11.2 The Center Selection Problem

11.3 Set Cover: A General Greedy Heuristic

11.4 The Pricing Method: Vertex Cover

11.5 Maximization via the Pricing Method: The Disjoint Paths Problem

11.6 Linear Programming and Rounding: An Application to Vertex Cover

*11.7 Load Balancing Revisited: A More Advanced LP Application

11.8 Arbitrarily Good Approximations: The Knapsack Problem

Solved Exercises

Exercises

Notes and Further Reading

12 Local Search

12.1 The Landscape of an Optimization Problem

12.2 The Metropolis Algorithm and Simulated Annealing

12.3 An Application of Local Search to Hopfield Neural Networks

12.4 Maximum-Cut Approximation via Local Search

12.5 Choosing a Neighbor Relation

*12.6 Classification via Local Search

12.7 Best-Response Dynamics and Nash Equilibria

Solved Exercises

Exercises

Notes and Further Reading

13 Randomized Algorithms

13.1 A First Application: Contention Resolution

13.2 Finding the Global Minimum Cut

13.3 Random Variables and Their Expectations

13.4 A Randomized Approximation Algorithm for MAX 3-SAT

13.5 Randomized Divide and Conquer: Median-Finding and Quicksort

13.6 Hashing: A Randomized Implementation of Dictionaries

13.7 Finding the Closest Pair of Points: A Randomized Approach

13.8 Randomized Caching

13.9 Chernoff Bounds

13.10 Load Balancing

13.11 Packet Routing

13.12 Background: Some Basic Probability Definitions

Solved Exercises

Exercises

Notes and Further Reading

Epilogue: Algorithms That Run Forever

References

Index

This page intentionally left blank

Jake Zavracky Acquisitions Editor: Matt Goldstein Project Editor: Maite Suarez-Rivas Production Supervisor: Marilyn Lloyd Marketing Manager: Michelle Brown Marketing Coordinator: Project Management: Windfall Software Composition: Windfall Software, using ZzTEX Copyeditor: Carol Leyba Technical Illustration: Dartmouth Publishing Proofreader: Indexer: Ted Laux Cover Design: Cover Photo: © 2005 Tim Laman / National Geographic. A pair of weaverbirds work Joyce Cosentino Wells Jennifer McClain together on their nest in Africa. Prepress and Manufacturing: Caroline Fell Printer: Courier Westford Access the latest information about Addison-Wesley titles 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. cm. Algorithm design / Jon Kleinberg, ´Eva Tardos.—1st ed. p. Includes bibliographical references and index. ISBN 0-321-29535-8 (alk. paper) 1. Computer algorithms. 2. Data structures (Computer science) I. Tardos, ´Eva. II. Title. QA76.9.A43K54 2005 005.1—dc22 2005000401 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 1 2 3 4 5 6 7 8 9 10-CRW-08 07 06 05

About the Authors Jon 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. ´Eva Tardos is a professor of Computer Science at Cor- nell University. She received her Ph.D. from E¨otv¨os 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- heim, 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-ﬂow 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 selﬁsh users.

This page intentionally left blank

分享到：

赞收藏

资料库

Algorithm Design.pdf

相关推荐

课程资源

热门标签

最新资料