Grokking Algorithms

Synopsis

Summary

Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and artificial intelligence. Each carefully presented example includes helpful diagrams and fully annotated code samples in Python.

Learning about algorithms doesn't have to be boring! Get a sneak peek at the fun, illustrated, and friendly examples you'll find in Grokking Algorithms on Manning Publications' YouTube channel.

Continue your journey into the world of algorithms with Algorithms in Motion, a practical, hands-on video course available exclusively at Manning.com (www.manning.com/livevideo/algorithms-​in-motion).

Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications.

About the Technology

An algorithm is nothing more than a step-by-step procedure for solving a problem. The algorithms you'll use most often as a programmer have already been discovered, tested, and proven. If you want to understand them but refuse to slog through dense multipage proofs, this is the book for you. This fully illustrated and engaging guide makes it easy to learn how to use the most important algorithms effectively in your own programs.

About the Book

Grokking Algorithms is a friendly take on this core computer science topic. In it, you'll learn how to apply common algorithms to the practical programming problems you face every day. You'll start with tasks like sorting and searching. As you build up your skills, you'll tackle more complex problems like data compression and artificial intelligence. Each carefully presented example includes helpful diagrams and fully annotated code samples in Python. By the end of this book, you will have mastered widely applicable algorithms as well as how and when to use them.

What's Inside

• Covers search, sort, and graph algorithms
• Over 400 pictures with detailed walkthroughs
• Performance trade-offs between algorithms
• Python-based code samples

About the Reader

This easy-to-read, picture-heavy introduction is suitable for self-taught programmers, engineers, or anyone who wants to brush up on algorithms.

About the Author

Aditya Bhargava is a Software Engineer with a dual background in Computer Science and Fine Arts. He blogs on programming at adit.io.

Table of Contents

1. Introduction to algorithms
2. Selection sort
3. Recursion
4. Quicksort
5. Hash tables
6. Breadth-first search
7. Dijkstra's algorithm
8. Greedy algorithms
9. Dynamic programming
10. K-nearest neighbors

Read more

Summary

Chapter 1: Introduction to Algorithms

* Summary:
* Defines an algorithm as a step-by-step procedure to solve a problem.
* Explains the importance of efficiency, correctness, and simplicity.
* Introduces the Big-O notation for describing algorithm complexity.
* Real Example:
* A recipe is an algorithm for cooking a meal. The ingredients are inputs, the steps are instructions, and the finished dish is the output.

Chapter 2: Sorting Algorithms

* Summary:
* Describes different sorting algorithms, including bubble sort, selection sort, insertion sort, merge sort, and quick sort.
* Compares their time complexities.
* Shows how to choose the best sorting algorithm for a given scenario.
* Real Example:
* Sorting a list of students by name using the bubble sort algorithm: Iterate through the list, comparing adjacent elements and swapping them if they are out of order.

Chapter 3: Searching Algorithms

* Summary:
* Discusses linear search, binary search, and hashing.
* Explains their time complexities and when to use each one.
* Introduces the concept of a hash table for efficient key-value lookup.
* Real Example:
* Searching for a specific word in a text document using linear search: Iterate through the document, checking each word until the desired word is found.

Chapter 4: Divide and Conquer

* Summary:
* Presents the divide-and-conquer paradigm for solving complex problems.
* Implements merge sort and quicksort using this technique.
* Explains recursion and backtracking as special cases of divide and conquer.
* Real Example:
* Finding the maximum value in an array using divide and conquer: Split the array into two halves, find the maximum in each half, and then compare the two maxima.

Chapter 5: Greedy Algorithms

* Summary:
* Introduces greedy algorithms that make locally optimal choices at each step.
* Covers Kruskal's algorithm for finding a minimum spanning tree.
* Discusses the limitations of greedy algorithms.
* Real Example:
* Planning a road trip by finding the shortest path between cities using a greedy algorithm that chooses the next city with the shortest distance at each step.

Chapter 6: Dynamic Programming

* Summary:
* Explains dynamic programming as a technique for solving problems by breaking them down into subproblems and storing intermediate results.
* Implements the Fibonacci sequence and longest common subsequence problems using dynamic programming.
* Real Example:
* Solving the knapsack problem using dynamic programming: Find the most valuable subset of items that fits within a given capacity, by considering each item and its combinations step-by-step.

Chapter 7: Graph Algorithms

* Summary:
* Introduces basic graph concepts and traversal techniques.
* Covers depth-first search (DFS) and breadth-first search (BFS).
* Discusses algorithms for finding connected components and shortest paths.
* Real Example:
* Finding the shortest path between two nodes in a graph using BFS: Explore all paths of increasing length until reaching the destination node.

Chapter 8: Advanced Topics

* Summary:
* Delves into advanced topics such as network flow algorithms, randomized algorithms, and computational geometry.
* Explores the Maximum Flow Minimum Cut theorem and its applications.
* Introduces randomized algorithms for solving complex problems efficiently.
* Real Example:
* Optimizing the flow of data in a network using the Max-Flow Min-Cut theorem: Find the maximum amount of data that can flow through the network without causing congestion.