实例介绍
【实例简介】
Algorithmic ideas 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 not
This page intentionally left blank JON KLEINBERG. EVA TARDOS Cornell University 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 zavrack Project management: Windfall so 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: 0 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 sitehttp://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, Eva Tardos -Ist ed p. Cm Includes bibliographical references and index ISBN 0-321-29535-8(alk. paper) 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 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 ISBN0-321-29535 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 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 This page intentionally left blank Contents about the authors Preface 1 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 arrays 42 2.4 A Survey of common Running Times 47 2.5 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 99 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 graph 137 4.5 The Minimum Spanning Tree Problem 142 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structu 151 4.7 Clustering 157 4.8 Huffman Codes and Data Compression 161 4.9 Minimum-Cost arborescences: A Multi-Phase greed algorith 177 Solved exercises 183 Exercises 188 Notes and further readi 05 s Divide and Conquer 209 5.1 A First Recurrence: The mergesort Algorithm 210 5. 2 Further recurrence relations 21 4 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 6 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 【实例截图】
【核心代码】
Algorithmic ideas 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 not
This page intentionally left blank JON KLEINBERG. EVA TARDOS Cornell University 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 zavrack Project management: Windfall so 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: 0 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 sitehttp://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, Eva Tardos -Ist ed p. Cm Includes bibliographical references and index ISBN 0-321-29535-8(alk. paper) 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 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 ISBN0-321-29535 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 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 This page intentionally left blank Contents about the authors Preface 1 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 arrays 42 2.4 A Survey of common Running Times 47 2.5 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 99 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 graph 137 4.5 The Minimum Spanning Tree Problem 142 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structu 151 4.7 Clustering 157 4.8 Huffman Codes and Data Compression 161 4.9 Minimum-Cost arborescences: A Multi-Phase greed algorith 177 Solved exercises 183 Exercises 188 Notes and further readi 05 s Divide and Conquer 209 5.1 A First Recurrence: The mergesort Algorithm 210 5. 2 Further recurrence relations 21 4 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 6 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 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论