by John Paul Mueller and Luca Massaron
Contents at a Glance
Introduction
Part 1: Getting Started
Introducing Algorithms
Considering Algorithm Design
Using Python to Work with Algorithms
Introducing Python for Algorithm Programming
Performing Essential Data Manipulations Using Python
Part 2: Understanding the Need to Sort and Search
Structuring Data
Arranging and Searching Data
Part 3: Exploring the World of Graphs
Understanding Graph Basics
Reconnecting the Dots
Discovering Graph Secrets
Getting the Right Web page
Part 4: Struggling with Big Data
Managing Big Data
Parallelizing Operations
Compressing Data
Part 5: Challenging Difficult Problems
Working with Greedy Algorithms
Relying on Dynamic Programming
Using Randomized Algorithms
Performing Local Search
Employing Linear Programming.
Considering Heuristics.
Part 6: The Part of Tens
Ten Algorithms That Are Changing the World
Ten Algorithmic Problems Yet to Solve
Index.
Purchase Now !
Just with Paypal
Just with Paypal
Book Details
Price
|
3.00 USD |
|---|---|
Pages
| 435 p |
File Size
|
7,349 KB |
File Type
|
PDF format |
ISBN
| 978-1-119-33049-3 (pbk) 978-1-119-33053-0 (ebk) 978-1-119-33052-3 (ebk) |
Copyright
| 2017 by John Wiley & Sons, Inc |
You need to learn about algorithms for school or work. Yet, all the books
you’ve tried on the subject end up being more along the lines of really good
sleep-inducing aids rather than texts to teach you something. Assuming
that you can get past the arcane symbols obviously written by a demented twoyear-
old with a penchant for squiggles, you end up having no idea of why you’d
even want to know anything about them. Most math texts are boring! However,
Algorithms For Dummies is different. The first thing you’ll note is that this book has
a definite lack of odd symbols (especially of the squiggly sort) floating about. Yes,
you see a few (it is a math book, after all), but what you find instead are clear
instructions for using algorithms that actually have names and a history behind
them to perform useful tasks. You’ll encounter simple coding techniques that perform
amazing things that will intrigue your friends and certainly make them
jealous as you perform amazing feats of math that they can’t begin to understand.
You get all this without having to strain your brain, even a little, and you won’t
even fall asleep (well, unless you really want to do so).
About This Book
Algorithms For Dummies is the math book that you wanted in college but didn’t get.
You discover, for example, that algorithms aren’t new. After all, the Babylonians
used algorithms to perform simple tasks as early as 1,600 BC. If the Babylonians
could figure this stuff out, certainly you can, too! This book actually has three
things that you won’t find in most math books:
»»Algorithms that have actual names and a historical basis so that you can
remember the algorithm and know why someone took time to create it
»»Simple explanations of how the algorithm performs amazing feats of data
manipulation, data analysis, or probability prediction
»»Code that shows how to use the algorithm without actually dealing with
arcane symbols that no one without a math degree can understand
Part of the emphasis of this book is on using the right tools. This book uses Python
to perform various tasks. Python has special features that make working with
algorithms significantly easier. For example, Python provides access to a huge
array of packages that let you do just about anything you can imagine, and more
than a few that you can’t. However, unlike many texts that use Python, this one
doesn’t bury you in packages. We use a select group of packages that provide great
flexibility with a lot of functionality, but don’t require you to pay anything. You
can go through this entire book without forking over a cent of your hard-earned money.
You also discover some interesting techniques in this book. The most important is
that you don’t just see the algorithms used to perform tasks; you also get an
explanation of how the algorithms work. Unlike many other books, Algorithms For
Dummies enables you to fully understand what you’re doing, but without requiring
you to have a PhD in math. Every one of the examples shows the expected output
and tells you why that output is important. You aren’t left with the feeling that
something is missing.
Of course, you might still be worried about the whole programming environment
issue, and this book doesn’t leave you in the dark there, either. At the beginning,
you find complete installation instructions for Anaconda, which is the Python
language Integrated Development Environment (IDE) used for this book. In addition,
quick primers (with references) help you understand the basic Python programming
that you need to perform. The emphasis is on getting you up and
running as quickly as possible, and to make examples straightforward and simple
so that the code doesn’t become a stumbling block to learning.
To help you absorb the concepts, this book uses the following conventions:
»»Text that you’re meant to type just as it appears in the book is in bold. The
exception is when you’re working through a step list: Because each step is
bold, the text to type is not bold.
»»Words that we want you to type in that are also in italics are used as placeholders,
which means that you need to replace them with something that
works for you. For example, if you see “Type Your Name and press Enter,” you
need to replace Your Name with your actual name.
»»We also use italics for terms we define. This means that you don’t have to rely
on other sources to provide the definitions you need.
»»Web addresses and programming code appear in monofont. If you’re reading
a digital version of this book on a device connected to the Internet, you can
click the live link to visit that website, like this: http://www.dummies.com.
»»When you need to click command sequences, you see them separated by a
special arrow, like this: File ➪ New File, which tells you to click File and then New File.
Table of Contents
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
Bookscreen
Beyond the Book
This book isn’t the end of your Python or algorithm learning experience — it’s
really just the beginning. We provide online content to make this book more flexible
and better able to meet your needs. That way, as we receive email from you,
we can address questions and tell you how updates to Python, or its associated
add-ons affect book content. In fact, you gain access to all these cool additions:
»»Cheat sheet: You remember using crib notes in school to make a better mark
on a test, don’t you? You do? Well, a cheat sheet is sort of like that. It provides
you with some special notes about tasks that you can do with Python,
Anaconda, and algorithms that not every other person knows. To find the
cheat sheet for this book, go to www.dummies.com and search for Algorithms
For Dummies Cheat Sheet. It contains really neat information such as finding
the algorithms that you commonly need to perform specific tasks.
»»Updates: Sometimes changes happen. For example, we might not have seen
an upcoming change when we looked into our crystal ball during the writing
of this book. In the past, this possibility simply meant that the book became
outdated and less useful, but you can now find updates to the book at
www.dummies.com/go/algorithmsfd.
In addition to these updates, check out the blog posts with answers to reader
questions and demonstrations of useful book-related techniques at
»»Companion files: Hey! Who really wants to type all the code in the book and
reconstruct all those plots manually? Most readers prefer to spend their time
actually working with Python, performing tasks using algorithms, and seeing
the interesting things they can do, rather than typing. Fortunately for you, the
examples used in the book are available for download, so all you need to do is
read the book to learn algorithm usage techniques. You can find these files at