John Paul Mueller - Algorithms For Dummies

Algorithms For Dummies®, 2nd Edition

Published by: John Wiley & Sons, Inc.,111 River Street, Hoboken, NJ 07030-5774, www.wiley.com

Copyright © 2022 by John Wiley & Sons, Inc., Hoboken, New Jersey

Media and software compilation copyright © 2022 by John Wiley & Sons, Inc. All rights reserved.

Published simultaneously in Canada

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 the prior written permission of the Publisher. Requests to the Publisher for permission should be addressed to the Permissions 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 .

Trademarks:Wiley, For Dummies, the Dummies Man logo, Dummies.com, Making Everything Easier, and related trade dress are trademarks or registered trademarks of John Wiley & Sons, Inc. and may not be used without written permission. 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.

LIMIT OF LIABILITY/DISCLAIMER OF WARRANTY: WHILE THE PUBLISHER AND AUTHORS HAVE USED THEIR BEST EFFORTS IN PREPARING THIS WORK, THEY 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 ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. NO WARRANTY MAY BE CREATED OR EXTENDED BY SALES REPRESENTATIVES, WRITTEN SALES MATERIALS OR PROMOTIONAL STATEMENTS FOR THIS WORK. THE FACT THAT AN ORGANIZATION, WEBSITE, OR PRODUCT IS REFERRED TO IN THIS WORK AS A CITATION AND/OR POTENTIAL SOURCE OF FURTHER INFORMATION DOES NOT MEAN THAT THE PUBLISHER AND AUTHORS ENDORSE THE INFORMATION OR SERVICES THE ORGANIZATION, WEBSITE, OR PRODUCT MAY PROVIDE OR RECOMMENDATIONS IT MAY MAKE. THIS WORK IS SOLD WITH THE UNDERSTANDING THAT THE PUBLISHER IS NOT ENGAGED IN RENDERING PROFESSIONAL SERVICES. THE ADVICE AND STRATEGIES CONTAINED HEREIN MAY NOT BE SUITABLE FOR YOUR SITUATION. YOU SHOULD CONSULT WITH A SPECIALIST WHERE APPROPRIATE. FURTHER, READERS SHOULD BE AWARE THAT WEBSITES LISTED IN THIS WORK MAY HAVE CHANGED OR DISAPPEARED BETWEEN WHEN THIS WORK WAS WRITTEN AND WHEN IT IS READ. NEITHER THE PUBLISHER NOR AUTHORS SHALL BE LIABLE FOR ANY LOSS OF PROFIT OR ANY OTHER COMMERCIAL DAMAGES, INCLUDING BUT NOT LIMITED TO SPECIAL, INCIDENTAL, CONSEQUENTIAL, OR OTHER DAMAGES.

For general information on our other products and services, please contact our Customer Care Department within the U.S. at 877-762-2974, outside the U.S. at 317-572-3993, or fax 317-572-4002. For technical support, please visit https://hub.wiley.com/community/support/dummies .

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: 2022934261

ISBN: 978-1-119-86998-6; 978-1-119-86999-3 (ebk); 978-1-119-87000-5 (ebk)

1 Cover

2 Title Page

3 Copyright

4 Introduction About This Book Foolish Assumptions Icons Used in This Book Beyond the Book Where to Go from Here

5 Part 1: Getting Started with Algorithms Chapter 1: Introducing Algorithms Describing Algorithms Using Computers to Solve Problems Distinguishing between Issues and Solutions Structuring Data to Obtain a Solution Chapter 2: Considering Algorithm Design Starting to Solve a Problem Dividing and Conquering Learning that Greed Can Be Good Computing Costs and Following Heuristics Evaluating Algorithms Chapter 3: Working with Google Colab Defining Google Colab Working with Notebooks Performing Common Tasks Using Hardware Acceleration Executing the Code Getting Help Chapter 4: Performing Essential Data Manipulations Using Python Performing Calculations Using Vectors and Matrixes Creating Combinations the Right Way Getting the Desired Results Using Recursion Performing Tasks More Quickly Chapter 5: Developing a Matrix Computation Class Avoiding the Use of NumPy Understanding Why Using a Class is Important Building the Basic Class Manipulating the Matrix

6 Part 2: Understanding the Need to Sort and Search Chapter 6: Structuring Data Determining the Need for Structure Stacking and Piling Data in Order Working with Trees Representing Relations in a Graph Chapter 7: Arranging and Searching Data Sorting Data Using Merge Sort and Quick Sort Using Search Trees and the Heap Relying on Hashing

7 Part 3: Exploring the World of Graphs Chapter 8: Understanding Graph Basics Explaining the Importance of Networks Defining How to Draw a Graph Measuring Graph Functionality Putting a Graph in Numeric Format Chapter 9: Reconnecting the Dots Traversing a Graph Efficiently Sorting the Graph Elements Reducing to a Minimum Spanning Tree Finding the Shortest Route Chapter 10: Discovering Graph Secrets Envisioning Social Networks as Graphs Navigating a Graph Chapter 11: Getting the Right Web page Finding the World in a Search Engine Explaining the PageRank Algorithm Implementing PageRank Going Beyond the PageRank Paradigm

8 Part 4: Wrangling Big Data Chapter 12: Managing Big Data Transforming Power into Data Streaming Flows of Data Sketching an Answer from Stream Data Chapter 13: Parallelizing Operations Managing Immense Amounts of Data Working Out Algorithms for MapReduce Chapter 14: Compressing and Concealing Data Making Data Smaller Hiding Your Secrets with Cryptography

9 Part 5: Challenging Difficult Problems Chapter 15: Working with Greedy Algorithms Deciding When It Is Better to Be Greedy Finding Out How Greedy Can Be Useful Chapter 16: Relying on Dynamic Programming Explaining Dynamic Programming Discovering the Best Dynamic Recipes Chapter 17: Using Randomized Algorithms Defining How Randomization Works Putting Randomness into your Logic Chapter 18: Performing Local Search Understanding Local Search Presenting local search tricks Solving Satisfiability of Boolean Circuits Chapter 19: Employing Linear Programming Using Linear Functions as a Tool Using Linear Programming in Practice Chapter 20: Considering Heuristics Differentiating Heuristics Routing Robots Using Heuristics Explaining Path Finding Algorithms

10 Part 6: The Part of Tens Chapter 21: Ten Algorithms That Are Changing the World Using Sort Routines Looking for Things with Search Routines Shaking Things Up with Random Numbers Performing Data Compression Keeping Data Secret Changing the Data Domain Analyzing Links Spotting Data Patterns Dealing with Automation and Automatic Responses Creating Unique Identifiers Chapter 22: Ten Algorithmic Problems Yet to Solve Solving Problems Quickly Solving 3SUM Problems More Efficiently Making Matrix Multiplication Faster Determining Whether an Application Will End Creating and Using One-Way Functions Multiplying Really Large Numbers Dividing a Resource Equally Reducing Edit Distance Calculation Time Playing the Parity Game Understanding Spatial Issues