Algorithms For Dummies

John Paul Mueller has produced 102 books and more than 600 articles to date on topics ranging from networking to machine learning. Luca Massaron is a data scientist specializing in organizing and interpreting big data and transforming it into smart data by means of the simplest and most effective data mining and machine learning techniques.

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 7

Chapter 1: Introducing Algorithms 9

Describing Algorithms 10

Defining algorithm uses 11

Finding algorithms everywhere 14

Using Computers to Solve Problems 15

Leveraging modern CPUs and GPUs 16

Working with special-purpose chips 17

Leveraging networks 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 hard problems 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

Starting by making it simpler 29

Breaking down a problem is usually better 30

Learning that Greed Can Be Good 31

Applying greedy reasoning 31

Reaching a good solution 32

Computing Costs and Following Heuristics 33

Representing the problem as a space 33

Going random and being blessed by luck 34

Using a heuristic and a cost function 35

Evaluating Algorithms 35

Simulating using abstract machines 36

Getting even more abstract 37

Working with functions 38

Chapter 3: Using Python to Work with Algorithms 43

Considering the Benefits of Python 45

Understanding why this book uses Python 45

Working with MATLAB 47

Considering other algorithm testing environments 48

Looking at the Python Distributions 48

Obtaining Analytics Anaconda 49

Considering Enthought Canopy Express 50

Considering pythonxy 50

Considering WinPython 51

Installing Python on Linux 51

Installing Python on MacOS 52

Installing Python on Windows 54

Downloading the Datasets and Example Code 58

Using Jupyter Notebook 58

Defining the code repository 59

Understanding the datasets used in this book 65

Chapter 4: Introducing Python for Algorithm Programming 67

Working with Numbers and Logic 68

Performing variable assignments 69

Doing arithmetic 70

Comparing data by using Boolean expressions 72

Creating and Using Strings 74

Interacting with Dates 76

Creating and Using Functions 77

Creating reusable functions 77

Calling functions 78

Using Conditional and Loop Statements 81

Making decisions using the if statement 81

Choosing between multiple options using nested decisions 82

Performing repetitive tasks using the for loop 83

Using the while statement 84

Storing Data Using Sets, Lists, and Tuples 85

Creating sets 85

Creating lists 86

Creating and using tuples 88

Defining Useful Iterators 89

Indexing Data Using Dictionaries 90

Chapter 5: Performing Essential Data Manipulations Using Python 91

Performing Calculations Using Vectors and Matrixes 92

Understanding scalar and vector operations 93

Performing vector multiplication 95

Creating a matrix is the right way to start 95

Multiplying matrixes 97

Defining advanced matrix operations 98

Creating Combinations the Right Way 100

Distinguishing permutations 100

Shuffling combinations 101

Facing repetitions 103

Getting the Desired Results Using Recursion 103

Explaining recursion 103

Eliminating tail call recursion 106

Performing Tasks More Quickly 107

Considering divide and conquer 107

Distinguishing between different possible solutions 110

Part 2: Understanding the Need to Sort and Search 113

Chapter 6: Structuring Data 115

Determining the Need for Structure 116

Making it easier to see the content 116

Matching data from various sources 117

Considering the need for remediation 118

Stacking and Piling Data in Order 121

Ordering in stacks 121

Using queues 123

Finding data using dictionaries 124

Working with Trees 125

Understanding the basics of trees 125

Building a tree 126

Representing Relations in a Graph 128

Going beyond trees 128

Building graphs 130

Chapter 7: Arranging and Searching Data 133

Sorting Data Using Mergesort and Quicksort 134

Defining why sorting data is important 134

Ordering data naïvely 135

Employing better sort techniques 137

Using Search Trees and the Heap 142

Considering the need to search effectively 143

Building a binary search tree 145

Performing specialized searches using a binary heap 146

Relying on Hashing 147

Putting everything into buckets 148

Avoiding collisions 149

Creating your own hash function 150

Part 3: Exploring The World Of Graphs 153

Chapter 8: Understanding Graph Basics 155

Explaining the Importance of Networks 156

Considering the essence of a graph 156

Finding graphs everywhere 158

Showing the social side of graphs 159

Understanding subgraphs 160

Defining How to Draw a Graph 161

Distinguishing the key attributes 162

Drawing the graph 163

Measuring Graph Functionality 164

Counting edges and vertexes 164

Computing centrality 166

Putting a Graph in Numeric Format 169

Adding a graph to a matrix 170

Using sparse representations 171

Using a list to hold a graph 171

Chapter 9: Reconnecting the Dots 173

Traversing a Graph Efficiently 174

Creating the graph 175

Applying breadth-first search 176

Applying depth-first search 177

Determining which application to use 179

Sorting the Graph Elements 180

Working on Directed Acyclic Graphs (DAGs) 181

Relying on topological sorting 182

Reducing to a Minimum Spanning Tree 183

Discovering the correct algorithms to use 185

Introducing priority queues 186

Leveraging Prim’s algorithm 187

Testing Kruskal’s algorithm 189

Determining which algorithm works best 191

Finding the Shortest Route 192

Defining what it means to find the shortest path 192

Explaining Dijkstra’s algorithm 194

Chapter 10: Discovering Graph Secrets 197

Envisioning Social Networks as Graphs 198

Clustering networks in groups 198

Discovering communities 201

Navigating a Graph 203

Counting the degrees of separation 204

Walking a graph randomly 206

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 208

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: Struggling With 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 232

Analyzing streams with the right recipe 234

Reserving the right data 235

Sketching an Answer from Stream Data 239

Filtering stream elements by heart 239

Demonstrating the Bloom filter 242

Finding the number of distinct elements 245

Learning to count objects in a stream 247

Chapter 13: Parallelizing Operations 249

Managing Immense Amounts of Data 250

Understanding the parallel paradigm 250

Distributing files and operations 252

Employing the MapReduce solution 254

Working Out Algorithms for MapReduce 258

Setting up a MapReduce simulation 259

Inquiring by mapping 261

Chapter 14: Compressing Data 265

Making Data Smaller 266

Understanding encoding 266

Considering the effects of compression 267

Choosing a particular kind of compression 269

Choosing your encoding wisely 271

Encoding using Huffman compression 273

Remembering sequences with LZW 275

Part 5: Challenging Difficult Problems 281

Chapter 15: Working with Greedy Algorithms 283

Deciding When It Is Better to Be Greedy 284

Understanding why greedy is good 285

Keeping greedy algorithms under control 286

Considering NP complete problems 288

Finding Out How Greedy Can Be Useful 290

Arranging cached computer data 290

Competing for resources 291

Revisiting Huffman coding 294

Chapter 16: Relying on Dynamic Programming 299

Explaining Dynamic Programming 300

Obtaining a historical basis 300

Making problems dynamic 301

Casting recursion dynamically 302

Leveraging memoization 305

Discovering the Best Dynamic Recipes 308

Looking inside the knapsack 308

Touring around cities 312

Approximating string search 317

Chapter 17: Using Randomized Algorithms 321

Defining How Randomization Works 322

Considering why randomization is needed 322

Understanding how probability works 323

Understanding distributions 325

Simulating the use of the Monte Carlo method 328

Putting Randomness into your Logic 330

Calculating a median using Quickselect 330

Doing simulations using Monte Carlo 333

Ordering faster with Quicksort 336

Chapter 18: Performing Local Search 339

Understanding Local Search 340

Knowing the neighborhood 340

Presenting local search tricks 342

Explaining hill climbing with n-queens 343

Discovering simulated annealing 346

Avoiding repeats using Tabu Search 347

Solving satisfiability of Boolean circuits 348

Solving 2-SAT using randomization 349

Implementing the Python code 350

Realizing that the starting point is important 354

Chapter 19: Employing Linear Programming 357

Using Linear Functions as a Tool 358

Grasping the basic math you need 359

Learning to simplify when planning 361

Working with geometry using simplex 361

Understanding the limitations 363

Using Linear Programming in Practice 364

Setting up PuLP at home 364

Optimizing production and revenue 365

Chapter 20: Considering Heuristics 371

Differentiating Heuristics 372

Considering the goals of heuristics 372

Going from genetic to AI 373

Routing Robots Using Heuristics 374

Scouting in unknown territories 374

Using distance measures as heuristics 376

Explaining Path Finding Algorithms 377

Creating a maze 377

Looking for a quick best-first route 380

Going heuristically around by A* 384

Part 6: The Part of Tens 389

Chapter 21: Ten Algorithms That Are Changing the World 391

Using Sort Routines 392

Looking for Things with Search Routines 393

Shaking Things Up with Random Numbers 393

Performing Data Compression 394

Keeping Data Secret 394

Changing the Data Domain 395

Analyzing Links 395

Spotting Data Patterns 396

Dealing with Automation and Automatic Responses 397

Creating Unique Identifiers 397

Chapter 22: Ten Algorithmic Problems Yet to Solve 399

Dealing with Text Searches 400

Differentiating Words 400

Determining Whether an Application Will End 401

Creating and Using One-Way Functions 401

Multiplying Really Large Numbers 402

Dividing a Resource Equally 402

Reducing Edit Distance Calculation Time 403

Solving Problems Quickly 403

Playing the Parity Game 404

Understanding Spatial Issues 404

Index 405