## Grokking Algorithms: An Illustrated Guide for Programmers and Other Curious People 1st Edition

**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.

**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 ebook 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 eBook**

*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 ebook, you will have mastered widely applicable algorithms as well as how and when to use them.

his book is designed to be easy to follow. I avoid big leaps of thought. Any time a new concept is introduced, I explain it right away or tell you when I’ll explain it. Core concepts are reinforced with exercises and multiple explanations so that you can check your assumptions and

make sure you’re following along.

I lead with examples. Instead of writing symbol soup, my goal is to make it easy for you to visualize these concepts. I also think we learn best by being able to recall something we already know, and examples make recall easier. So when you’re trying to remember the difference between arrays and linked lists (explained in chapter 2), you can just think about getting seated for a movie. Also, at the risk of stating the obvious, I’m a visual learner. his book is chock-full of images.

The contents of the book are carefully curated. There’s no need to write a book that covers every sorting algorithm—that’s why we have Wikipedia and Khan Academy. All the algorithms I’ve included are practical. I’ve found them useful in my job as a software engineer, and they provide a good foundation for more complex topics. Happy reading!

### Roadmap

The first three chapters of this book lay the foundations:

- Chapter 1—You’ll learn your first practical algorithm: binary search. You also learn to analyze the speed of an algorithm using Big O

notation. Big O notation is used throughout the book to analyze how slow or fast an algorithm is.

- Chapter 2—You’ll learn about two fundamental data structures: arrays and linked lists. these data structures are used throughout the

book, and they’re used to make more advanced data structures like hash tables (chapter 5).

- Chapter 3—You’ll learn about recursion, a handy technique used by many algorithms (such as quicksort, covered in chapter 4).

In my experience, Big O notation and recursion are challenging topics for beginners. So I’ve slowed down and spent extra time on these

sections.

The rest of the book presents algorithms with broad applications:

- Problem-solving techniques—Covered in chapters 4, 8, and 9. If you come across a problem and aren’t sure how to solve it efficiently, try divide and conquer (chapter 4) or dynamic programming (chapter 9). Or you may realize there’s no efficient solution, and get an approximate answer using a greedy algorithm instead (chapter 8).

- Hash tables—Covered in chapter 5. A hash table is a very useful data structure. It contains sets of key and value pairs, like a person’s name and their email address, or a username and the associated password. It’s hard to overstate hash tables’ usefulness. When I want to solve a problem, the two plans of attack I start with are “Can I use a hash table?” and “Can I model this as a graph?”

- Graph algorithms—Covered in chapters 6 and 7. Graphs are a way to model a network: a social network, or a network of roads, or neurons, or any other set of connections. Breadth-first search (chapter 6) and Dijkstra’s algorithm (chapter 7) are ways to find the shortest distance between two points in a network: you can use this approach to calculate the degrees of separation between two people or the shortest

route to a destination.

- K-nearest neighbors (KNN)—Covered in chapter 10. his is a simple machine-learning algorithm. You can use KNN to build a recommendations system, an OCR engine, a system to predict stock values—anything that involves predicting a value (“We think Adit will rate this movie 4 stars”) or classifying an object (“hat letter is a Q”).

- Next steps—Chapter 11 goes over 10 algorithms that would make good further reading.

**What’s Inside the ebook:**

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

### How to use this ebook

The order and contents of this book have been carefully designed. If you’re interested in a topic, feel free to jump ahead. Otherwise, read the chapters in order—they build on each other.

I strongly recommend executing the code for the examples yourself. I can’t stress this part enough. Just type out my code samples verbatim (or download them from https://github.com/egonschiele/grokking_algorithms), and execute them. You’ll retain a lot more if you do.

I also recommend doing the exercises in this ebook. The exercises are short—usually just a minute or two, sometimes 5 to 10 minutes. hey will help you check your thinking, so you’ll know when you’re on track before you’ve gone too far.

### Who should read this ebook

This book is aimed at anyone who knows the basics of coding and wants to understand algorithms. Maybe you already have a coding problem and are trying to find an algorithmic solution. Or maybe you want to understand what algorithms are useful for. Here’s a short,

an incomplete list of people who will probably find this ebook useful:

- Hobbyist coders

- Coding boot camp students

- Computer science grads looking for a refresher

- Physics/Math/other grads who are interested in programming

**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**

preface

acknowledgments

about this book

**1 Introduction to algorithms**

*Introduction*

What you’ll learn about the performance

What you’ll learn about solving problems

*Binary search*

A better way to search

Running time

*Big O notation*

Algorithm running times grow at different rates

Visualizing different Big O run times

Big O establishes a worst-case run time

Some common Big O run times

The traveling salesperson

*Recap*

**2 Selection sort**

*How memory works*

*Arrays and linked lists*

Linked lists

Arrays

Terminology

Inserting into the middle of a list

Deletions

*Selection sort*

*Recap*

**3 Recursion**

*Recursion*

*Base case and the recursive case*

*The stack*

The call stack

The call stack with recursion

**Recap**

**4 Quicksort**

*Divide & conquer*

*Quicksort*

*Big O notation revisited*

Merge sort vs. quicksort

Average case vs. worst case

*Recap*

**5 Hash tables**

*Hash functions*

*Use cases*

Using hash tables for lookups

Preventing duplicate entries

Using hash tables as a cache

Recap

*Collisions*

*Performance*

Load factor

A good hash function

*Recap*

**6 Breadth-first search**

*Introduction to graphs*

*What is a graph?*

*Breadth-first search*

Finding the shortest path

Queues

*Implementing the graph*

*Implementing the algorithm*

Running time

*Recap*

**7 Dijkstra’s algorithm**

*Working with Dijkstra’s algorithm*

*Terminology*

*Trading for a piano*

*Negative-weight edges*

*Implementation*

*Recap*

**8 Greedy algorithms**

*The classroom scheduling problem*

*The knapsack problem*

*The set-covering problem*

Approximation algorithms

*NP-complete problems*

*Traveling salesperson, step by step*

How do you tell if a problem is NP-complete?

*Recap*

**9 Dynamic programming**

*The knapsack problem*

The simple solution

Dynamic programming

*Knapsack problem FAQ*

What happens if you add an item?

What happens if you change the order of the rows?

Can you fill in the grid column-wise instead

of row-wise?

What happens if you add a smaller item?

Can you steal fractions of an item?

Optimizing your travel itinerary

Handling items that depend on each other

Is it possible that the solution will require

more than two sub-knapsacks?

Is it possible that the best solution doesn’t fill

the knapsack completely?

*Longest common substring*

Making the grid

Filling in the grid

The solution

Longest common subsequence

Longest common subsequence—solution

*Recap*

**10 K-nearest neighbors**

*Classifying oranges vs. grapefruit*

*Building a recommendations system*

Feature extraction

Regression

Picking good features

*Introduction to machine learning*

OCR

Building a spam filter

Predicting the stock market

*Recap*

**11 Where to go next**

*Trees*

*Inverted indexes*

*The Fourier transform*

*Parallel algorithms*

*MapReduce*

Why are distributed algorithms useful?

The map function

The reduce function

*Bloom filters and HyperLogLog*

Bloom filters

HyperLogLog

*The SHA algorithms*

Comparing files

Checking passwords

*Locality-sensitive hashing*

*Diffie-Hellman key exchange*

*Linear programming*

*Epilogue*

**answers to exercises
index**

## Preface

I first got into programming as a hobby. Visual Basic 6 for Dummies taught me the basics, and I kept reading books to learn more. But the subject of algorithms was impenetrable for me. I remember savoring the table of contents of my first algorithms book, thinking “I’m finally

going to understand these topics!” But it was dense stuff, and I gave up after a few weeks. It wasn’t until I had my first good algorithms professor that I realized how simple and elegant these ideas were.

A few years ago, I wrote my first illustrated blog post. I’m a visual learner, and I really liked the illustrated style. Since then, I’ve written a few illustrated posts on functional programming, Git, machine learning, and concurrency. By the way: I was a mediocre writer when I started out. Explaining technical concepts is hard. Coming up with good examples takes time, and explaining a difficult concept takes time.

So it’s easiest to gloss over the hard stuff. I thought I was doing a pretty good job until after one of my posts got popular, a coworker came up to me and said, “I read your post and I still don’t understand this.” I still had a lot to learn about writing.

Somewhere in the middle of writing these blog posts, Manning reached out to me and asked if I wanted to write an illustrated ebook. Well, it turns out that Manning editors know a lot about explaining technical concepts, and they taught me how to teach. I wrote this ebook to scratch a particular itch: I wanted to write a book that explained hard technical topics well, and I wanted an easy-to-read algorithms ebook. My writing has come a long way since that first blog post, and I hope you find this ebook an easy and informative read.

## Reviews of the customers about the ebook:

- Travis:

I’m gonna keep this short (EDIT: that..definitely didn’t end up happening) because I haven’t gone through the whole ebook yet, so **disclaimer** on that part. But after just the first couple of chapters, I was very impressed.I’m a ‘seasoned’ programmer, I would like to think (industry experience at a “top” company, CS degree, coding all my life, etc), and so almost all of this ebook is “review” for me. I’m going back through fundamentals in preparation for coding interviews, as I’m back on the market for a job. I’d say this book does these things very well:1) Fills in the gaps that might’ve always been there – What I mean by this is, if you maybe got a bachelor’s in computer science, there could easily have been some material that just didn’t completely sink in or that your curriculum didn’t focus on. I think going through this ebook is a great way to make sure those gaps are filled.

2) Explains concepts in an easy to grasp form – The examples that are used in the book are great. There’s one example early on with big O involving drawing 16 boxes on a piece of paper. One way is to draw 16 boxes one at a time – yielding O(n). Another way is to fold that piece of paper in half each time. This gets your 16 boxes in only 4 folds – big O(log n). It’s simple, yet a great way of showing the difference between the two.

3) Keeps your attention – I love to buy books and then not read them… it’s a talent that I exercise often… One thing I can say about this book is that it actually keeps my attention, and I enjoy reading it. That’s saying a lot of it can do that. How much good is a book if it’s too boring to focus on and get through? If you don’t read it, it doesn’t matter how quality the content is.

I’ve recommended this book to several people in my life already, and I wish I still had my Amazon affiliate account setup because I feel like a freaking spokesperson for the thing..! Haha.

In summary: I would recommend this book to a very wide range of people—ANYONE in computer science looking to get a job, anyone trying to get a degree or just take anything CS-related, anyone interested in some of the CS fundamentals, anyone looking to review computer science concepts, anyone wanting to dip their feet into a new field of study they haven’t explored before.

I wish I had this ebook when I was an undergrad—It would’ve saved me so much headache and difficulty.

I’ll update this review once I’ve finished more of the book, but from what I’ve gone through so far, and compared to plenty of other programming books (algorithms, interview prep books, etc), it’s by far my favorite.

- Dev:

After going through a few different data structure and algorithm books and even part of Cracking the Coding Interview, and reading Grokking Algorithm’s, I realize how much easier it is to get even the more difficult concepts by the way the author draws out examples. And when I saw draw-out examples, there are illustrated examples that make it so simple even a kid can get these concepts that even experienced developers struggle with. Also, where other authors fail, Adit includes key insights about why and when to use certain algorithms and data structures that just make sense. Even if you don’t understand Python (the most simplified/elegant language I’ve seen so far), this book is a must-read if you’re interested in interviewing or even if you’re just trying to gain a better understanding of data structures and algorithms. - Shane:

I’m a front-end dev without any formal computer science education. In the past, when I heard terms related to algorithms and big O notation, they seemed scary and made me feel totally unqualified to be part of that world. But the reality is, a lot of these concepts seem more difficult than they really are. When they’re presented in simple terms with examples and illustrations, you start to realize that it’s not beyond you at all – you just haven’t learned it yet. This book does an incredible job of making these concepts accessible. I recommend it to anyone without a formal CS background, whether you’re new to programming, or like me, have been doing it for a long time but haven’t had much exposure to algorithms. I recently used this book as a resource when preparing for coding interviews, and it was invaluable. I give it a ton of credit for helping me land my current job in a role I didn’t think was possible for me just a few years ago. - Bamieh:

An amazing ebook for non-programmers interested in learning about the world of computer science. The ebook might also be very useful for undergrads entering the field.The author starts by providing a general introduction to the concepts of algorithms and analyzing their time using Big O notation. The book gradually advances the reader into various concepts in algorithms to paint a clear picture throughout the book:

– A few necessary data structures.

– A few algorithm implementations for sorting, searching, and finding the shortest path.

– Graph algorithms for modeling networks.

– K-NN is a gentle intro to classification problems and machine learning.The ebook introduces the main methods for problem-solving techniques including:

– Divide and conquer: breaking a problem into smaller pieces

– Approximation algorithms and NP-complete problems: greedy algorithms are used when calculating the exact solution will take too much time

– Dynamic programming: optimizing a solution given a constrain by breaking it up into subproblems and solving these subproblems first (knapsack problem)Finally, the author wraps up by introducing the reader to concepts from various branches of computer science. The author provides hints on learning about each of these topics moving forwards:

– Binary Trees for B-trees, red-black trees, heaps, and splay trees.

– Inverted Indexes: building search engines

– Fourier transform decomposing signals into the frequencies that make it up.

– Parallel algorithms: MapReduce.

– HyperLogLog and Bloom filters: probabilistic data structures and algorithms.

– SHA functions: encryption and data integrity.

– locality-sensitive hashing: Simhash functions where small changes only change the output slightly.

– Diffie-Hellman key exchange: public-private keys for secure data sharing.

– Linear programming: maximizing a solution given a constraint, Simplex algorithm. - Ron:

I’m not big on rating things, but I had to for this amazing book. This is by far the best introduction to algorithms out there, especially if you have not encountered them before. If you’re a dev new to coding from some other field and lack a CS background, start here. If you are a VISUAL LEARNER, start here. If you like the light, easy text to get acquainted with an idea, start here. If you want to learn the basics and learn them well, start here. After you read this book you’ll be ready for the more dense ones. - Seamus:

This is a great supplement to any computer science student taking a course in algorithms. Definitely NOT a substitute for more academic books and instruction on the subject, but definitely a great way to de-mystify what is for many people the hardest part about getting a degree in CS. The section on Dynamic Programming in particular is very helpful as it focuses on the principles and uses drawings to illustrate, and approaches the subject very gradually. It doesn’t help (or even mention) things like coming up with or solving for recurrences, and doesn’t have much in the way of real code examples, but that’s actually a good thing as it helps keep the focus on the ideas rather than the implementation.I also can’t say enough good things about the layout! They were generous with the whitespace, which helps with clarity and focusing on one idea at a time. - C.Pustejovsky:

Aditya Bhargava does an amazing job explaining core concepts related to algorithms using pictures, diagrams, examples, and exercises sprinkled throughout his ebook.He uses Python for his code examples which is a very accessible programming language in terms of both popularity and readability. This is a great choice for beginners who will likely be checking this book out first before diving deeper.Finally, he points out the topics he considers to be outside the scope of the ebook. This gives the reader plenty of starting points for continuing their journey into algorithms and data structures.

- Joseph:

I just finished reading this book and I wish I had it during my time in college. This book has supplemented my understanding of algorithms and has taught me different ways from which to view an algorithm. I would definitely recommend this book to any student about to take a course in algorithms because it will supplement your learning and introduce different perspectives and perhaps cover any algorithm you didn’t cover in class. The book features popular algorithms like binary search, breath, and depth-first search, and Dijkstra’s algorithms. It is well written and has plenty of examples, exercises for you to make sure you are understanding the material. One of my favorite purchases! - Jony:

The book is perfect for people that have a non-CS background and are working in IT related field or transitioning to it. It doesn’t go into details and internals of algorithms or data structures, just explains what they are, why they are used in plain English with simple real-life examples and illustrations. No classic phone book example for binary search, thanks for that to the author. That is why this book is called ‘Grokking…’. Anyone who is beyond the ‘Grokking…’ level can proceed to Cormen’s ‘Algorithms Unlocked’ and classic CLRS book. - Ashlee:

I am thoroughly enjoying this book. I’m not sure how comprehensive it is, but it’s definitely a great supplement for anyone attempting to learn more about algorithms, data structures, and computer science generally. It’s a pleasure to read, with very informative drawings and clear explanations. It really helped drive home some concepts that I was either hard for me to comprehend or remember from [drier, less engaging] sources. I’ve also found the practice questions and answers to be very helpful for technical interview preparation. I would wholeheartedly recommend this for anyone who needs to learn about algorithms and data structures for work or those who just have a passing interest in the topic.

## Buy more ebooks:

The Algorithm Design Manual (Texts in Computer Science)

Cracking the Coding Interview, 6th Edition: 189 Programming Questions and Solutions

## Reviews

There are no reviews yet.