GROKKING ALGORITHM BLUEPRINT: A Comprehensive Beginner's Guide to Learn the Realms of Grokking Algorithms from A-Z and Become Efficient Programmers

By William Turner

What is grokking algorithms? A new kind of algorithm? A new way of doing data science? No. The official definition of grokking is "To understand profoundly through intuition or empathy." It also means "to empathize or communicate sympathetically (with); also, to experience enjoyment." In short, it's all about learning algorithms in a way that th

• Language: English
• Publisher: William Turner
• Release date: Oct 12, 2023
• ISBN: 9798868919497

William Turner

William B. Turner holds a Ph.D. in U.S. history and a J.D. He has published his dissertation as a monograph and a second, edited collection for which he had two co-editors. He wrote the first chapter. He has a total of eight law review articles in print. After living in five other states, he now lives in his hometown, Oklahoma City.

Book preview

Introduction

What is grokking algorithms? A new kind of algorithm? A new way of doing data science? No. The official definition of grokking is To understand profoundly through intuition or empathy. It also means to empathize or communicate sympathetically (with); also, to experience enjoyment. In short, it’s all about learning algorithms in a way that they are part of you, not just memorizing what to do. To grok means to learn in such a way that your view of programming is changed forever.

I will walk you through some of the most popular algorithms in an easy-to-understand way that ensures you truly understand them and become fully immersed in them. So much so that when you’ve finished the book, you’ll be excited to go out and learn more.

I cannot possibly cover every algorithm; that would take several books. Instead, I’ve picked the ones you are likely to come across the most frequently. I’ve covered them in some detail but not too much, and with some code examples. Some of the algorithms you will learn about include:

Sorting algorithms, such as Quick Sort and Selection Sort

Greedy algorithms

Divide and Conquer methods

Dijkstra’s shortest path

You will also learn about:

Dynamic programming

Recursion techniques, hash tables, breadth-first searches

KNN

Space and time complexity

Big O notation

And much more

If you are ready to immerse yourself in the world of algorithms, let's get started.

Chapter 1

An Introduction to Algorithms

This chapter will give you:

The foundation for understanding this guide

A guide to writing a Binary Search algorithm

An overview of Big O notation, i.e., an algorithm’s running time

A brief guide on space and time complexity

An introduction to recursion, a common algorithm design technique that we’ll cover in more detail in chapter 3.

So, what is an algorithm?

In its simplest form, an algorithm is a series of steps that accomplish a specific task. While there are hundreds of different algorithms, the ones included in this book are fast and/or are used on problems that most will find interesting.

Here’s a bit about what you’ll find in this book:

The first chapter introduces algorithms and binary search, showing how to speed your code up significantly.

You’ll learn how to find and calculate the shortest path using certain algorithms, just like a GPS device gets to your destination using graph algorithms

You’ll learn how dynamic programming works, using an example of an algorithm built to play checkers

Every algorithm comes with an example and a discussion on the Big O notation and running time. I’ll also look at other problems for which we could use the same algorithm.

Performance

The good thing about algorithms is that they are not program-specific, which means they will work in all programming languages. Every algorithm discussed in this book has an implementation for all the main languages, so there’s no need to break a sweat writing the algorithms yourself.

However, you do need to understand trade-offs because, without them, the implementations don’t mean anything. I will teach you how to compare the trade-offs between the algorithms to help you understand which one/s to use for each problem.

Problem Solving

I will also teach you techniques to solve problems you might otherwise have given up on. For example:

Video game players can write a system that uses graph algorithms to follow a player around

You can use KNN to develop a recommendation system

Not every problem can be solved quickly. Part of this guide looks at NP-Complete problems that indicate how you can identify those problems and choose the right algorithm that gives you as near an answer as possible.

By working your way through the guide, you will better understand some of the more common algorithms that can be used on many problems. You can then take this knowledge and put it to use, learning different algorithms.

Let's dive into our first algorithm. Before we do, though, there are some things you should understand before starting.

First, you should have an understanding of basic algebra. If I gave you the following function and asked you what f(5) was, what would your answer be:

f( x) = x x 2

If you know your algebra, you'll know the answer is 10. If you didn't know that, go away and brush up on your algebra skills.

You should also have knowledge of a programming language. I'm using Python as it is one of the easiest to learn and is fantastic for beginners. If you are proficient in using a different language, that's fine – as I said earlier, algorithms work in all languages.

Binary Search

Let's get into the exciting part.

Let's say you need to find an address or phone number. Many years ago, you would have picked up a phone book and looked through it to find them. If their name began with M, you would have two ways to find them – start at the beginning and go through until you find the M's, or head straight to the middle of the phone book – M is somewhere near the middle – and find it much quicker. The same applies to finding a word in a thesaurus or dictionary.

Now let's flip forward to modern times. You sign into Twitter. When you do this, Twitter needs to verify that you are signed up for an account. It does this by searching its database for your username. Now let's say your username is maggiemay. In that case, Twitter could start at A and search through or go straight to the M section in its database.

All of these are the same kind of problem – search. And all of them can be solved using the Binary Search algorithm.

This algorithm takes a list of sorted elements as an input – you'll understand why it must be sorted later. If you are looking for a specific element and it is present in the list, the algorithm will return its position. If it isn't there, you get a result of null.

Let's try this example. I have a number in my head, between one and 50. You need to guess that number in as few tries as you can, and every time you make a guess, I will tell give you one of three responses:

Too high

Too low

Correct

The logical, perhaps easiest way would be to start guessing at 1 and go through the numbers one by one.

However, this isn't a great approach and is often called the simple approach. Although you eliminate a number with each wring guess, it is only one number. If I had chosen 49 as my number, you would need 49 guesses to get it right – that's a lot.

So, what would be a better way? To start at 25, of course. That's halfway through, but it's not my number, and I'll tell you it's too low. That's 50% of the numbers eliminated immediately. Now you can concentrate on 26 to 50. So your next guess would be 38 – hallway through what's left. I'll tell you it's too high. Again, that's half the remaining numbers eliminated, leaving you with 26 to 37. So you go halfway between them, 31. You can see where I'm going. With binary search, you simply guess at the number in the middle, thus eliminating 50% of the numbers every time.

That, my friends, is your first algorithm, and wasn't it easy to learn?

No matter what number is in my head, you can guess it in the minimum number of steps by removing 50% of the possible answers with each guess.

Let's try that on a dictionary with 250,000 words. How many guesses would the worst-case scenario take to find one word?

Using the simple search, it could be 250,000 guesses if the word is the last one in the dictionary. However, using the binary search approach, you can start in the middle and reduce the number of words searched by 50% every time until you get to the right word.

Where a simple search takes a potential 250,000 steps, a simple search would do it in less than 20 – what a difference!

Generally speaking, a list of n elements will always take log n steps for the worst-case running time, while a simple search is n steps.

Logarithms

Do you know what a logarithm is? What about exponentials? If not, let me simplify it. If I said to you, log 100, it would be nothing more than me asking you how many tens should be multiplied to get 100?

The answer is also simple:

2

10 x 10

It's that simple. Logs are 10 flips of exponentials.

Throughout this guide, I will mention an algorithm's running time in terms of the Big O notation – more about that in a bit. When I do this, log will always mean log. When you use a simple search to find a number, you might need to examine every element in the worst-case scenario. So, if you have a list of 8 numbers, it'll be a maximum of 8 checks.

The worst-case for a binary search would be log n elements. So, your list of 8 elements would be 8 = 3. This is because 23 == 8, so only three numbers would need to be checked at most.