Data Structures and Algorithms in Python Michael T. Goodrich DepartmentofComputerScience UniversityofCalifornia, Irvine Roberto Tamassia DepartmentofComputerScience BrownUniversity Michael H. Goldwasser DepartmentofMathematicsand ComputerScience Saint LouisUniversity VP & PUBLISHER Don Fowley EXECUTIVE EDITOR Beth Lang Golub EDITORIAL PROGRAM ASSISTANT Katherine Willis MARKETING MANAGER Christopher Ruel DESIGNER Kenji Ngieng SENIOR PRODUCTION MANAGER Janis Soo ASSOCIATE PRODUCTION MANAGER Joyce Poh This book was set in LaTEX by the authors. Printed and bound by Courier Westford. The cover was printed by Courier Westford. This book is printed on acid free paper. 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 fulfi ll 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 environmental, social, economic, and ethical challenges we face in our business. Among the issues we are addressing are carbon impact, paper specifi cations and procurement, ethical conduct within our business and among our vendors, and community and charitable support. For more information, please visit our website: www.wiley.com/go/citizenship. Copyright © 2013 John Wiley & Sons, Inc. 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, scanning 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 the Copyright Clearance Center, Inc. 222 Rosewood Drive, Danvers, MA 01923, website www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030-5774, (201)748-6011, fax (201)748-6008, website http://www.wiley.com/go/permissions. Evaluation copies are provided to qualifi ed 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 transferred to a third party. Upon completion of the review period, please return the evaluation copy to Wiley. Return instructions and a free of charge return mailing label are available at www.wiley.com/go/returnlabel. If you have chosen to adopt this textbook 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. Printed in the United States of America 10 9 8 7 6 5 4 3 2 1 To Karen, Paul,Anna, and Jack – MichaelT.Goodrich To Isabel – RobertoTamassia To Susan, Calista,and Maya – MichaelH.Goldwasser Preface The design and analysis of efficient data structures has longbeen recognized as a vital subject in computing and is part of the core curriculum of computer science andcomputerengineering undergraduate degrees. DataStructures andAlgorithms inPythonprovidesanintroductiontodatastructuresandalgorithms,includingtheir design,analysis,andimplementation. Thisbookisdesignedforuseinabeginning- level data structures course, or in an intermediate-level introduction to algorithms course. Wediscussitsuseforsuchcoursesinmoredetaillaterinthispreface. Topromote the development of robust and reusable software,wehave tried to take a consistent object-oriented viewpoint throughout this text. One of the main ideas ofthe object-oriented approach isthat data should bepresented as being en- capsulated with the methods that access and modify them. That is, rather than simply viewing data as a collection of bytes and addresses, we think of data ob- jects as instances of an abstract data type (ADT), which includes a repertoire of methods for performing operations on data objects of this type. We then empha- size that there may be several different implementation strategies for a particular ADT,andexploretherelativeprosandconsofthesechoices. Weprovidecomplete Python implementations for almost all data structures and algorithms discussed, and we introduce important object-oriented design patterns as means to organize thoseimplementations intoreusablecomponents. Desiredoutcomesforreaders ofourbookincludethat: • They have knowledge of the most common abstractions for datacollections (e.g.,stacks, queues, lists,trees,maps). • Theyunderstandalgorithmicstrategiesforproducingefficientrealizationsof commondatastructures. • They can analyze algorithmic performance, both theoretically and experi- mentally, andrecognize commontrade-offs betweencompeting strategies. • Theycanwiselyuseexistingdatastructuresandalgorithmsfoundinmodern programming language libraries. • Theyhaveexperienceworkingwithconcreteimplementationsformostfoun- dational datastructures andalgorithms. • Theycanapplydatastructures andalgorithms tosolvecomplexproblems. Insupportofthelastgoal,wepresentmanyexampleapplicationsofdatastructures throughout the book, including the processing of file systems, matching of tags in structured formats such as HTML, simple cryptography, text frequency analy- sis, automated geometric layout, Huffman coding, DNA sequence alignment, and searchengineindexing. v vi Preface Book Features This book is based upon the book Data Structures and Algorithms in Java by Goodrich and Tamassia, and the related Data Structures and Algorithms in C++ byGoodrich, Tamassia,andMount. However,thisbookisnotsimplyatranslation of those other books to Python. In adapting the material for this book, we have significantly redesigned theorganization andcontentofthebookasfollows: • Thecodebasehasbeenentirelyredesigned totakeadvantageofthefeatures ofPython,suchasuseofgenerators foriterating elementsofacollection. • Many algorithms that were presented as pseudo-code in the Java and C++ versions aredirectly presented ascompletePythoncode. • Ingeneral,ADTsaredefinedtohaveconsistentinterfacewithPython’sbuilt- indatatypesandthoseinPython’scollectionsmodule. • Chapter 5 provides an in-depth exploration of the dynamic array-based un- derpinnings ofPython’sbuilt-inlist,tuple,andstrclasses. NewAppendixA servesasanadditional reference regardingthefunctionality ofthestrclass. • Over450illustrations havebeencreatedorrevised. • Newandrevisedexercises bringtheoveralltotalnumberto750. Online Resources This book is accompanied by an extensive set of online resources, which can be foundatthefollowingWebsite: www.wiley.com/college/goodrich Studentsareencouraged tousethissitealongwiththebook,tohelpwithexer- cises and increase understanding of the subject. Instructors are likewise welcome to use the site to help plan, organize, and present their course materials. Included on this Web site is a collection of educational aids that augment the topics of this book,forbothstudentsandinstructors. Becauseoftheiraddedvalue,someofthese onlineresources arepasswordprotected. Forallreaders,andespeciallyforstudents,weincludethefollowingresources: • AllthePythonsourcecodepresented inthisbook. • PDFhandouts ofPowerpointslides(four-per-page) provided toinstructors. • Adatabaseofhintstoallexercises,indexedbyproblem number. Forinstructors usingthisbook,weincludethefollowingadditional teachingaids: • Solutions tohundreds ofthebook’sexercises. • Colorversionsofallfiguresandillustrations fromthebook. • SlidesinPowerpointandPDF(one-per-page) format. The slides are fully editable, so as to allow an instructor using this book full free- domincustomizing hisorherpresentations. Alltheonline resources areprovided atnoextrachargetoanyinstructor adopting thisbookforhisorhercourse. Preface vii Contents and Organization The chapters for this book are organized to provide a pedagogical path that starts with the basics of Python programming and object-oriented design. We then add foundational techniques likealgorithm analysis andrecursion. Inthemainportion of the book, we present fundamental data structures and algorithms, concluding withadiscussion ofmemorymanagement (that is,thearchitectural underpinnings ofdatastructures). Specifically,thechaptersforthisbookareorganizedasfollows: 1. Python Primer 2. Object-Oriented Programming 3. Algorithm Analysis 4. Recursion 5. Array-Based Sequences 6. Stacks, Queues, and Deques 7. Linked Lists 8. Trees 9. Priority Queues 10. Maps, Hash Tables, and Skip Lists 11. Search Trees 12. Sorting and Selection 13. Text Processing 14. Graph Algorithms 15. Memory Management and B-Trees A. Character Strings in Python B. Useful Mathematical Facts Amoredetailedtableofcontents followsthispreface, beginning onpagexi. Prerequisites We assume that the reader is at least vaguely familiar with a high-level program- minglanguage,suchasC,C++,Python,orJava,andthatheorsheunderstands the mainconstructs fromsuchahigh-level language, including: • Variablesandexpressions. • Decisionstructures (suchasif-statements andswitch-statements). • Iteration structures (forloopsandwhileloops). • Functions (whetherstand-alone orobject-oriented methods). For readers who are familiar with these concepts, but not with how they are ex- pressedinPython,weprovideaprimeronthePythonlanguageinChapter1. Still, thisbookisprimarily adatastructures book, notaPythonbook;hence, itdoesnot giveacomprehensive treatmentofPython. viii Preface Wedelaytreatment ofobject-oriented programming inPythonuntilChapter2. This chapter is useful for those new toPython, and forthose who maybe familiar withPython,yetnotwithobject-oriented programming. Intermsofmathematicalbackground,weassumethereaderissomewhatfamil- iar with topics from high-school mathematics. Even so, in Chapter 3, we discuss thesevenmost-importantfunctionsforalgorithmanalysis. Infact,sectionsthatuse something otherthanoneofthesesevenfunctions areconsidered optional, andare (cid:2) indicated with a star ( ). We give a summary of other useful mathematical facts, including elementary probability, inAppendixB. Relation to Computer Science Curriculum To assist instructors in designing a course in the context of the IEEE/ACM 2013 Computing Curriculum, the following table describes curricular knowledge units thatarecoveredwithinthisbook. KnowledgeUnit RelevantMaterial AL/BasicAnalysis Chapter3andSections4.2&12.2.4 AL/AlgorithmicStrategies Sections12.2.1,13.2.1,13.3,&13.4.2 AL/Fundamental Data Structures Sections4.1.3, 5.5.2,9.4.1,9.3, 10.2,11.1, 13.2, andAlgorithms Chapter12&muchofChapter14 Sections 5.3, 10.4, 11.2 through 11.6, 12.3.1, AL/AdvancedDataStructures 13.5,14.5.1,&15.3 AR/MemorySystemOrganization Chapter15 andArchitecture DS/Sets,RelationsandFunctions Sections10.5.1,10.5.2,&9.4 DS/ProofTechniques Sections3.4,4.2,5.3.2,9.3.6,&12.4.1 DS/BasicsofCounting Sections2.4.2,6.2.2,12.2.4,8.2.2&AppendixB DS/GraphsandTrees MuchofChapters8and14 DS/DiscreteProbability Sections1.11.1,10.2,10.4.2,&12.3.1 Much of the book, yet especially Chapter 2 and PL/Object-OrientedProgramming Sections7.4,9.5.1,10.1.3,&11.2.1 PL/FunctionalProgramming Section1.10 SDF/AlgorithmsandDesign Sections2.1,3.3,&12.2.1 SDF/FundamentalProgramming Chapters1&4 Concepts Chapters6&7,AppendixA,andSections1.2.1, SDF/FundamentalDataStructures 5.2,5.4,9.1,&10.1 SDF/DevelopmentalMethods Sections1.7&2.2 SE/SoftwareDesign Sections2.1&2.1.3 Mapping IEEE/ACM2013Computing Curriculumknowledge units tocoveragein thisbook.