Algorithms For Dummies

Your secret weapon to understanding—and using!—one of the most powerful influences in the world today

From your Facebook News Feed to your most recent insurance premiums—even making toast!—algorithms play a role in virtually everything that happens in modern society and in your personal life. And while they can seem complicated from a distance, the reality is that, with a little help, anyone can understand—and even use—these powerful problem-solving tools!

In Algorithms For Dummies, you'll discover the basics of algorithms, including what they are, how they work, where you can find them (spoiler alert: everywhere!), who invented the most important ones in use today (a Greek philosopher is involved), and how to create them yourself.

You'll also find:

• Dozens of graphs and charts that help you understand the inner workings of algorithms
• Links to an online repository called GitHub for constant access to updated code
• Step-by-step instructions on how to use Google Colaboratory, a zero-setup coding environment that runs right from your browser

Whether you're a curious internet user wondering how Google seems to always know the right answer to your question or a beginning computer science student looking for a head start on your next class, Algorithms For Dummies is the can't-miss resource you've been waiting for.

John Mueller has published more than 100 books on technology, data, and programming. John has a website and blog where he writes articles on technology and offers assistance alongside his published books.

Luca Massaron is a data scientist specializing in insurance and finance. A Google Developer Expert in machine learning, he has been involved in quantitative analysis and algorithms since 2000.

Introduction 1

About This Book 1

Foolish Assumptions 3

Icons Used in This Book 3

Beyond the Book 4

Where to Go from Here 5

Part 1: Getting Started with Algorithms 7

Chapter 1: Introducing Algorithms 9

Describing Algorithms 10

The right way to make toast: Defining algorithm uses 12

Finding algorithms everywhere 14

Using Computers to Solve Problems 15

Getting the most out of modern CPUs and GPUs 16

Working with special-purpose chips 17

Networks: Sharing is more than caring 18

Leveraging available data 18

Distinguishing between Issues and Solutions 19

Being correct and efficient 19

Discovering there is no free lunch 20

Adapting the strategy to the problem 20

Describing algorithms in a lingua franca 20

Facing problems that are like brick walls, only harder 21

Structuring Data to Obtain a Solution 21

Understanding a computer’s point of view 22

Arranging data makes the difference 22

Chapter 2: Considering Algorithm Design 23

Starting to Solve a Problem 24

Modeling real-world problems 25

Finding solutions and counterexamples 26

Standing on the shoulders of giants 27

Dividing and Conquering 28

Avoiding brute-force solutions 29

Keeping it simple, silly (KISS) 29

Breaking down a problem is usually better 30

Learning that Greed Can Be Good 30

Applying greedy reasoning 31

Reaching a good solution 31

Computing Costs and Following Heuristics 32

Representing the problem as a space 33

Going random and being blessed by luck 34

Using a heuristic and a cost function 34

Evaluating Algorithms 35

Simulating using abstract machines 36

Getting even more abstract 37

Working with functions 38

Chapter 3: Working with Google Colab 41

Defining Google Colab 42

Understanding what Google Colab does 42

Getting familiar with Google Colab features 44

Working with Notebooks 47

Creating a new notebook 47

Opening existing notebooks 47

Saving notebooks 50

Performing Common Tasks 51

Creating code cells 52

Creating text cells 54

Creating special cells 54

Editing cells 55

Moving cells 55

Using Hardware Acceleration 55

Executing the Code 56

Getting Help 57

Chapter 4: Performing Essential Data Manipulations Using Python 59

Performing Calculations Using Vectors and Matrixes 60

Understanding scalar and vector operations 61

Performing vector multiplication 63

Creating a matrix is the right way to start 63

Multiplying matrixes 64

Defining advanced matrix operations 65

Creating Combinations the Right Way 67

Distinguishing permutations 68

Shuffling combinations 69

Facing repetitions 70

Getting the Desired Results Using Recursion 71

Explaining recursion 71

Eliminating tail call recursion 74

Performing Tasks More Quickly 75

Considering divide and conquer 75

Distinguishing between different possible solutions 78

Chapter 5: Developing a Matrix Computation Class 79

Avoiding the Use of NumPy 80

Understanding Why Using a Class is Important 81

Building the Basic Class 82

Creating a matrix 83

Printing the resulting matrix 84

Accessing specific matrix elements 85

Performing scalar and matrix addition 86

Performing multiplication 87

Manipulating the Matrix 90

Transposing a matrix 91

Calculating the determinant 91

Flattening the matrix 95

Part 2: Understanding the Need to Sort and Search 97

Chapter 6: Structuring Data 99

Determining the Need for Structure 100

Making it easier to see the content 100

Matching data from various sources 101

Considering the need for remediation 102

Stacking and Piling Data in Order 105

Ordering in stacks 105

Using queues 107

Finding data using dictionaries 108

Working with Trees 109

Understanding the basics of trees 109

Building a tree 110

Representing Relations in a Graph 112

Going beyond trees 113

Building graphs 114

Chapter 7: Arranging and Searching Data 117

Sorting Data Using Merge Sort and Quick Sort 118

Understanding why sorting data is important 118

Employing better sort techniques 122

Using Search Trees and the Heap 127

Considering the need to search effectively 127

Building a binary search tree 129

Performing specialized searches using a binary heap 131

Relying on Hashing 132

Putting everything into buckets 132

Avoiding collisions 134

Creating your own hash function 135

Part 3: Exploring the World of Graphs 139

Chapter 8: Understanding Graph Basics 141

Explaining the Importance of Networks 142

Considering the essence of a graph 142

Finding graphs everywhere 145

Showing the social side of graphs 146

Understanding subgraphs 147

Defining How to Draw a Graph 148

Distinguishing the key attributes 149

Drawing the graph 150

Measuring Graph Functionality 151

Counting edges and vertexes 152

Computing centrality 154

Putting a Graph in Numeric Format 157

Adding a graph to a matrix 157

Using sparse representations 158

Using a list to hold a graph 159

Chapter 9: Reconnecting the Dots 161

Traversing a Graph Efficiently 162

Creating the graph 163

Applying breadth-first search 164

Applying depth-first search 165

Determining which application to use 167

Sorting the Graph Elements 168

Working on Directed Acyclic Graphs (DAGs) 169

Relying on topological sorting 169

Reducing to a Minimum Spanning Tree 170

Getting the minimum spanning tree historical context 170

Working with unweighted versus weighted graphs 171

Creating a minimum spanning tree example 171

Discovering the correct algorithms to use 173

Introducing priority queues 174

Leveraging Prim’s algorithm 175

Testing Kruskal’s algorithm 177

Determining which algorithm works best 179

Finding the Shortest Route 180

Defining what it means to find the shortest path 180

Adding a negative edge 182

Explaining Dijkstra’s algorithm 184

Explaining the Bellman-Ford algorithm 187

Explaining the Floyd-Warshall algorithm 190

Chapter 10: Discovering Graph Secrets 195

Envisioning Social Networks as Graphs 196

Clustering networks in groups 196

Discovering communities 199

Navigating a Graph 202

Counting the degrees of separation 202

Walking a graph randomly 204

Chapter 11: Getting the Right Web page 207

Finding the World in a Search Engine 208

Searching the Internet for data 208

Considering how to find the right data 209

Explaining the PageRank Algorithm 210

Understanding the reasoning behind the PageRank algorithm 210

Explaining the nuts and bolts of PageRank 212

Implementing PageRank 212

Implementing a Python script 213

Struggling with a naive implementation 216

Introducing boredom and teleporting 219

Looking inside the life of a search engine 220

Considering other uses of PageRank 221

Going Beyond the PageRank Paradigm 221

Introducing semantic queries 222

Using AI for ranking search results 222

Part 4: Wrangling Big Data 223

Chapter 12: Managing Big Data 225

Transforming Power into Data 226

Understanding Moore’s implications 226

Finding data everywhere 228

Getting algorithms into business 231

Streaming Flows of Data 233

Analyzing streams with the right recipe 234

Reserving the right data 235

Sketching an Answer from Stream Data 240

Filtering stream elements by heart 240

Demonstrating the Bloom filter 243

Finding the number of distinct elements 246

Learning to count objects in a stream 247

Chapter 13: Parallelizing Operations 249

Managing Immense Amounts of Data 250

Understanding the parallel paradigm 251

Distributing files and operations 253

Employing the MapReduce solution 255

Working Out Algorithms for MapReduce 259

Setting up a MapReduce simulation 260

Inquiring by mapping 262

Chapter 14: Compressing and Concealing Data 267

Making Data Smaller 268

Understanding encoding 268

Considering the effects of compression 270

Choosing a particular kind of compression 271

Choosing your encoding wisely 273

Encoding using Huffman compression 276

Remembering sequences with LZW 278

Hiding Your Secrets with Cryptography 282

Substituting characters 283

Working with AES encryption 285

Part 5: Challenging Difficult Problems 289

Chapter 15: Working with Greedy Algorithms 291

Deciding When It Is Better to Be Greedy 292

Understanding why greedy is good 293

Keeping greedy algorithms under control 294

Considering NP complete problems 297

Finding Out How Greedy Can Be Useful 299

Arranging cached computer data 299

Competing for resources 301

Revisiting Huffman coding 303

Chapter 16: Relying on Dynamic Programming 307

Explaining Dynamic Programming 308

Obtaining a historical basis 308

Making problems dynamic 309

Casting recursion dynamically 311

Leveraging memoization 314

Discovering the Best Dynamic Recipes 316

Looking inside the knapsack 317

Touring around cities 321

Approximating string search 326

Chapter 17: Using Randomized Algorithms 331

Defining How Randomization Works 332

Considering why randomization is needed 333

Understanding how probability works 334

Understanding distributions 335

Simulating the use of the Monte Carlo method 339

Putting Randomness into your Logic 341

Calculating a median using quick select 341

Doing simulations using Monte Carlo 344

Ordering faster with quick sort 347

Chapter 18: Performing Local Search 349

Understanding Local Search 350

Knowing the neighborhood 351

Presenting local search tricks 353

Explaining hill climbing with n-queens 354

Discovering simulated annealing 357

Avoiding repeats using Tabu Search 358

Solving Satisfiability of Boolean Circuits 359

Solving 2-SAT using randomization 360

Implementing the Python code 361

Realizing that the starting point is important 365

Chapter 19: Employing Linear Programming 367

Using Linear Functions as a Tool 368

Grasping the basic math you need 369

Learning to simplify when planning 371

Working with geometry using simplex 372

Understanding the limitations 373

Using Linear Programming in Practice 374

Setting up PuLP at home 375

Optimizing production and revenue 376

Chapter 20: Considering Heuristics 381

Differentiating Heuristics 382

Considering the goals of heuristics 383

Going from genetic to AI 383

Routing Robots Using Heuristics 384

Scouting in unknown territories 385

Using distance measures as heuristics 387

Explaining Path Finding Algorithms 388

Creating a maze 388

Looking for a quick best-first route 392

Going heuristically around by A* 396

Part 6: The Part of Tens 401

Chapter 21: Ten Algorithms That Are Changing the World 403

Using Sort Routines 404

Looking for Things with Search Routines 404

Shaking Things Up with Random Numbers 405

Performing Data Compression 406

Keeping Data Secret 406

Changing the Data Domain 407

Analyzing Links 407

Spotting Data Patterns 408

Dealing with Automation and Automatic Responses 409

Creating Unique Identifiers 409

Chapter 22: Ten Algorithmic Problems Yet to Solve 411

Solving Problems Quickly 412

Solving 3SUM Problems More Efficiently 412

Making Matrix Multiplication Faster 413

Determining Whether an Application Will End 413

Creating and Using One-Way Functions 414

Multiplying Really Large Numbers 414

Dividing a Resource Equally 415

Reducing Edit Distance Calculation Time 415

Playing the Parity Game 416

Understanding Spatial Issues 416

Index 417

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.