Data Structures and Algorithms in Python

Based on the authors' market leading data structures books in Java and C++, this book offers a comprehensive, definitive introduction to data structures in Python by authoritative authors. Data Structures and Algorithms in Python is the first authoritative object-oriented book available for Python dData structures andAlgorithms in PythonMichael T. GoodrichDepartment of Computer ScienceUniversity of California, IrvineRoberto tamassiaDepartment of Computer ScienceBrown universitMichael H. GoldwasserDepartment of Mathematics and Computer ScienceSaint Louis UniversityWILEYvp PublisherDon fowleEXECUTIVE EDITORBeth Lang golubEDITORIAL PROGRAM ASSISTANTKatherine willisMARKETING MANAGERChristopher ruelDESIGNERKenji ngiengSENIOR PRODUCTION MANAGERJanis sooASSOCIATE PRODUCTION MANAGERJoyce PohThis book was set in ATeX by the authors Printed and bound by courier WestfordThe cover was printed by Courier WestfordThis book is printed on acid free paperFounded in 1807, John Wiley Sons, InC has been a valued source of know ledge and understanding formore than 200 years, helping people around the world meet their needs and fulfill their aspirations. Ourcompany is built on a foundation of principles that include responsibility to the communities we serve andwhere we live and work. In 2008, we launched a Corporate Citizenship Initiative, a global effort to addressthe environmental, social, economic, and ethical challenges we face in our business. among the issues we areaddressing are carbon impact, paper specifications and procurement, ethical conduct within our business andamong our vendors, and community and charitable support. For more information, please visit our websitewww.wiley.com/go/citizenshipCopyright o 2013 John Wiley sons, Inc. All rights reserved. No part of this publication may bereproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanicalphotocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 ofthe 1976 United States Copyright Act, without either the prior written permission of the Publisher, orauthorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, InC. 222RosewoodDrivedaNversMa01923,websitewww.copyright.comRequeststothepublisherforpermissionshould be addressed to the Permissions Department, John wiley sons, Inc, lll River Street, Hoboken,Nj07030-5774,(201)748-6011,fax(201)748-6008,websitehttp://www.wiley.com/go/permissionsEvaluation copies are provided to qualified academics and professionals for review purposes only, for usein their courses during the next academic year. These copies are licensed and may not be sold or transferredto a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Returninstructionsandafreeofchargereturnmailinglabelareavailableatwww.wiley.com/go/returnlabel.Ifyouhave chosen to adopt this textbook for use in your course, please accept this book as your complimentary deskcopy. Outside of the United States, please contact your local sales representative.Printed in the united states of america10987654321To Karen Paul. Anna and jackMichael T goodrichTo IsabelRoberto tamassiaTo Susan, Calista, and MayaMichael h. goldwasserPrefaceThe design and analysis of efficient data structures has long been recognized as avital subject in computing and is part of the core curriculum of computer scienceand computer engineering undergraduate degrees. Data Structures and algorithmsin Python provides an introduction to data structures and algorithms, including theirdesign, analysis, and implementation. This book is designed for use in a beginninglevel data structures course, or in an intermediate-level introduction to algorithmscourse. We discuss its use for such courses in more detail later in this prefaceTo promote the development of robust and reusable software, we have tried totake a consistent object-oriented viewpoint throughout this text. One of the mainideas of the object-oriented approach is that data should be presented as being encapsulated with the methods that access and modify them. That is, rather thansimply viewing data as a collection of bytes and addresses, we think of data objects as instances of an abstract data type(ADt), which includes a repertoire ofmethods for performing operations on data objects of this type. We then empha-size that there may be several different implementation strategies for a particularADT, and explore the relative pros and cons of these choices. We provide completePython implementations for almost all data structures and algorithms discussedand we introduce important object-oriented design patterns as means to organizethose implementations into reusable componentsDesired outcomes for readers of our book include thatThey have knowledge of the most common abstractions for data collections(e. g, stacks, queues, lists, trees, mapsThey understand algorithmic strategies for producing efficient realizations ofcommon data structuresThey can analyze algorithmic performance, both theoretically and experimentally and recognize common trade-offs between competing strategiesThey can wisely use existing data structures and algorithms found in modernprogramming language librariesThey have experience working with concrete implementations for most foundational data structures and algorithmsThey can apply data structures and algorithms to solve complex problemsIn support of the last goal, we present many example applications of data structuresthroughout the book, including the processing of file systems, matching of tagsin structured formats such as HTML, simple cryptography, text frequency analy-sis, automated geometric layout, Huffman coding, DNA sequence alignment, andsearch engine indexingBook featuresThis book is based upon the book Data Structures and Algorithms in Java byGoodrich and Tamassia, and the related Data structures and algorithms in C++by Goodrich, Tamassia, and Mount. However, this book is not simply a translationof those other books to Python In adapting the material for this book, we havesignificantly redesigned the organization and content of the book as followsThe code base has been entirely redesigned to take advantage of the featuresof Python such as use of generators for iterating elements of a collectionMany algorithms that were presented as pseudo-code in the Java and C++versions are directly presented as complete Python codee In general, adts are defined to have consistent interface with Pythons builtin data types and those in Pythons collections moduleChapter 5 provides an in-depth exploration of the dynamic array-based underpinnings of Pythons built-in list, tuple, and str classes. New Appendix aserves as an additional reference regarding the functionality of the str classOver 450 illustrations have been created or revisede New and revised exercises bring the overall total number to 750Online resourcesThis book is accompanied by an extensive set of online resources, which can befound at the following web site:www.wiley.com/college/goodrichStudents are encouraged to use this site along with the book, to help with exer-cises and increase understanding of the subject. Instructors are likewise welcometo use the site to help plan, organize, and present their course materials. Includedon this Web site is a collection of educational aids that augment the topics of thisbook. for both students and instructors. because of their added value. some of theseonline resources are pass word protectedFor all readers, and especially for students, we include the following resourcesAll the Python source code presented in this bookPDF handouts of Powerpoint slides(four-per-page) provided to instructorse a database of hints to all exercises, indexed by problem numberFor instructors using this book, we include the following additional teaching aidsSolutions to hundreds of the book's exercisesColor versions of all figures and illustrations from the book.Slides in Powerpoint and PDF(one-per-page)formatThe slides are fully editable, so as to allow an instructor using this book full freedon in customizing his or her presentations. All the online resources are providedat no extra charge to any instructor adopting this book for his or her coursePrefaceContents and organizationThe chapters for this book are organized to provide a pedagogical path that startswith the basics of Python programming and object-oriented design. We then addfoundational techniques like algorithm analysis and recursion In the main portionof the book, we present fundamental data structures and algorithms, concludingwith a discussion of memory management(that is, the architectural underpinningsof data structures). Specifically, the chapters for this book are organized as follows1. Python Primer2. Object-Oriented Programming3. Algorithm Analysis4. Recursion5. Array-Based Sequences6. Stacks, Queues, and deques7. Linked Lists8. Trees9. Priority Queues10. Maps, Hash Tables and skip Lists11. Search Trees12. Sorting and selection13. Text Processing14. Graph algorithms15. Memory Management and b-treesA. Character Strings in PythonB. Useful mathematical factsA more detailed table of contents follows this preface, beginning on page xiPrerequisitesWe assume that the reader is at least vaguely familiar with a high-level programming language, such as c, c++, python, or Java, and that he or she understands themain constructs from such a high-level language, includinVariables and expressionsDecision structures(such as if-statements and switch-statements)Iteration structures(for loops and while loops)Functions(whether stand-alone or object-oriented methods)For readers who are familiar with these concepts, but not with how they are ex-pressed in Python, we provide a primer on the python language in Chapter 1. Still,this book is primarily a data structures book, not a Python book; hence, it does notgive a comprehensive treatment of PythonWe delay treatment of object-oriented programming in Python until Chapter 2This chapter is useful for those new to Python, and for those who may be familiarwith Python, yet not with object-oriented programminIn terms of mathematical background we assume the reader is somewhat famil-iar with topics from high-school mathematics. Even So, in Chapter 3, we discussthe seven most-important functions for algorithm analysis. In fact, sections that usesomething other than one of these seven functions are considered optional, and areindicated with a star(*). We give a summary of other useful mathematical facts,including elementary probability. in appendix bRelation to Computer Science curriculumTo assist instructors in designing a course in the context of the Ieee/acm 2013Computing Curriculum, the following table describes curricular knowledge unitsthat are covered within this bookKnowledge UnitRelevant materialAL/Basic AnalysisChapter 3 and Sections 4.2& 12.2.4AL/Algorithmic strategiesSections12.2.1,13.2.1,13.3,&13.4.2AL/Fundamental Data Structures Sections 4.1.3, 5.5.2, 9.4.1, 9.3, 10.2, 11.1, 13.2and algorithmsChapter 12& much of Chapter 14aL/Advanced data structuresSections5.3,10.4,11.2 through11.6,12.3.113.5,14.5.1.&15.3AR/Memory System Organization Chapter 15and architectureDS/Sets. Relations and Functions Sections 10.5.1. 10.5.2. &9.4DS/Proof TechniquesSections3.4,4.2,5.3.2,9.3.6,&12.4.1DS/Basics of CountingSections 2.4.2, 6.2.2, 12.2.4, 8.2.2& appendix bDS/Graphs and TreesMuch of Chapters 8 and 14DS/Discrete ProbabilitySections1.11.l,10.2,10.4.2,&12.3.1PL/Object-Oriented ProgrammingMuch of the book, yet especially Chapter 2 andSections7.4,9.5.1,10.1.3,&11.2.1PL/Functional Programming Section 1.10SDF/Algorithms and designSections2.1.3.3.&12.2.1SDF/Fundamental Programming Chapters 1 4ConceptsSDF/Fundamental Data StructuresChapters 6&7, appendix a, and Sections 1.2.15.2.5.4.9.1.&10.1SDF/Developmental Methods Sections 1.7&2.2SE/Software DesignSections 2. 1 & 2.1.3Mapping IEEE/ACM 2013 Computing Curriculum know ledge units to coverage inthis book