Hjem

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 Ch