Dive Into Algorithms is a wide-ranging, Pythonic tour of many of the world's most interesting algorithms. With little more than a bit of computer programming experience and basic high-school math, you'll explore standard computer science algorithms for searching, sorting, and optimization; human-based algorithms that help us determine how to catch a baseball or eat the right amount at a buffet; and advanced algorithms like ones used in machine learning and artificial intelligence. You'll even explore how ancient Egyptians and Russian peasants used algorithms to multiply numbers, how the ancient Greeks used them to find greatest common divisors, and how Japanese scholars in the age of samurai designed algorithms capable of generating magic squares.
You'll explore algorithms that are useful in pure mathematics and learn how mathematical ideas can improve algorithms. You'll learn about an algorithm for generating continued fractions, one for quick calculations of square roots, and another for generating seemingly random sets of numbers.
You'll also learn how to:
• Use algorithms to debug code, maximize revenue, schedule tasks, and create decision trees
• Measure the efficiency and speed of algorithms
• Generate Voronoi diagrams for use in various geometric applications
• Use algorithms to build a simple chatbot, win at board games, or solve sudoku puzzles
• Write code for gradient ascent and descent algorithms that can find the maxima and minima of functions
• Use simulated annealing to perform global optimization
• Build a decision tree to predict happiness based on a person's characteristics
Once you've finished this book you'll understand how to code and implement important algorithms as well as how to measure and optimize their performance, all while learning the nitty-gritty details of today's most powerful algorithms.
Author Bio
Bradford Tuckfield, PhD, is a data scientist and consultant. The author of Applied Unsupervised Learning with R, his research has appeared in top academic journals in math, business management, and medicine. He has also written essays about culture for magazines and policy journals.
Author(s): Bradford Tuckfield
Edition: 1
Publisher: No Starch Press
Year: 2021
Language: English
Commentary: Vector PDF
Pages: 248
City: San Francisco, CA
Tags: Artificial Intelligence; Machine Learning; Algorithms; Natural Language Processing; Python; Optimization; Search Algorithms; Geometry; Sorting Algorithms; Elementary
Contents in Detail
Acknowledgments
Introduction
Who Is This Book For?
About This Book
Setting Up the Environment
Install Python on Windows
Install Python on macOS
Install Python on Linux
Installing Third-Party Modules
Summary
Chapter 1: Problem-Solving With Algorithms
The Analytic Approach
The Galilean Model
The Solve-for-x Strategy
The Inner Physicist
The Algorithmic Approach
Thinking with Your Neck
Applying Chapman’s Algorithm
Solving Problems with Algorithms
Summary
Chapter 2: Algorithms in History
Russian Peasant Multiplication
Doing RPM by Hand
Implementing RPM in Python
Euclid’s Algorithm
Doing Euclid’s Algorithm by Hand
Implementing Euclid’s Algorithm in Python
Japanese Magic Squares
Creating the Luo Shu Square in Python
Implementing Kurushima's Algorithm in Python
Summary
Chapter 3: Maximizing and Minimizing
Setting Tax Rates
Steps in the Right Direction
Turning the Steps into an Algorithm
Objections to Gradient Ascent
The Problem of Local Extrema
Education and Lifetime Income
Climbing the Education Hill—the Right Way
From Maximization to Minimization
Hill Climbing in General
When Not to Use an Algorithm
Summary
Chapter 4: Sorting and Searching
Insertion Sort
Putting the Insertion in Insertion Sort
Sorting via Insertion
Measuring Algorithm Efficiency
Why Aim for Efficiency?
Measuring Time Precisely
Counting Steps
Comparing to Well-Known Functions
Adding Even More Theoretical Precision
Using Big O Notation
Merge Sort
Merging
From Merging to Sorting
Sleep Sort
From Sorting to Searching
Binary Search
Applications of Binary Search
Summary
Chapter 5: Pure Math
Continued Fractions
Compressing and Communicating Phi
More about Continued Fractions
An Algorithm for Generating Continued Fractions
From Decimals to Continued Fractions
From Fractions to Radicals
Square Roots
The Babylonian Algorithm
Square Roots in Python
Random Number Generators
The Possibility of Randomness
Linear Congruential Generators
Judging a PRNG
The Diehard Tests for Randomness
Linear Feedback Shift Registers
Summary
Chapter 6: Advanced Optimization
Life of a Salesman
Setting Up the Problem
Brains vs. Brawn
The Nearest Neighbor Algorithm
Implementing Nearest Neighbor Search
Checking for Further Improvements
Algorithms for the Avaricious
Introducing the Temperature Function
Simulated Annealing
Tuning Our Algorithm
Avoiding Major Setbacks
Allowing Resets
Testing Our Performance
Summary
Chapter 7: Geometry
The Postmaster Problem
Triangles 101
Advanced Graduate-Level Triangle Studies
Finding the Circumcenter
Increasing Our Plotting Capabilities
Delaunay Triangulation
Incrementally Generating Delaunay Triangulations
Implementing Delaunay Triangulations
From Delaunay to Voronoi
Summary
Chapter 8: Language
Why Language Algorithms Are Hard
Space Insertion
Defining a Word List and Finding Words
Dealing with Compound Words
Checking Between Existing Spaces for Potential Words
Using an Imported Corpus to Check for Valid Words
Finding First and Second Halves of Potential Words
Phrase Completion
Tokenizing and Getting N-grams
Our Strategy
Finding Candidate n + 1-grams
Selecting a Phrase Based on Frequency
Summary
Chapter 9: Machine Learning
Decision Trees
Building a Decision Tree
Downloading Our Dataset
Looking at the Data
Splitting Our Data
Smarter Splitting
Choosing Splitting Variables
Adding Depth
Evaluating Our Decision Tree
The Problem of Overfitting
Improvements and Refinements
Random Forests
Summary
Chapter 10: Artificial Intelligence
La Pipopipette
Drawing the Board
Representing Games
Scoring Games
Game Trees and How to Win a Game
Building Our Tree
Winning a Game
Adding Enhancements
Summary
Chapter 11: Forging Ahead
Doing More with Algorithms
Building a Chatbot
Text Vectorization
Vector Similarity
Becoming Better and Faster
Algorithms for the Ambitious
Solving the Deepest Mysteries
Index
