Learning Algorithms

Learning Algorithms

by George Heineman
Released July 2021
Publisher(s): O'Reilly Media, Inc.
ISBN: 9781492091011

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

O’Reilly members get unlimited access to live online training experiences, plus books, videos, and digital content from O’Reilly and nearly 200 trusted publishing partners.

Start your free trial

Book description

When it comes to writing efficient code, every software professional needs to have an effective working knowledge of algorithms. In this practical book, author George Heineman (Algorithms in a Nutshell) provides concise and informative descriptions of key algorithms that improve coding in multiple languages. Software developers, testers, and maintainers will discover how algorithms solve computational problems creatively.

Each chapter builds on earlier chapters through eye-catching visuals and a steady rollout of essential concepts, including an algorithm analysis to classify the performance of every algorithm presented in the book. At the end of each chapter, youâ??ll get to apply what youâ??ve learned to a novel challenge problemâ??simulating the experience you might find in a technical code interview.

With this book, you will:

  • Examine fundamental algorithms central to computer science and software engineering
  • Learn common strategies for efficient problem solvingâ??such as divide and conquer, dynamic programming, and greedy approaches
  • Analyze code to evaluate time complexity using big O notation
  • Use existing Python libraries and data structures to solve problems using algorithms
  • Understand the main steps of important algorithms

Table of contents

  1. Foreword
  2. Preface
    1. Who This Book Is For
    2. About the Code
    3. Conventions Used in This Book
    4. O’Reilly Online Learning
    5. How to Contact Us
    6. Acknowledgments
  3. 1. Problem Solving
    1. What Is an Algorithm?
    2. Finding the Largest Value in an Arbitrary List
    3. Counting Key Operations
    4. Models Can Predict Algorithm Performance
    5. Find Two Largest Values in an Arbitrary List
    6. Tournament Algorithm
    7. Time Complexity and Space Complexity
    8. Summary
    9. Challenge Exercises
  4. 2. Analyzing Algorithms
    1. Using Empirical Models to Predict Performance
    2. Multiplication Can Be Faster
    3. Performance Classes
    4. Asymptotic Analysis
    5. Counting All Operations
    6. Counting All Bytes
    7. When One Door Closes, Another One Opens
    8. Binary Array Search
    9. Almost as Easy as π
    10. Two Birds with One Stone
    11. Pulling It All Together
    12. Curve Fitting Versus Lower and Upper Bounds
    13. Summary
    14. Challenge Exercises
  5. 3. Better Living Through Better Hashing
    1. Associating Values with Keys
    2. Hash Functions and Hash Codes
    3. A Hashtable Structure for (Key, Value) Pairs
    4. Detecting and Resolving Collisions with Linear Probing
    5. Separate Chaining with Linked Lists
    6. Removing an Entry from a Linked List
    7. Evaluation
    8. Growing Hashtables
    9. Analyzing the Performance of Dynamic Hashtables
    10. Perfect Hashing
    11. Iterate Over (key, value) Pairs
    12. Summary
    13. Challenge Exercises
  6. 4. Heaping It On
    1. Max Binary Heaps
    2. Inserting a (value, priority)
    3. Removing the Value with Highest Priority
    4. Representing a Binary Heap in an Array
    5. Implementation of Swim and Sink
    6. Summary
    7. Challenge Exercises
  7. 5. Sorting Without a Hat
    1. Sorting by Swapping
    2. Selection Sort
    3. Anatomy of a Quadratic Sorting Algorithm
    4. Analyze Performance of Insertion Sort and Selection Sort
    5. Recursion and Divide and Conquer
    6. Merge Sort
    7. Quicksort
    8. Heap Sort
    9. Performance Comparison of O(N log N) Algorithms
    10. Tim Sort
    11. Summary
    12. Challenge Exercises
  8. 6. Binary Trees: Infinity in the Palm of Your Hand
    1. Getting Started
    2. Binary Search Trees
    3. Searching for Values in a Binary Search Tree
    4. Removing Values from a Binary Search Tree
    5. Traversing a Binary Tree
    6. Analyzing Performance of Binary Search Trees
    7. Self-Balancing Binary Trees
    8. Analyzing Performance of Self-Balancing Trees
    9. Using Binary Tree as (key, value) Symbol Table
    10. Using the Binary Tree as a Priority Queue
    11. Summary
    12. Challenge Exercises
  9. 7. Graphs: Only Connect!
    1. Graphs Efficiently Store Useful Information
    2. Using Depth First Search to Solve a Maze
    3. Breadth First Search Offers Different Searching Strategy
    4. Directed Graphs
    5. Graphs with Edge Weights
    6. Dijkstra’s Algorithm
    7. All-Pairs Shortest Path
    8. Floyd–Warshall Algorithm
    9. Summary
    10. Challenge Exercises
  10. 8. Wrapping It Up
    1. Python Built-in Data Types
    2. Implementing Stack in Python
    3. Implementing Queues in Python
    4. Heap and Priority Queue Implementations
    5. Future Exploration
  11. Index
  12. About the Author

Product information

  • Title: Learning Algorithms
  • Author(s): George Heineman
  • Release date: July 2021
  • Publisher(s): O'Reilly Media, Inc.
  • ISBN: 9781492091011