Undergraduate Topics in Computer Science Kent D. Lee Steve Hubbard Data Structures and Algorithms with Python Undergraduate Topics in Computer Science This copy belongs to 'acha04' Undergraduate Topics in Computer Science (UTiCS) delivers high-quality instructional content for undergraduates studying in all areas of computing and information science. From core foundational and theoretical material to final-year topics and applications, UTiCS books take a fresh, concise, and modern approach and are ideal for self-study or for a one- or two-semester course. The texts are all authoredbyestablishedexpertsintheirfields,reviewedbyaninternationaladvisory board, and contain numerous examples and problems. Many include fully worked solutions. More information about this series at http://www.springer.com/series/7592 This copy belongs to 'acha04' Kent D. Lee Steve Hubbard • Data Structures and Algorithms with Python 123 This copy belongs to 'acha04' Kent D.Lee SteveHubbard Luther College Decorah, IA USA Series editor Ian Mackie Advisory Board Samson Abramsky, University of Oxford, Oxford, UK KarinBreitman,PontificalCatholicUniversityofRiodeJaneiro,RiodeJaneiro,Brazil Chris Hankin, Imperial College London, London, UK Dexter Kozen, Cornell University, Ithaca, USA Andrew Pitts, University of Cambridge, Cambridge, UK Hanne Riis Nielson, Technical University of Denmark, Kongens Lyngby, Denmark Steven Skiena, Stony Brook University, Stony Brook, USA Iain Stewart, University of Durham, Durham, UK ISSN 1863-7310 ISSN 2197-1781 (electronic) ISBN 978-3-319-13071-2 ISBN 978-3-319-13072-9 (eBook) DOI 10.1007/978-3-319-13072-9 LibraryofCongressControlNumber:2014953918 SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation,broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionor informationstorageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purposeofbeingenteredandexecutedonacomputersystem,forexclusiveusebythepurchaserof thework.Duplicationofthispublicationorpartsthereofispermittedonlyundertheprovisionsofthe Copyright Law of the Publisher’s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the CopyrightClearanceCenter.ViolationsareliabletoprosecutionundertherespectiveCopyrightLaw. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publicationdoesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexempt fromtherelevantprotectivelawsandregulationsandthereforefreeforgeneraluse. While the advice and information in this book are believed to be true and accurate at the date of publication,neithertheauthorsnortheeditorsnorthepublishercanacceptanylegalresponsibilityfor anyerrorsoromissionsthatmaybemade.Thepublishermakesnowarranty,expressorimplied,with respecttothematerialcontainedherein. Printedonacid-freepaper SpringerispartofSpringerScience+BusinessMedia(www.springer.com) This copy belongs to 'acha04' Preface Thanks for choosing Data Structures and Algorithms with Python. This text was written based on classroom notes for two courses, an introductory data structures and algorithms course and an advanced data structures and algorithms course. The materialcontainedinthistextcanbetaughtintwosemesters.Theearlychaptersin this text are intended as an introductory text for data structures and algorithms, whilethelaterchapterscoveradvancedtopicsthataresuitableforthesecondcourse indata structuresand algorithms. The Python language isusedthroughout the text and some familiarity with Python or some other object-oriented language is assumed. However, the first chapter contains a Python primer for those coming from a different language background. Thistextserveswellasafollow-ontexttoPythonProgrammingFundamentals by Kent D. Lee and published by Springer, but does not require you to have read that text. In this text the next steps are taken to teach you how to handle large amountsofdataefficiently.Anumberofalgorithmsareintroducedandtheneedfor themismotivatedthroughexamplesthatbringmeaningtotheproblemswefaceas computer programmers. An algorithm is a well-defined procedure for accom- plishingatask.AlgorithmsareanimportantpartofComputerScienceandthistext explores many algorithms to give you the background you need when writing programsofyourown.Thegoalisthathavingseensomeofthesortsofalgorithms presentedinthistext,youwillbeabletoapplythesetechniquestoother programs you write in the future. Another goal of this text is to introduce you to the idea of computational complexity. While there are many unique and interesting algorithms that we could explore, it is important to understand that some algorithms are more efficient than others.Whilecomputers areverygoodatdoing calculationsquickly, aninefficient algorithmcanmakethefastestcomputerseemverysloworevenmakeitappearto come to a halt. This text will show you what can and cannot be computed effi- ciently. The text builds this idea of efficiency from the most basic offacts giving youthetoolsyouwillneedtodeterminejusthowefficientanyalgorithmissoyou can make informed judgements about the programs you write. v This copy belongs to 'acha04' vi Preface The text assumes that you have some prior experience in computer program- ming, probably from an introductory programming course where you learned to breaksimpleproblemsintostepsthatcouldbesolvedbyacomputer.Thelanguage you used may have been Python, but not necessarily. Python is an excellent lan- guage for a text on data structuresand algorithms whether youhaveused it before or not. Python is an object-oriented programming language with operator over- loading and dynamic typing. Whether this is your first exposure to Python or you used it in your first course, you will learn more about the language from this text. The first chapter of the text reviews some of the fundamentals of computer pro- gramming along with the basic syntax of Python to get you up to speed in the language.Thensubsequentchaptersdiveintomoreadvancedtopicsandshouldbe read in sequence. Atthebeginningofeverychapterthegoalsofthechapterarestated.Attheend ofeverychapterisasetofreviewquestionsthatreinforcethegoalsofthechapter. These review questions are followed in each chapter by a few programming problemsthatrelatetothechaptergoalsbyaskingyoutousethethingsyoulearned in the chapter and apply them to a computer program. You can motivate your reading of a chapter by first consulting the review questions and then reading the chapter to answer them. Along the way, there are lots of examples to illustrate the concepts being introduced. Wehopeyouenjoythetext!Ifyouhaveanyquestionsorcommentspleasesend them to [email protected]. Kent D. Lee Steve Hubbard This copy belongs to 'acha04' For Teachers Atypicalintroductorydatastructurescoursecoversthefirstsevenchaptersofthis text. Chapter 1 introduces Python programming and the Tkinter module which is used in various places in the text. Tkinter comes with Python, so no special libraries need be installed for students to use it. Tkinter is used to visualize many of the results in this text. Chapter 2 introduces complexity analysis and depending on your needs, some of the material in Chap. 2 could be skipped in an introductory data structures course.Inparticular,thematerialonΘnotationandamortizedcomplexitycanbe skipped.Big-Ohnotationisenoughforthefirstsevenchapters.Typically,Chap.7 iscoveredlightlyandneartheendofasemestercourse.Itseemsthereisgenerally not enough time in a semester to cover graph theory in much detail. AdvancedcoursesindatastructuresandalgorithmsshouldstartwithChap.1if students are unfamiliar with Python or Tkinter. A brief refresher may not be bad even for those that have programmed using Python before. Chapter 2 should be covered in detail including the material on Θ notation and amortized complexity. Somereviewofhashingasitisused insetsandmapsinChap.5maybegood reviewearlierintheadvancedcoursealongwithabriefdiscussionofbinarysearch treesandtreetraversalsinChap.6.Dependingonyourneeds,Chap.7wouldbea goodchaptertocovernextincludingthematerialondepthfirstsearchofagraph. Chapter 8 is where the advanced material begins with assumptions made that students understand the concepts presented in the earlier chapters. The two introductorychaptersalongwithChaps.8–12makeaseven-chaptersequencethat will fill a semeseter in an advanced course nicely. This text is very project oriented. Solutions for all projects are available from KentD.Lee.YoucancontactKentatkentdlee@luther.eduforinstructorsolutions. You must provide proof (through a website or other reference) that you are an instructor at an educational institution to get access to the instructor materials. vii This copy belongs to 'acha04' viii ForTeachers Ifyouhaveanysuggestionsorfindanyerrorsinthetext,pleaseletusknowby emailingKentatkentdlee@luther.edu.Thanksandwehopeyouenjoyusingthetext inyourcourse! Kent D. Lee Steve Hubbard This copy belongs to 'acha04' Credits Connect Four is referenced in Chaps. 4, 12 and Appendix H. Connect Four is a trademark of the Milton Bradley Company in the United States and other countries. Chapter 2 references Mac OS X. Mac and Mac OS are registered trademarks of Apple Inc., registered in the U.S. and other countries. Microsoft Windows is also referenced in Chap. 2. Windows is a registered trademark of Microsoft Corporation in the United Stated and other countries. ix This copy belongs to 'acha04'