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
