Essential Algorithms Essential Algorithms A Practical Approach to Computer Algorithms Using Python® and C# Rod Stephens Essential Algorithms: A Practical Approach to Computer Algorithms Using Python® and C# Published by John Wiley & Sons, Inc. 10475 Crosspoint Boulevard Indianapolis, IN 46256 www.wiley.com Copyright © 2019 by John Wiley & Sons, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978‐1‐119‐57599‐3 ISBN: 978‐1‐119‐57596‐2 (ebk) ISBN: 978‐1‐119‐57598‐6 (ebk) Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 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, 222 Rosewood Drive, Danvers, MA 01923, (978) 750‐8400, fax (978) 646‐8600. Requests to the Publisher for permission should be addressed to the Per- missions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748‐6011, fax (201) 748‐6008, or online at http://www.wiley.com/go/permissions. Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services. If professional assistance is required, the services of a competent professional person should be sought. Nei- ther the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or website may provide or recommendations it may make. Further, readers should be aware that Internet websites listed in this work may have changed or disappeared between when this work was written and when it is read. For general information on our other products and services please contact our Customer Care Department within the United States at (877) 762‐2974, outside the United States at (317) 572‐3993 or fax (317) 572‐4002. Wiley publishes in a variety of print and electronic formats and by print‐on‐demand. Some material included with standard print versions of this book may not be included in e‐books or in print‐on‐demand. If this book refers to media such as a CD or DVD that is not included in the version you purchased, you may download this material at http:// booksupport.wiley.com. For more information about Wiley products, visit www.wiley.com. Library of Congress Control Number: 2019933736 Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. Python is a regis- tered trademark of Python Software Foundation. All other trademarks are the property of their respective owners. John Wiley & Sons, Inc. is not associated with any product or vendor mentioned in this book. For Maki About the Author Rod Stephens started out as a mathematician, but while studying at MIT, he discovered how much fun algorithms are. He took every algorithms course MIT offered, and he has been writing complex algorithms ever since. During his career, Rod has worked on an eclectic assortment of applica- tions in fields such as telephone switching, billing, repair dispatching, tax processing, wastewater treatment, concert ticket sales, cartography, and training for professional football players. Rod was a Microsoft Visual Basic Most Valuable Professional (MVP) for 15 years and has taught introductory programming courses. He has written more than 30 books that have been translated into languages from all over the world. He has also written more than 250 magazine articles covering C#, Visual Basic, Visual Basic for Applications, Delphi, and Java. Rod’s popular C# Helper website (http://www.csharphelper.com) receives millions of hits per year and contains tips, tricks, and example programs for C# programmers. His VB Helper website (http://www.vb-helper.com) contains similar material for Visual Basic programmers. You can contact Rod at: [email protected]. vii About the Technical Editor John Mueller is a freelance author and technical editor. He has writing in his blood, having produced 112 books and more than 600 articles to date. The topics range from networking to artificial intelligence and from database management to heads-down programming. Some of his current books include discussions of data science, machine learning, and algorithms. His technical editing skills have helped more than 70 authors refine the content of their manuscripts. John has provided technical editing services to numerous magazines, performed various types of consulting, and he writes certification exams as well. Be sure to read John’s blog at: http://blog.johnmuellerbooks.com/. You can reach John on the Internet at [email protected]. John also has a web- site at http://www.johnmuellerbooks.com/. Be sure to follow John on Amazon at https://www.amazon.com/John-Mueller/. ix Credits Senior Acquisitions Editor Technical Editor Kenyon Brown John Muller Editorial Manager Copy Editor Pete Gaughan Kim Wimpsett Associate Publisher Proofreader Jim Minatel Nancy Bell Production Manager Indexer Kathleen Wisor Potomac Indexing, LLC Project Editor Cover Designer Gary Schwartz Wiley Production Editor Athiyappan Lalith Kumar xi Acknowledgments Thanks to Ken Brown, Devon Lewis, Gary Schwartz, Pete Gaughan, Jim Mina- tel, Athiyappan Lalitkumar, and everyone else at Wiley that helped make this book possible. Thanks to longtime friend John Mueller, who provided his technical exper- tise to help make the information in this book as accurate as possible. (Any remaining mistakes are mine, not his.) Thanks also to Sunil Kumar for his generous feedback on the first edition. xiii Contents at a glance Introduction xxix Chapter 1 Algorithm Basics 1 Chapter 2 Numerical Algorithms 23 Chapter 3 Linked Lists 71 Chapter 4 Arrays 103 Chapter 5 Stacks and Queues 135 Chapter 6 Sorting 167 Chapter 7 Searching 201 Chapter 8 Hash Tables 209 Chapter 9 Recursion 227 Chapter 10 Trees 285 Chapter 11 Balanced Trees 349 Chapter 12 Decision Trees 367 Chapter 13 Basic Network Algorithms 403 Chapter 14 More Network Algorithms 451 Chapter 15 String Algorithms 493 Chapter 16 Cryptography 519 Chapter 17 Complexity Theory 543 xv xvi Contents at a glance Chapter 18 Distributed Algorithms 561 Chapter 19 Interview Puzzles 595 Appendix A Summary of Algorithmic Concepts 607 Appendix B Solutions to Exercises 623 Glossary 711 Index 739