Python Algorithms

Data Structures and Algorithms in PythonPython AlgorithmsMastering Basic Algorithms in thePython LanguageMagnus Lie HetlandApress°Python Algorithms: Mastering Basic Algorithms in the Python LanguageCopyright o 2010 by Magnus Lie Hetlandmeans,electronic or mechanical, including photocopying, recording or by any in formation ?EAll rights reserved. No part of this work may be reproduced or transmitted in any form or bystorage or retrieval system, without the prior written permission of the copyright owner andthe publisherISBN-13(pbk):978-1-43023237-7ISBN-13( electronic):978-1-4302-3238-4Printed and bound in the united states of america 987654321Trademarked names, logos, and images may appear in this book. Rather than use a trademarksymbol with every occurrence of a trademarked name, logo, or image we use the names, logos, andimages only in an editorial fashion and to the benefit of the trademark owner, with no intention ofinfringement of the trademarkThe use in this publication of trade names, trademarks, service marks, and similar terms, even ifthey are not identified as such, is not to be taken as an expression of opinion as to whether or notthey are subject to proprietary rightsPresident and Publisher: Paul ManningLead editor: frank pohlmannDevelopment Editor: Douglas PundickTechnical reviewer: Alex martelliEditorial Board Steve Anglin, Mark Beckner, Ewan Buckingham, Gary CornellJonathan gennick, Jonathan Hassell, Michelle Lowman, Matthew moodieDuncan Parkes, Jeffrey Pepper, Frank Pohlmann, Douglas Pundick,Ben renow-Clarke, Dominic shakeshaft, Matt Wade. Tom WelshCoordinating Editor: Adam HeathCompositor: mary sudulIndexer: Brenda millerArtist: April milneCover Designer: Anna IshchenkoPhoto Credit: KaiT. RaglandDistributed to the book trade worldwide by Springer Science+Business Media, LLC, 233 SpringStreet, 6th Floor, New York, NY 10013. Phone 1-800-SPRINGeR, fax(201)348-4505, e-mailorders-ny@springer-sbm.comorvisitwww.springeronline.comForinformationontranslationspleasee-mailrights@apress.comorvisitwww.apress.comApress and friends of ed books may be purchased in bulk for academic, corporate, or promotionaluse eBook versions and licenses are also available for most titles for more information referenceourSpecialBulkSales-eBookLicensingwebpageatwww.apress.com/info/bulksalesThe information in this book is distributed on an"as is"basis, without warranty. Although everyprecaution has been taken in the preparation of this work, neither the author(s) nor Apress shallhave any liability to any person or entity with respect to any loss or damage caused or alleged to becaused directly or indirectly by the information contained in this workThesourcecodeforthisbookisavailabletoreadersatwww.apress.comFor my studentsMay your quest for knowledge be richly rewardedContents mmmmm viAbout the authorXIIAbout the technical reviewerAcknowledgments,,…,…,,,,,,1,,1XVPreface■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■口■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■XVIChapter 1: Introduction RmREERIRaI 1Chapter 2: The basicsChapter 3: Counting 101 emaan45Chapter 4: Induction and Recursion and reduction■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■口■■Chapter 5: Traversal: The skeleton Key of Algorithmics■■■■■■■■■■■■■■■■■■■■■■■■■■■■■a■■■101Chapter 6: Divide, Combine, and Conquer mam 125Chapter 7: Greed Is Good? Prove It!maan151Chapter 8: Tangled Dependencies and Memoization mmmmmmmm 175Chapter 9: From a to B with Edsger and friends■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■199Chapter 10: Matchings, Cuts, and Flows mRB RRRRERRIRIRChapter 11: Hard Problems and limited sloppiness an241Appendix A: Pedal to the Metal: Accelerating python■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■m271Appendix B: List of Problems and Algorithms■■■■■■■■■■■口■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■275Appendix C: Graph terminology a■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■285Appendix D: Hints for Exercises.aar291Index■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■口■307Contents at a glance mmvAbout the authorXIIAbout the technical reviewer■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■XIVAcknowledgments R RERRIaEIIaIIn XVPreface■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■口■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■XVIChapter 1: Introduction aam■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■What's all this, then?Why Are You Here?Some PrerequisitesWhat's in this b00k…SummaryIf youre curiousExercises…ReferencesChapter 2: TheSome Core Ideas in Computing.Asymptotic NotationIt's greek to me!Rules of the roadTaking the Asymptotics for a spinThree Important Cases………Empirical Evaluation of algorithms■ CONTENTSImplementing Graphs and Trees.Adjacency Lists and the LikeAdjacency Matrices面B面面面面日面日面日面日面日自aImplementing TreesA Multitude of RepresentationsBeware of e|ackB0Xes…36Hidden Squares…37The trouble with floatsSummary…,…,If Youre curiousExercises42ReferencesChapter3: Counting101.,,,,,…,,,,,,m,,,,45The skinny on SumsMore greek46Working with Sums………,,…A Tale of two tournamentsDBDDBDBDDBBDDBBDDShaking HandsThe hare and the tortoiseSubsets permutations, and combinations53Recursion and recurrences56Doing it by handA Few Important Examples...........Guessing and checking ..The Master theorem A cookie-Cutter Solution64So what was all that about?6768If you're curious69Exercises69■ CONTENTSReferencesChapter 4: Induction and Recursion .a and reduction■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■Oh, That's EasyOne, TWo, Many74Mirror mirror76Designing with Induction(and Recursion)81Finding a Maximum Permutation…..................,,,…,…,……….81The celebrity Problem.............Topological Sorting........................87Stronger AssumptionsInvariants and correctness92Relaxation and gradual ImprovementReduction contraposition hardness Proof94Problem Solving Advice .Summary……,,96If you're curious97Exercises∴,97References99Chapter 5: Traversal: The skeleton Key of algorithmics mmmmmma am 101A Walk in the park107No Cycles Allowed108How to Stop Walking in circles...09G0Deep!….110Depth- First Timestamps and Topological Sorting( Again)…………………………12Infinite Mazes and shortest(Unweighted )Paths114Strongly Connected Components .....118Summary…121