Algorithm Design

所需积分/C币:50 2017-08-21 13:32:35 4.98MB PDF
收藏 收藏

Algorithm Design jon kleiberg
■ This page intentionally left blank JoN KLEINBERG. EVA TARDOS 〔onel| Universit PEARSON Addison Wesley Boston san francisco New York London Toronto Sydney Tokyo Singapore Madrid Mexico City Munich Paris Cape Town Hong Kong Montreal Acquisitions Editor: Matt Goldstein Project Editor: Maite suarez-Rivas Production Supervisor: Marilyn lloyd Marketing Manager: Michelle brown Marketing Coordinator: Jake Zavracky Project Management: Windfall software Composition: Windfall Software, using ZzTEX Copyeditor: Carol leyba Technical Illustration: Dartmouth Publishing Proofreader: Jennifer Mcclain Indexer: Ted laux Cover Design: Joyce Cosentino Wells Cover Photo: o 2005 Tim Laman/ National Geographic. A pair of weaverbirds work 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 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, Algorithm design Jon Kleinberg, Eva Tardos. -1st 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, Eva IL. Title QA76.9A43K542005 005.1-dc22 2005000401 Copyright o 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 hotocopying, 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 ISBN0-321-29535-8 12345678910-CRW-08070605 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 Eotvos 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 analy 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 This page intentionally left blank Contents about the authors Preface Introduction: Some Representative problems 1.1 A First Problem: Stable Matching 1.2 Five Representative problems 12 Solved exercises 19 Exercises 22 Notes and Further Reading 28 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 Al 42 2. 4 A Survey of Common Running Times 47 A More Complex Data Structure: Priority Queues 57 Solved exercises 65 Exercises 67 Notes and Further reading 70 3 Graphs 73 3.1 Basic Definitions and Applications 73 3.2 Graph Connectivity and Graph Traversal 78 3.3 Implementing Graph Traversal Using Queues and Stacks 87 3.4 Testing Bipartiteness: An Application of Breadth-First Search 94 3.5 Connectivity in Directed Graphs 97 Contents 3.6 Directed Acyclic Graphs and Topological Ordering Solved exercises 104 Exercises 107 Notes and Further Reading 112 4 Greedy algorithms 115 4.1 Interval Scheduling: The Greedy algorithm Stays Ahead 116 4.2 Scheduling to Minimize Lateness: An Exchange Argument 125 4.3 Optimal caching A More Complex exchange argument 131 4.4 Shortest Paths in a grap h137 4.5 The Minimum Spanning Tree Problem 142 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure 151 4.7 Clustering 157 4.8 Huffman Codes and Data Compression 161 4.9 Minimum-Cost Arborescences: A Multi-Phase greed Algorithm 177 Solved exercises 183 Exerci 188 Notes and further reading 205 s Divide and conquer 209 5.1 A First Recurrence: The mergesort Algorithm 210 5.2 Further recurrence relations 214 5.3 Counting Inversions 221 5.4 Finding the closest Pair of points 225 5.5 Integer Multiplication 231 5.6 Convolutions and the fast fourier transform 234 Solved exercises 242 Exercises 246 Notes and further reading 249 Dynamic programming 251 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 261 The star indicates an optional section (See the Preface for more information about the relationships among the chapters and sections.

试读 127P Algorithm Design
立即下载 低至0.43元/次 身份认证VIP会员低至7折
Algorithm Design 50积分/C币 立即下载
Algorithm Design第1页
Algorithm Design第2页
Algorithm Design第3页
Algorithm Design第4页
Algorithm Design第5页
Algorithm Design第6页
Algorithm Design第7页
Algorithm Design第8页
Algorithm Design第9页
Algorithm Design第10页
Algorithm Design第11页
Algorithm Design第12页
Algorithm Design第13页
Algorithm Design第14页
Algorithm Design第15页
Algorithm Design第16页
Algorithm Design第17页
Algorithm Design第18页
Algorithm Design第19页
Algorithm Design第20页

试读结束, 可继续阅读

50积分/C币 立即下载 >