Dive Into Algorithms

Dive Into Algorithms

by Bradford Tuckfield
Released January 2021
Publisher(s): No Starch Press
ISBN: 9781718500686

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

  1. Cover
  2. Titlepage
  3. Copyright
  4. Dedication
  5. About the Author
  6. About the Technical Reviewer
  7. Acknowledgments
  8. Introduction
    1. Who Is This Book For?
    2. About This Book
    3. Setting Up the Environment
      1. Install Python on Windows
      2. Install Python on macOS
      3. Install Python on Linux
      4. Installing Third-Party Modules
    4. Summary
  9. Chapter 1: Problem-Solving With Algorithms
    1. The Analytic Approach
      1. The Galilean Model
      2. The Solve-for-x Strategy
      3. The Inner Physicist
    2. The Algorithmic Approach
      1. Thinking with Your Neck
      2. Applying Chapman’s Algorithm
      3. Solving Problems with Algorithms
    3. Summary
  10. Chapter 2: Algorithms in History
    1. Russian Peasant Multiplication
      1. Doing RPM by Hand
      2. Implementing RPM in Python
    2. Euclid’s Algorithm
      1. Doing Euclid’s Algorithm by Hand
      2. Implementing Euclid’s Algorithm in Python
    3. Japanese Magic Squares
      1. Creating the Luo Shu Square in Python
      2. Implementing Kurushima's Algorithm in Python
    4. Summary
  11. Chapter 3: Maximizing and Minimizing
    1. Setting Tax Rates
      1. Steps in the Right Direction
      2. Turning the Steps into an Algorithm
    2. Objections to Gradient Ascent
    3. The Problem of Local Extrema
      1. Education and Lifetime Income
      2. Climbing the Education Hill—the Right Way
    4. From Maximization to Minimization
    5. Hill Climbing in General
    6. When Not to Use an Algorithm
    7. Summary
  12. Chapter 4: Sorting and Searching
    1. Insertion Sort
      1. Putting the Insertion in Insertion Sort
      2. Sorting via Insertion
    2. Measuring Algorithm Efficiency
      1. Why Aim for Efficiency?
      2. Measuring Time Precisely
      3. Counting Steps
      4. Comparing to Well-Known Functions
      5. Adding Even More Theoretical Precision
      6. Using Big O Notation
    3. Merge Sort
      1. Merging
      2. From Merging to Sorting
    4. Sleep Sort
    5. From Sorting to Searching
      1. Binary Search
      2. Applications of Binary Search
    6. Summary
  13. Chapter 5: Pure Math
    1. Continued Fractions
      1. Compressing and Communicating Phi
      2. More about Continued Fractions
      3. An Algorithm for Generating Continued Fractions
      4. From Decimals to Continued Fractions
      5. From Fractions to Radicals
    2. Square Roots
      1. The Babylonian Algorithm
      2. Square Roots in Python
    3. Random Number Generators
      1. The Possibility of Randomness
      2. Linear Congruential Generators
      3. Judging a PRNG
      4. The Diehard Tests for Randomness
      5. Linear Feedback Shift Registers
    4. Summary
  14. Chapter 6: Advanced Optimization
    1. Life of a Salesman
      1. Setting Up the Problem
      2. Brains vs. Brawn
      3. The Nearest Neighbor Algorithm
      4. Implementing Nearest Neighbor Search
      5. Checking for Further Improvements
      6. Algorithms for the Avaricious
      7. Introducing the Temperature Function
    2. Simulated Annealing
      1. Tuning Our Algorithm
      2. Avoiding Major Setbacks
      3. Allowing Resets
      4. Testing Our Performance
    3. Summary
  15. Chapter 7: Geometry
    1. The Postmaster Problem
    2. Triangles 101
    3. Advanced Graduate-Level Triangle Studies
      1. Finding the Circumcenter
      2. Increasing Our Plotting Capabilities
    4. Delaunay Triangulation
      1. Incrementally Generating Delaunay Triangulations
      2. Implementing Delaunay Triangulations
    5. From Delaunay to Voronoi
    6. Summary
  16. Chapter 8: Language
    1. Why Language Algorithms Are Hard
    2. Space Insertion
      1. Defining a Word List and Finding Words
      2. Dealing with Compound Words
      3. Checking Between Existing Spaces for Potential Words
      4. Using an Imported Corpus to Check for Valid Words
      5. Finding First and Second Halves of Potential Words
    3. Phrase Completion
      1. Tokenizing and Getting N-grams
      2. Our Strategy
      3. Finding Candidate n + 1-grams
      4. Selecting a Phrase Based on Frequency
    4. Summary
  17. Chapter 9: Machine Learning
    1. Decision Trees
    2. Building a Decision Tree
      1. Downloading Our Dataset
      2. Looking at the Data
      3. Splitting Our Data
      4. Smarter Splitting
      5. Choosing Splitting Variables
      6. Adding Depth
    3. Evaluating Our Decision Tree
      1. The Problem of Overfitting
      2. Improvements and Refinements
    4. Random Forests
    5. Summary
  18. Chapter 10: Artificial Intelligence
    1. La Pipopipette
    2. Drawing the Board
    3. Representing Games
    4. Scoring Games
    5. Game Trees and How to Win a Game
      1. Building Our Tree
      2. Winning a Game
      3. Adding Enhancements
    6. Summary
  19. Chapter 11: Forging Ahead
    1. Doing More with Algorithms
    2. Building a Chatbot
      1. Text Vectorization
      2. Vector Similarity
    3. Becoming Better and Faster
    4. Algorithms for the Ambitious
    5. Solving the Deepest Mysteries
  20. Index

Product information

  • Title: Dive Into Algorithms
  • Author(s): Bradford Tuckfield
  • Release date: January 2021
  • Publisher(s): No Starch Press
  • ISBN: 9781718500686