实例介绍
【实例简介】
Algorithm Design and Applications Michael T. Goodrich Department of Information and Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science Brown University
Algorithm Design and Applications Michael T Goodrich Department of Information and Computer science University of California, Irvine Roberto Tamassia Department of Computer Science Brown university WILEY VICE PRESiDENt PUblisher Don Fowley EXECUTIVE EDITOR Beth Lang Golub EDITORIAL ASSISTANT Jayne ziemba ASSISTANT MARKETING MANAGER Debbie martin ASSOCIATE PRODUCTION MANAGER Joyce poh PRODUCTION EDITOR Wanqian Ye COVER CREDIT C Ansel Adams/U.S National Archives and records administration This book was set by the authors and printed and bound by Courier Kendallville This book is printed on acid frcc papcr. oo Founded in 1807, John Wiley Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008 we launched a Corporate Citizenship Initiative, a global effort to address the environrnental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support Formoreinformationpleasevisitourwebsitewww.wileycom/go/citizenship Copyright o 2015 John Wiley Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval systcm, or transmitted in any form or by any mcans, clectronic, mechanical, photocopying, rccording ther ng or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to theCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers,Ma01923(websitewww.copyright.com) Requests to the publisher for permission should be addressed to the Permissions Department, John Wiley sons, Inc 111 Rivcr Strect, Hoboken, NJ 07030-5774,(201)748-6011, fax(201)748-6008, or online at www.wiley.com/go/permissions Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or trans ferred to a third part Upon completion of the review period, please return the evaluation copy to wiley. Return instructions and a free of chargereturnshippinglabelareavailableatwww.wiley.com/go/returnlabel.Ifyouhavechosentoadoptthistextbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative Library of Congress Cataloging in Publication Data. Goodrich. MichaeI T,author University of California, Irvine, Roberto Tamassia, Department of Computer Science, Brown Universi/p nce Algorithm design and applications/Michael T Goodrich, Department of Information and Computer Scie Includes bibliographical references and index SBN978-1-118-33591-8( hardback 1. Computer algorithms. 2. Data structures( Computer science)I. Tamassia, Roberto, 1960-author. II. Title QA76.9A43G6682014 00573-dc23 2014021534 Printed in the United States of Am 1098765432 To Karen. Paul. Anna and jack Michael. goodrich T o sabe Roberto tamassia Contents Preface X Algorithm Analysis 1.1 Analyzing Algorithms 1.2 A Quick Mathematical Review 1.3 a Case Study in algorithm analysis 29 1.4 Amortization 34 1.5 Exercises 42 Part Data structures 2 Basic Data Structures 51 2.1 Stacks and Queues 2.2 Lists 2.3 Trees 2. 4 Exercises 84 3 Binary Search Trees 89 3.1 Searches and updates 91 3.2 Range Queries 101 3.3 Index-Based searching 3.4 Randomly Constructed Search Trees 107 3.5 Exercises 110 4 Balanced Binary Search Trees 115 4.1 Ranks and Rotations 117 4.2 AVL Trees 120 4.3 Red-Black Trees 126 4.4 Weak avl trees 4.5 Splay Trees 4.6 Exercises 149 5 Priority Queues and Heaps 155 5.1 Priority Queues 157 5.2 PQ-Sort. Selection-Sort. and Insertion - Sort .158 5.3 Heaps 163 5.4 Heap-Sort 5.5 Extending Priority Queues 179 5.6 Exercises 182 Contents 6 Hash Tables 187 6.1 Maps 189 6.2 Hash Functions 192 6.3 Handling Collisions and Rehashing 198 6.4 Cuckoo Hashing 206 6.5 Universal Hashing 212 6.6 Exercises ...215 7 Union-Find structures 219 7.1 Union-Find and its applications .221 7.2 A List-Based Implementation 225 7.3 A Tree-Based Implementation .,228 7.4 Exercises 236 Part l: Sorting and selection 8 Merge-Sort and Quick-sort 241 8.1 Merge-Sort 243 8.2 Quick-Sort 250 8.3 A Lower Bound on Comparison-Based Sorting 257 8. 4 Exercises 9 Fast Sorting and Selection 265 9.1 Bucket-Sort and Radix-Sort 267 9.2 Selection 270 9.3 Weighted Mediar 276 9. 4 Exercises 279 Part ll: Fundamental Techniques 10 The Greedy Method 283 10.1 The Fractional Knapsack Problem 286 10.2 Task Scheduling 289 10.3 Text Compression and Huffman Coding 92 10.4 Exercises 298 1 Divide-and-Conquer 303 11. 1 Recurrences and the Master Theorem 305 11.2 Integer Multiplication 313 11. 3 Matrix Multiplication 315 11. 4 The Maxima-Set Problem ,,,,317 11.5 Exercises ,,,,,,,,,,319 Contents 12 Dynamic Programming 323 12.1 Matrix Chain-Products 325 12.2 The General Technique 329 12.3 Telescope Scheduling .331 12.4 Game Strategies 334 12.5 The Longest Common Subsequence Problem 339 12.6 The 0-1 Knapsack Problem 343 12.7Eⅹ excises. 346 13 Graphs and Traversals 353 13.1 Graph Terminology and Representations 355 13.2 Depth-First Search ,,365 13.3 Breadth-First Search ..,370 13.4 Directed Graphs 373 13.5 Biconnected Components 13. 6 Exercises 392 Part IV: Graph Algorithms 14 Shortest Paths 397 14. 1 Single-Source Shortest Paths 399 14.2 Dijkstra's Algorithm 400 14.3 The Bellman-Ford algorithm 407 14.4 Shortest Paths in Directed Acyclic Graphs ,,410 14.5 All-Pairs Shortest Paths 412 14.6 Exercises 418 15 Minimum Spanning Trees 423 15. 1 Properties of Minimum Spanning Trees 425 15.2 Kruskal's algorithm 428 15.3 The Prim-Jarnik algorithm .433 15. 4 Baruvka's algorithm 436 15.5 Exercises 439 16 Network Flow and Matching 443 16.1 Flows and cuts 445 16.2 Maximum Flow algorithms 452 16. 3 Maximum Bipartite Matching 458 16.4 Baseball Elimination ,,,,,460 16.5 Minimum-Cost Flow 462 16.6 Exercises 469 Contents Part V: Computational Intractability 17 NP-Completeness 473 17. P and NP 476 17.2 NP-Completeness 483 17.3 CNF-SAT and 3SAT 489 17.4 VERTEX-COVER, CLIQUE, and SET-COVER 492 17.5 SUBSET-SUM and KNAPSACK 496 17.6 HAMILTONIAN-CYCLE and TsP .499 17.7 Exercises 502 18 Approximation Algorithms 507 18.1 The Metric Traveling salesperson problem 511 18.2 Approximations for Covering Problems 515 18.3 Polynomial-Time Approximation Schemes 518 18.4 Backtracking and Branch-and-Bound 521 18.5 Exercises ,,,,,525 art Vi: Additional Topics 19 Randomized Algorithms 529 19. 1 Generating random Permutations 531 19.2 Stable Marriages and Coupon Collecting 19.3 Minimum Cuts 539 19.4 Finding Prime Numbers 546 19.5 Chernoff bounds ,,,,,551 19.6 Skip Lists 557 19.7 Exercises 563 20 B-Trees and External Memory 569 20. 1 External Memory 571 20.2(2, 4)Trees and B-Trees 574 20.3 EXternal-Memory Sorting 590 20.4 Online Caching Algorithms 593 20.5 Exercises 600 21 Multidimensional Searching 603 21. 1 Range Trees 605 21.2 Priority Search Trees 609 21.3 Quadtrees and k-d Trees 614 21.4 Exercises ,,,,,,618 【实例截图】
【核心代码】
Algorithm Design and Applications Michael T. Goodrich Department of Information and Computer Science University of California, Irvine Roberto Tamassia Department of Computer Science Brown University
Algorithm Design and Applications Michael T Goodrich Department of Information and Computer science University of California, Irvine Roberto Tamassia Department of Computer Science Brown university WILEY VICE PRESiDENt PUblisher Don Fowley EXECUTIVE EDITOR Beth Lang Golub EDITORIAL ASSISTANT Jayne ziemba ASSISTANT MARKETING MANAGER Debbie martin ASSOCIATE PRODUCTION MANAGER Joyce poh PRODUCTION EDITOR Wanqian Ye COVER CREDIT C Ansel Adams/U.S National Archives and records administration This book was set by the authors and printed and bound by Courier Kendallville This book is printed on acid frcc papcr. oo Founded in 1807, John Wiley Sons, Inc. has been a valued source of knowledge and understanding for more than 200 years, helping people around the world meet their needs and fulfill their aspirations. Our company is built on a foundation of principles that include responsibility to the communities we serve and where we live and work. In 2008 we launched a Corporate Citizenship Initiative, a global effort to address the environrnental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifications and procurement, ethical conduct within our business and among our vendors, and community and charitable support Formoreinformationpleasevisitourwebsitewww.wileycom/go/citizenship Copyright o 2015 John Wiley Sons, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval systcm, or transmitted in any form or by any mcans, clectronic, mechanical, photocopying, rccording ther ng or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to theCopyrightClearanceCenter,Inc.,222RosewoodDrive,Danvers,Ma01923(websitewww.copyright.com) Requests to the publisher for permission should be addressed to the Permissions Department, John Wiley sons, Inc 111 Rivcr Strect, Hoboken, NJ 07030-5774,(201)748-6011, fax(201)748-6008, or online at www.wiley.com/go/permissions Evaluation copies are provided to qualified academics and professionals for review purposes only, for use in their courses during the next academic year. These copies are licensed and may not be sold or trans ferred to a third part Upon completion of the review period, please return the evaluation copy to wiley. Return instructions and a free of chargereturnshippinglabelareavailableatwww.wiley.com/go/returnlabel.Ifyouhavechosentoadoptthistextbook for use in your course, please accept this book as your complimentary desk copy. Outside of the United States, please contact your local sales representative Library of Congress Cataloging in Publication Data. Goodrich. MichaeI T,author University of California, Irvine, Roberto Tamassia, Department of Computer Science, Brown Universi/p nce Algorithm design and applications/Michael T Goodrich, Department of Information and Computer Scie Includes bibliographical references and index SBN978-1-118-33591-8( hardback 1. Computer algorithms. 2. Data structures( Computer science)I. Tamassia, Roberto, 1960-author. II. Title QA76.9A43G6682014 00573-dc23 2014021534 Printed in the United States of Am 1098765432 To Karen. Paul. Anna and jack Michael. goodrich T o sabe Roberto tamassia Contents Preface X Algorithm Analysis 1.1 Analyzing Algorithms 1.2 A Quick Mathematical Review 1.3 a Case Study in algorithm analysis 29 1.4 Amortization 34 1.5 Exercises 42 Part Data structures 2 Basic Data Structures 51 2.1 Stacks and Queues 2.2 Lists 2.3 Trees 2. 4 Exercises 84 3 Binary Search Trees 89 3.1 Searches and updates 91 3.2 Range Queries 101 3.3 Index-Based searching 3.4 Randomly Constructed Search Trees 107 3.5 Exercises 110 4 Balanced Binary Search Trees 115 4.1 Ranks and Rotations 117 4.2 AVL Trees 120 4.3 Red-Black Trees 126 4.4 Weak avl trees 4.5 Splay Trees 4.6 Exercises 149 5 Priority Queues and Heaps 155 5.1 Priority Queues 157 5.2 PQ-Sort. Selection-Sort. and Insertion - Sort .158 5.3 Heaps 163 5.4 Heap-Sort 5.5 Extending Priority Queues 179 5.6 Exercises 182 Contents 6 Hash Tables 187 6.1 Maps 189 6.2 Hash Functions 192 6.3 Handling Collisions and Rehashing 198 6.4 Cuckoo Hashing 206 6.5 Universal Hashing 212 6.6 Exercises ...215 7 Union-Find structures 219 7.1 Union-Find and its applications .221 7.2 A List-Based Implementation 225 7.3 A Tree-Based Implementation .,228 7.4 Exercises 236 Part l: Sorting and selection 8 Merge-Sort and Quick-sort 241 8.1 Merge-Sort 243 8.2 Quick-Sort 250 8.3 A Lower Bound on Comparison-Based Sorting 257 8. 4 Exercises 9 Fast Sorting and Selection 265 9.1 Bucket-Sort and Radix-Sort 267 9.2 Selection 270 9.3 Weighted Mediar 276 9. 4 Exercises 279 Part ll: Fundamental Techniques 10 The Greedy Method 283 10.1 The Fractional Knapsack Problem 286 10.2 Task Scheduling 289 10.3 Text Compression and Huffman Coding 92 10.4 Exercises 298 1 Divide-and-Conquer 303 11. 1 Recurrences and the Master Theorem 305 11.2 Integer Multiplication 313 11. 3 Matrix Multiplication 315 11. 4 The Maxima-Set Problem ,,,,317 11.5 Exercises ,,,,,,,,,,319 Contents 12 Dynamic Programming 323 12.1 Matrix Chain-Products 325 12.2 The General Technique 329 12.3 Telescope Scheduling .331 12.4 Game Strategies 334 12.5 The Longest Common Subsequence Problem 339 12.6 The 0-1 Knapsack Problem 343 12.7Eⅹ excises. 346 13 Graphs and Traversals 353 13.1 Graph Terminology and Representations 355 13.2 Depth-First Search ,,365 13.3 Breadth-First Search ..,370 13.4 Directed Graphs 373 13.5 Biconnected Components 13. 6 Exercises 392 Part IV: Graph Algorithms 14 Shortest Paths 397 14. 1 Single-Source Shortest Paths 399 14.2 Dijkstra's Algorithm 400 14.3 The Bellman-Ford algorithm 407 14.4 Shortest Paths in Directed Acyclic Graphs ,,410 14.5 All-Pairs Shortest Paths 412 14.6 Exercises 418 15 Minimum Spanning Trees 423 15. 1 Properties of Minimum Spanning Trees 425 15.2 Kruskal's algorithm 428 15.3 The Prim-Jarnik algorithm .433 15. 4 Baruvka's algorithm 436 15.5 Exercises 439 16 Network Flow and Matching 443 16.1 Flows and cuts 445 16.2 Maximum Flow algorithms 452 16. 3 Maximum Bipartite Matching 458 16.4 Baseball Elimination ,,,,,460 16.5 Minimum-Cost Flow 462 16.6 Exercises 469 Contents Part V: Computational Intractability 17 NP-Completeness 473 17. P and NP 476 17.2 NP-Completeness 483 17.3 CNF-SAT and 3SAT 489 17.4 VERTEX-COVER, CLIQUE, and SET-COVER 492 17.5 SUBSET-SUM and KNAPSACK 496 17.6 HAMILTONIAN-CYCLE and TsP .499 17.7 Exercises 502 18 Approximation Algorithms 507 18.1 The Metric Traveling salesperson problem 511 18.2 Approximations for Covering Problems 515 18.3 Polynomial-Time Approximation Schemes 518 18.4 Backtracking and Branch-and-Bound 521 18.5 Exercises ,,,,,525 art Vi: Additional Topics 19 Randomized Algorithms 529 19. 1 Generating random Permutations 531 19.2 Stable Marriages and Coupon Collecting 19.3 Minimum Cuts 539 19.4 Finding Prime Numbers 546 19.5 Chernoff bounds ,,,,,551 19.6 Skip Lists 557 19.7 Exercises 563 20 B-Trees and External Memory 569 20. 1 External Memory 571 20.2(2, 4)Trees and B-Trees 574 20.3 EXternal-Memory Sorting 590 20.4 Online Caching Algorithms 593 20.5 Exercises 600 21 Multidimensional Searching 603 21. 1 Range Trees 605 21.2 Priority Search Trees 609 21.3 Quadtrees and k-d Trees 614 21.4 Exercises ,,,,,,618 【实例截图】
【核心代码】
标签：
好例子网口号：伸出你的我的手 — 分享！
小贴士
感谢您为本站写下的评论，您的评论对其它用户来说具有重要的参考价值，所以请认真填写。
- 类似“顶”、“沙发”之类没有营养的文字，对勤劳贡献的楼主来说是令人沮丧的反馈信息。
- 相信您也不想看到一排文字/表情墙，所以请不要反馈意义不大的重复字符，也请尽量不要纯表情的回复。
- 提问之前请再仔细看一遍楼主的说明，或许是您遗漏了。
- 请勿到处挖坑绊人、招贴广告。既占空间让人厌烦，又没人会搭理，于人于己都无利。
关于好例子网
本站旨在为广大IT学习爱好者提供一个非营利性互相学习交流分享平台。本站所有资源都可以被免费获取学习研究。本站资源来自网友分享，对搜索内容的合法性不具有预见性、识别性、控制性，仅供学习研究，请务必在下载后24小时内给予删除，不得用于其他任何用途，否则后果自负。基于互联网的特殊性，平台无法对用户传输的作品、信息、内容的权属或合法性、安全性、合规性、真实性、科学性、完整权、有效性等进行实质审查；无论平台是否已进行审查，用户均应自行承担因其传输的作品、信息、内容而可能或已经产生的侵权或权属纠纷等法律责任。本站所有资源不代表本站的观点或立场，基于网友分享，根据中国法律《信息网络传播权保护条例》第二十二与二十三条之规定，若资源存在侵权或相关问题请联系本站客服人员，点此联系我们。关于更多版权及免责申明参见 版权及免责申明
网友评论
我要评论