Algorithms For Dummies

Оглавление

John Paul Mueller. Algorithms For Dummies

Algorithms For Dummies® To view this book's Cheat Sheet, simply go to www.dummies.com and search for “Algorithms For Dummies Cheat Sheet” in the Search box. Table of Contents

List of Illustrations

Guide

Pages

Introduction

About This Book

Foolish Assumptions

Icons Used in This Book

Beyond the Book

Where to Go from Here

Getting Started with Algorithms

Introducing Algorithms

Describing Algorithms

The right way to make toast: Defining algorithm uses

Finding algorithms everywhere

Using Computers to Solve Problems

Getting the most out of modern CPUs and GPUs

Working with special-purpose chips

Networks: Sharing is more than caring

Leveraging available data

Distinguishing between Issues and Solutions

Being correct and efficient

Discovering there is no free lunch

Adapting the strategy to the problem

Describing algorithms in a lingua franca

Facing problems that are like brick walls, only harder

Structuring Data to Obtain a Solution

Understanding a computer’s point of view

Arranging data makes the difference

Considering Algorithm Design

Starting to Solve a Problem

Modeling real-world problems

Finding solutions and counterexamples

Standing on the shoulders of giants

Dividing and Conquering

Avoiding brute-force solutions

Keeping it simple, silly (KISS)

Breaking down a problem is usually better

Learning that Greed Can Be Good

Applying greedy reasoning

Reaching a good solution

Computing Costs and Following Heuristics

Representing the problem as a space

Going random and being blessed by luck

Using a heuristic and a cost function

Evaluating Algorithms

Simulating using abstract machines

Getting even more abstract

Working with functions

Working with Google Colab

Defining Google Colab

Understanding what Google Colab does

SOME FIREFOX ODDITIES

Getting familiar with Google Colab features

Locating commands

Configuring settings

Customizing keyboard shortcuts

Comparing files

Working with Notebooks

Creating a new notebook

Opening existing notebooks

Using Google Drive for existing notebooks

Using GitHub for existing notebooks

Using local storage for existing notebooks

Saving notebooks

Using Drive to save notebooks

Using GitHub to save notebooks

Using GitHub gists to save notebooks

Performing Common Tasks

Creating code cells

Creating text cells

Creating special cells

Working with headings

Working with a table of contents

Editing cells

Moving cells

Using Hardware Acceleration

Executing the Code

Getting Help

Performing Essential Data Manipulations Using Python

Performing Calculations Using Vectors and Matrixes

Understanding scalar and vector operations

Performing vector multiplication

Creating a matrix is the right way to start

Multiplying matrixes

Defining advanced matrix operations

Creating Combinations the Right Way

Distinguishing permutations

Shuffling combinations

Facing repetitions

Getting the Desired Results Using Recursion

Explaining recursion

Eliminating tail call recursion

Performing Tasks More Quickly

Considering divide and conquer

Distinguishing between different possible solutions

Developing a Matrix Computation Class

Avoiding the Use of NumPy

Understanding Why Using a Class is Important

Building the Basic Class

Creating a matrix

Printing the resulting matrix

Accessing specific matrix elements

Performing scalar and matrix addition

Performing multiplication

Element-wise product

Dot product

Manipulating the Matrix

Transposing a matrix

Calculating the determinant

Why is the matrix so determined?

Creating some prerequisite code

Performing the calculation

Flattening the matrix

Understanding the Need to Sort and Search

Structuring Data

Determining the Need for Structure

Making it easier to see the content

Matching data from various sources

Considering the need for remediation

Dealing with data duplication

Dealing with missing values

Understanding other remediation issues

Stacking and Piling Data in Order

Ordering in stacks

Using queues

Finding data using dictionaries

Working with Trees

Understanding the basics of trees

Building a tree

Representing Relations in a Graph

Going beyond trees

Building graphs

Arranging and Searching Data

Sorting Data Using Merge Sort and Quick Sort

Understanding why sorting data is important

Using a selection sort

Switching to an insertion sort

Employing better sort techniques

Rearranging data with merge sort

Solving sorting issues the best way using quick sort

UNDERSTANDING QUICK SORT WORST-CASE PERFORMANCE

Using Search Trees and the Heap

Considering the need to search effectively

Building a binary search tree

Performing specialized searches using a binary heap

Relying on Hashing

Putting everything into buckets

Avoiding collisions

Creating your own hash function

DISCOVERING UNEXPECTED USES OF HASHES

Exploring the World of Graphs

Understanding Graph Basics

Explaining the Importance of Networks

Considering the essence of a graph

Finding graphs everywhere

Showing the social side of graphs

Understanding subgraphs

Defining How to Draw a Graph

Distinguishing the key attributes

NETWORKX API

Drawing the graph

Measuring Graph Functionality

Counting edges and vertexes

USE OF WHITESPACE IN OUTPUT

Computing centrality

Putting a Graph in Numeric Format

Adding a graph to a matrix

Using sparse representations

Using a list to hold a graph

Reconnecting the Dots

Traversing a Graph Efficiently

CONSIDERING REDUNDANCY

Creating the graph

Applying breadth-first search

Applying depth-first search

Determining which application to use

Sorting the Graph Elements

GRAPHS WITH LOOPS

Working on Directed Acyclic Graphs (DAGs)

Relying on topological sorting

Reducing to a Minimum Spanning Tree

Getting the minimum spanning tree historical context

Working with unweighted versus weighted graphs

Creating a minimum spanning tree example

Discovering the correct algorithms to use

Introducing priority queues

Leveraging Prim’s algorithm

Testing Kruskal’s algorithm

Determining which algorithm works best

Finding the Shortest Route

Defining what it means to find the shortest path

Adding a negative edge

Explaining Dijkstra’s algorithm

Explaining the Bellman-Ford algorithm

Routing information more efficiently

Proving algorithm versatility

Explaining the Floyd-Warshall algorithm

Comparing with other algorithms

Using three passes is better

Discovering Graph Secrets

Envisioning Social Networks as Graphs

Clustering networks in groups

Discovering communities

Navigating a Graph

Counting the degrees of separation

Walking a graph randomly

Getting the Right Web page

Finding the World in a Search Engine

Searching the Internet for data

Considering how to find the right data

Explaining the PageRank Algorithm

Understanding the reasoning behind the PageRank algorithm

Explaining the nuts and bolts of PageRank

Implementing PageRank

Implementing a Python script

Struggling with a naive implementation

Introducing boredom and teleporting

Looking inside the life of a search engine

Considering other uses of PageRank

Going Beyond the PageRank Paradigm

Introducing semantic queries

Using AI for ranking search results

Wrangling Big Data

Managing Big Data

Transforming Power into Data

Understanding Moore’s implications

POLITICS AND THE LEGAL STUFF

Finding data everywhere

Getting algorithms into business

Volume

Velocity

Variety

Veracity

Streaming Flows of Data

Analyzing streams with the right recipe

Reserving the right data

Sketching an Answer from Stream Data

Filtering stream elements by heart

Adding elements to Bloom filters

Searching a Bloom filter for an element

Demonstrating the Bloom filter

Finding the number of distinct elements

Learning to count objects in a stream

Parallelizing Operations

Managing Immense Amounts of Data

Understanding the parallel paradigm

Distributing files and operations

Employing the MapReduce solution

USING A PACKAGE SOLUTION FOR MAPREDUCE

Explaining map

Explaining reduce

Distributing operations

Working Out Algorithms for MapReduce

Setting up a MapReduce simulation

Inquiring by mapping

Compressing and Concealing Data

Making Data Smaller

Understanding encoding

Considering the effects of compression

Choosing a particular kind of compression

AN EXAMPLE OF LOSSY COMPRESSION BENEFITS

Choosing your encoding wisely

Encoding using Huffman compression

Remembering sequences with LZW

Hiding Your Secrets with Cryptography

Substituting characters

Working with AES encryption

FIXING THE TIME.CLOCK() ERROR

Challenging Difficult Problems

Working with Greedy Algorithms

Deciding When It Is Better to Be Greedy

Understanding why greedy is good

Keeping greedy algorithms under control

Considering NP complete problems

Finding Out How Greedy Can Be Useful

Arranging cached computer data

Competing for resources

Addressing customer satisfaction

Meeting deadlines

Revisiting Huffman coding

Relying on Dynamic Programming

Explaining Dynamic Programming

Obtaining a historical basis

Making problems dynamic

Casting recursion dynamically

Leveraging memoization

Discovering the Best Dynamic Recipes

Looking inside the knapsack

Touring around cities

Approximating string search

Using Randomized Algorithms

Defining How Randomization Works

Considering why randomization is needed

Understanding how probability works

Understanding distributions

Simulating the use of the Monte Carlo method

Putting Randomness into your Logic

Calculating a median using quick select

Doing simulations using Monte Carlo

Ordering faster with quick sort

Performing Local Search

Understanding Local Search

Knowing the neighborhood

Presenting local search tricks

Explaining hill climbing with n-queens

Discovering simulated annealing

Avoiding repeats using Tabu Search

Solving Satisfiability of Boolean Circuits

Solving 2-SAT using randomization

Implementing the Python code

Realizing that the starting point is important

Employing Linear Programming

Using Linear Functions as a Tool

Grasping the basic math you need

Learning to simplify when planning

Working with geometry using simplex

Understanding the limitations

Using Linear Programming in Practice

Setting up PuLP at home

Optimizing production and revenue

Considering Heuristics

Differentiating Heuristics

Considering the goals of heuristics

Going from genetic to AI

Routing Robots Using Heuristics

Scouting in unknown territories

Using distance measures as heuristics

Explaining Path Finding Algorithms

Creating a maze

Looking for a quick best-first route

Going heuristically around by A*

The Part of Tens

Ten Algorithms That Are Changing the World

Using Sort Routines

Looking for Things with Search Routines

Shaking Things Up with Random Numbers

Performing Data Compression

Keeping Data Secret

Changing the Data Domain

Analyzing Links

Spotting Data Patterns

Dealing with Automation and Automatic Responses

Creating Unique Identifiers

Ten Algorithmic Problems Yet to Solve

Solving Problems Quickly

Solving 3SUM Problems More Efficiently

Making Matrix Multiplication Faster

Determining Whether an Application Will End

Creating and Using One-Way Functions

Multiplying Really Large Numbers

Dividing a Resource Equally

Reducing Edit Distance Calculation Time

Playing the Parity Game

Understanding Spatial Issues

Index. A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Z

About the Authors

John’s Dedication

Luca’s Dedication

John’s Acknowledgments

Luca’s Acknowledgments

WILEY END USER LICENSE AGREEMENT

Отрывок из книги

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 two-year-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, 2nd Edition 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 and that perform useful tasks. You’ll encounter simple coding techniques to perform amazing tasks that will intrigue your friends. You can certainly make them jealous as you perform 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). New in this edition of the book are more details about how algorithms work, and you even get to create your own basic math package so that you know how to do it for that next job interview.

Algorithms For Dummies, 2nd Edition 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:

.....

A RAM simulation places the algorithm in a situation that’s both language and machine-agnostic (it’s independent of programming language and computer type). However, explaining how a RAM simulation works to others requires quite an effort. The analysis of algorithms proposes to use the number of operations you get from a RAM simulation and turn them into a mathematical function expressing how your algorithm behaves in terms of time, which is a quantification of the steps or operations required when the number of data inputs grows. For instance, if your algorithm sorts objects, you can express complexity using a function that reports how many operations it needs depending on the number of objects it receives.

.....