Grokking Algorithms

A Comprehensive Beginner’s Guide to Learn the Realms of Grokking Algorithms from A-Z and Become Efficient Programmers

© Copyright 2022 – All rights reserved.

The content contained within this book may not be reproduced, duplicated, or transmitted without direct written permission from the author or the publisher.

Under no circumstances will any blame or legal responsibility be held against the publisher, or author, for any damages, reparation, or monetary loss due to the information contained within this book, either directly or indirectly.

Legal Notice:

This book is copyright protected. It is only for personal use. You cannot amend, distribute, sell, use, quote or paraphrase any part, or the content within this book, without the consent of the author or publisher.

Disclaimer Notice:

Please note the information contained within this document is for educational and entertainment purposes only. All effort has been executed to present accurate, up to date, reliable, complete information. No warranties of any kind are declared or implied. Readers acknowledge that the author is not engaging in the rendering of legal, financial, medical, or professional advice. The content within this book has been derived from various sources. Please consult a licensed professional before attempting any techniques outlined in this book.

By reading this document, the reader agrees that under no circumstances is the author responsible for any losses, direct or indirect, that are incurred as a result of the use of information contained within this document, including, but not limited to, errors, omissions, or inaccuracies.

Table of Contents

Introduction

Chapter 1: An Introduction to Algorithms

Binary Search

Logarithms

Big O Notation

Common Run Times

The Traveling Salesperson

Key Takeaways

Chapter 2: Sorting Things Out with Selection Sort

How Does Memory Work?

Arrays and Linked Lists

Selection Sort

Key Takeaways

Chapter 3: Breaking Down Recursion

Recursion

The Stack

Key Takeaways

Chapter 4: Let’s Get to Quick Sort

Divide and Conquer

Quicksort

Back to Big O

Key Takeaways

Chapter 5: Hash Tables for Storage

Hash Functions

Performance

Key Takeaways

Chapter 6: Breadth-First Searches

Introduction to Graphs

Queues

Key Takeaways

Chapter 7: Dijkstra – Taking the Shortest Path

Negative-Weight Edges

Key Takeaways

Chapter 8: Feeding Greedy Algorithms

College Scheduling

The Knapsack Problem

Set-Covering Problem

Approximation Algorithms

Sets

NP-Complete Problems

Key Takeaways

Chapter 9: Dynamic Programming

Dynamic Programming

Frequently Asked Questions

Longest Common Substring

Longest Common Subsequence

Key Takeaways

Chapter 10: Who’s your KNN?

Classification: Lemons vs. Limes

How to Build a Recommendation System

Regression

Introduction to Machine Learning

Key Takeaways

Chapter 11: The Best Way to Learn Algorithms

Conclusion

References

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. If your list contained 1,024 elements, it would be log 1024 = 10 because 210 == 1024 – this means no more than 10 numbers would need to be checked.

Let's do some practical work now and use Python to write binary search. I'm using arrays in this example – if you are unsure of these, I'll discuss them in chapter 2. All you need to know for the minute is that a sequence of elements can be stored in an array, which is a row of buckets.

Because Python indexing starts at 0, the first bucket is at position 0. The next is at position 1, then 2, and so on.

The function called binary_search takes two things – an item and a sorted array. Should the item exist in the array, its position is returned by the function. You'll be tracking the array part that needs to be searched through.

To start with, here’s the whole array:

low = 0

high = len(list) - 1

As always, the middle element is checked first with a binary search.

Every time, the middle element is checked::

mid = (low + high) / 2

guess = list[mid]

If you guess low, do the appropriate update to low:

if guess < item:

low = mid + 1

Conversely, if your guess is high, you do the appropriate update to high.

Here is the entire code:

def binary_search(list, item):

  low = 0

  high = len(list)—1

  while low <= high:

mid = (low + high)

guess = list[mid]

if guess == item:

   return mid

  if guess > item:

  high = mid - 1

  else:

low = mid + 1

return None

The result should be:

my_list = [1, 3, 5, 7, 9]

print binary_search(my_list, 3) # => 1

print binary_search(my_list, -1) # => None

In Python, a “None” return means Null, which tells you that the specific item could not be found.

Running Time

As mentioned earlier, I will talk about an algorithm's running time. You always want the right algorithm for the given problem, whether you need space or time optimization.

Let's get back to our binary search and discuss how much time you can save using it. Well, with our simple search, you would check every number individually so that a list containing 100 numbers could potentially take 100 guesses. What if the list contained a billion numbers, though? That would take a maximum number of a billion guesses.

Noticed anything?

The size of the list and the maximum guesses are the same numbers – this is known as linear time.

It's different with binary search; for a list of 100 items, it would take no more than 7 guesses. With a list of a billion, it would take no more than 30 guesses.

Big O Notation

Anyone who knows anything about algorithms has heard of the Big O notation, but what is it? Nothing more complicated than a notation indicating the speed of an algorithm.

But why is this important?

You won't always be using your own algorithms. Much of the time, you'll likely be using other people's algorithms, and you want to know whether they are fast or slow. So, this part of our introduction will look at the Big O notation and some common running times.

Let's start with an example.

Billy has been tasked with writing a search algorithm for an airplane simulator company. His algorithm must start when a plane is just about to crash land and helps with the calculation of landing the plane safely.

This demonstrates the difference in run time between two algorithms and how they can grow at different rates. Billy needs to decide between using a simple or binary search – his algorithm has to be fast and accurate because the simulator user will only have 10 seconds to determine where to land the plane, or it will crash.

As we know, binary search is much faster, but the simple search algorithm is far easier to write, and there is a much lower chance of introducing bugs into the code. Billy does NOT want any bugs – it could be catastrophic. So, being clever, Billy decides to test both algorithms, each with an identical list containing 1oo elements.

We'll assume that one element can be checked every millisecond. Because he has to check 10 elements in the simple search, the running time will be 100 ms. With the binary search, only 7 elements need to be checked, which takes just 7 ms. In real terms, a list like this will probably have a billion or more items in it – how long would each algorithm take?

Try to work it out and have your answers ready before we move on:

Simple search would take ____ms

Binary search would take ____ms

Assuming a billion elements in the list, Billy's binary search algorithm takes 30 ms because log 1,000,000,000 is approximately 30 – that is 15 times faster than a simple search. With 100 elements, the simple search took 100 ms, and the binary search just 7 ms. So, in theory, the simple search algorithm will take 450 ms (30 x 15). That's way under the 10-second time limit needed, so Billy decides the simple search is the way to go.

But has he made the right decision?

No, he hasn't.

In fact, he couldn't have been more wrong!

A simple search on a billion items takes a billion ms – an impressive 11 days! The problem lies in the running time growth rates for each algorithm – they are not the same.

As the number of elements in a list increases, the binary search running time grows a little. By contrast, the simple search will take significantly longer to run. Billy made the mistake of thinking that the binary search was just 15 times faster, but that is wrong – in a list with a billion elements, it's nearer 33 million times faster.

This demonstrates why knowing the run time of an algorithm is not enough – you also need to know the growth rate, and that is where Big O comes into its own.

Big O is quite simple – it tells an algorithm's speed.

Here's an example. You have a list that is size n. Because a simple search needs to check all the elements, it takes n operations. In Big O notation, the run time is O(n). But hold on! What happened to the seconds? Well, there aren't any because Big O doesn't provide the speed in seconds. It does let you see how many operations are needed and lets you know the growth rate. The run time is O(log n) for the same operation using a binary search.

See if you can work out the running time for the algorithms below. We'll start with one you can do with nothing more than a pencil and some paper.

You need to draw a grid containing 20 boxes – how will you do it?

Simple Search

With this algorithm, you would draw each box individually. One box equals one operation, so drawing 20 boxes is 20 operations. What is the running time?

It's O(n) time

Binary Search

We could do it the other way -  fold a piece of paper. Each fold is an operation. Fold it four more times and then unfold it – you have your grid. And you did it in just 5 operations. So, what's the running time?

O(log n)

Worst-Case Run Time

Let's say you want to find someone in the phone book using a simple search. The run time is O(n), so the worst-case means looking at every individual entry in the book. Now let's say the name you want is the first in the book, and a simple search finds it quickly. Does that mean the run time is O(1) and not O(n)?

The simple search algorithm still takes O(n) time regardless of where the name is in the book. Finding the right name first is the best case, but Big O is all about worst-case. So, in the worst case, you could say that you would need to examine every single name in the book. The fact that the worst-case is O(n) time tells you, quite reassuringly, that the search will not be any slower than that.

Common Run Times

The five commonest run times you will encounter the most are, from the fastest to the slowest:

O(log n): also called log time, commonly used by binary search

O( n): also called linear time, commonly used by simple search

O( n * log n): used by QuickSort and other fast sorting algorithms

O(n 2): used by SelectionSort and other slow sorting algorithms

O( n!): used by the slowest sorting algorithms, such as the traveling salesperson problem, which we'll look at shortly.

Let's go back to our grid, this time 16 boxes. You have five algorithms to choose from in drawing that grid. What would the run time be for each one?

Use the first algorithm above, and you get a run time of O(log n). 10 operations could be done per second (remember, each one takes a millisecond), so it takes 4 operations (log 16=4) and 0.4 seconds.

The second algorithm isn't so fast. The run time is O( n), which takes 16 operations and 1.6 seconds.

See if you can work out the details for the remaining three algorithms.

This is just a simple look. You can't actually convert Big O into an accurate amount of operations quite as easily as that, but it gives you a good idea. We'll look back at Big ) throughout the rest of the book, but, for now, this is what you need to understand:

We do not measure the speed of an algorithm in seconds. Instead, we measure it in terms of the growth rate of the operations

That means learning how an algorithm's size increases exponentially with an increase in the inputs.

Big O notation is used to express the run time

O(log n) is quicker than O( n), but it speeds up significantly with an increase in the list of elements

The Traveling Salesperson

Are you panicking yet? Do you think there's no way you will get an algorithm that takes O( n!) time, the excruciatingly slow run time? Wrong! The traveling salesperson problem is famous, used just about everywhere to demonstrate that algorithms can have poor running times. It has one of the worst growth rates, and many believe there is no way to improve it.

Here we go.

Your salesperson, we'll call him Denny, needs to visit five different cities. He wants to get to all of them in the shortest possible distance. The first way to do this is to look at all potential orders of traveling to the cities.

Denny adds the total distances of each order and chooses the one that has the smallest distance. With five cities to visit, there are 120 possible routes, so solving the problem takes 120 operations. To put that in perspective, if he needed to visit seven cities, there would be 5040 potential routes – a significant increase for just two more cities.

Generally, with a list of n items, getting a result takes n factorial (n!) operations. This equates to O( n!), which is known as factorial time. Apart from tiny numbers, computing everything will always take a lot of operations. If that list of cities grew to a hundred or more, you simply couldn't calculate the result before the end of time.

This has to be one of the worst algorithms ever. Surely Denny could use another much faster one, couldn't he? No, he couldn't; this is one of the biggest computer science problems that remain unsolved.

There isn't a quick algorithm that would work for it, and many believe there is no way a smart algorithm would work. In fact, all we can do is get an approximate solution, but we'll discuss that in a later chapter.

Key Takeaways

Here's what you learned in this chapter

Binary search is much quicker than simple search

O(log n) is quicker than O( n), but as the list grows, so too does its speed

We don't use seconds to measure algorithm speed

We use an algorithm's growth to measure its time

The Big O notation is used to write algorithm times

Chapter 2: Sorting Things Out with Selection Sort

Here’s what you will learn in this chapter:

How two basic data structures work – linked lists and arrays. These structures are used all over the place, and we looked at arrays briefly in the first chapter – get used to them because they will be used throughout the rest of the book. Arrays are important, so make sure you understand them before moving on. However, linked lists also have their place, so you must understand when to use each.

Your very first sorting algorithm. Remember that some algorithms require the input data to be sorted – like the binary search algorithm. You will learn the selection sort algorithm, but it’s worth noting that most languages already have a built-in sorting algorithm, negating the need to write one yourself. However, selection sort leads to Quicksort, which we’ll look at later. Quicksort is one of the more important sorting algorithms; you’ll find it easier to understand if you already know a sorting algorithm.

Before we get started, you’ll need to understand logarithms and Big O notation to grasp the performance analysis in this chapter – refer back to chapter 1 if you need a refresher.

How Does Memory Work?

Understanding many algorithms requires understanding how memory works. Let’s say you attend an important meeting but are not allowed to take anything into the building for security purposes. You see a series of connected containers when you get to the door. Each holds one item, and you have two things to store – you ask for two containers. You place one item in each and are ready to attend your meeting. That is how memory works on a computer. Think of your computer as a whole bunch of connected containers, each with its own address.

Whenever you want something stored in memory, you request space from the computer, and in return, it gives you a memory address. If you have several things to store, you can do it in two ways: linked lists and arrays. We’ll discuss both now.

Arrays and Linked Lists

Ok, so you sometimes need stuff stored in memory. Let’s say you are tasked with writing an app to manage your shopping list, and you want everything on the list stored in memory as a list.

Do you choose a linked list or an array?

Arrays

Let’s start with an array because they are easier to understand. When you use an array, all your shopping items are contiguously stored in memory – this means they are stored next to one another.

You have five items on your list, but you now need to add a sixth. The problem is that the next container in memory has someone else’s stuff in it.

Think of this as attending a lecture with your study group. There are five of you, and you have a group of seats together. But then a sixth friend joins you but has nowhere to sit. You all need to move to where there is enough space for all of you. In terms of your shopping list, you need to request a bigger chunk of memory from your computer, big enough to fit everything in. Once your request is granted, your shopping list needs to be moved to the new location.

If a seventh friend decides to join you, you need to move again to somewhere bigger – and you could keep on doing this for as long as people decide to join your group. This is the problem with arrays – adding stuff to them is a real pain in the posterior. Every time you need to add to your array, you need to move to somewhere else in memory, making it dead slow to add new items.

There is an easy fix: you could “reserve” space. If you have five items on your shopping list, you could request 10 memory slots – that way, you can add another five items to the list without needing to move again. This can work, but it isn’t perfect:

First, you may never use the reserved slots, which leads to wasted memory – you don’t need them, but no one else can use them either.

You might need to add more items than you have space for, so you are on the move again.

The solution to this scenario is a linked list.

Linked lists

When you use a linked list, you can store items anywhere in memory because each item holds an address pointing to the next item – no matter where it is. This way, we link a heap of random memory slots together.

Think of it as treasure hunting. You visit the first location and get a message telling you where the next item is. You go there, and another message tells you the address of the next one – right through to the end. When you add to a linked list, you can put the new item wherever you want in memory so long as the previous item is given the address.

Using linked lists means never having to move to a bigger location. It also means avoiding a problem we get with arrays.

Back to your lecture with your five friends. All six of you need to find somewhere to sit, but the lecture hall is full, and you cannot find six seats together anywhere. That happens with arrays. Let’s say you need 5,000 memory slots for your array. You have 5,000 free slots in memory, but they are not together, so your array will not fit. Using a linked list is like telling your friends to split up and sit separately at the lecture. Your linked list will fit if there is sufficient free space in memory.

So what do we use arrays for if linked lists are better for inserting new items?

Let’s use websites as an example.

If you open a site showing you a top-ten list of something, you can be sure their tactics for getting more page views are underhand.

Rather than putting the entire list on a single page, they place a single item on each page, making you click through them to see them all. This allows websites 10 pages of content, all filled with ads. But clicking through each page is boring – why can’t they have all the list on one page and allow you to click on each item in the list for more information?

The same problem occurs with linked lists.

Let’s say you want the end item of a linked list. You don’t know the memory address of that item, so you can’t just go to it and read it. Instead, you must go through each item individually to get the address for the next one on the list until you reach the one you want.

Linked lists work well if you need to see all the items individually but not so well if you need to jump around between the items.

Arrays work better in this situation because you already know each item’s address.

Let’s say you have 8 items on your shopping list. You know the first item is at address 00, so what would item 8’s address be?

Simple math will answer the question – address 07.

If you need to access random items, arrays work best. You can look up an item in an array instantly. Because the items in a linked list are all over the place, you can’t work out the position of item 8 quickly. Instead, you must go through all the items to get the address.

Terminology

All the elements in an array are numbered, and this starts from 0, not 1, as you might expect:

ITEM | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8
POSITION | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7

As you can see, item 1 is at position 0, item 2 is at position 1, and so on, which can confuse new programmers. However, beginning at zero makes it easier to write array-based code, and virtually every programming language uses it.

An element’s position is known as an index. Instead of saying item 1 is at position 0, you should say item 1 is at index 0. The word ‘index’ will be used hereon to mean position.

Inserting Items into the Middle of a List

Let’s say you want your shopping list in order of importance. Before, you simply added an item to the end of it, but now you want to add items to make your list in order of importance.

Should you use a linked list or an array if you want to add items in the middle of your lists?

With a linked list, you can insert the item and simply change the pointer in the previous address to point to the new item. With an array, all the items need to be moved down to make room for the new one. What if there isn’t enough space? Then you need to move the entire array to a new location in memory.

That tells you that linked lists are the better option when you need to add items into the middle of the list.

Deletions

What if you want to remove an item from your list? Again, the linked lists work better because all you need to change is the pointer in the previous item. With the arrays, once again, everything needs to be moved when an item is deleted.

Where insertions don’t always work, usually due to a lack of space, deletions will work every time – you are making space in the memory rather than needing more.

Below you can see the run times for common array and list operations:

| Arrays | Lists
Reading | O(1) | O(n)
Insertion | O(n) | O(1)
Deletion | O(n) | O(1)

However, it is worth bearing in mind that you will only get O(1) time on deletions when the item to be deleted can be accessed instantly. You should follow best practice and track the first and last items in linked lists, and deleting those takes O(1) time.

Are arrays used more than linked lists or vice versa?

Well, that depends on what they are being used for. Arrays tend to be used more because you have random access to the elements. The other type of access is sequential.

With sequential access, every element must be read individually, starting with index 0, and this is the only type of access a linked list allows. With random access, you can go straight to the element you want. This makes arrays much faster at reading, and because many use cases need random access, arrays are used more than linked lists.

Both are used to implement other data structures, but you’ll learn more about that later.

Selection Sort

Let’s pull all that together to learn the selection sort algorithm. For this, you need an understanding of linked lists, arrays, and Big O notation.

Let’s say you have a whole load of movies stored on your computer, and each one has a count indicating how many times you watched it. You want this list in order of most to least-watched.

How do you achieve this?

Well, you could manually review the list, look for the one you watched the most, and start a new list with it. Then you go through again and repeat until all the movies are in the order you want.

How long would the run time be?

Remember – with O(n) time, every list element is touched once, i.e., a simple search where every movie is looked at once.

If you want to find the movie you watched the most, every movie on your list must be checked once. The run time would be O(n).

So, your operation takes O(n), which needs to be done n times. The run time is O(n x n) or O(n 2).

Sorting algorithms are one of the most useful and can be used for all sorts of operations, including sorting emails, names, and so on. However, while selection sort is great, it isn’t particularly fast. Quicksort is much faster with a run time of O(n log n), but we’ll discuss that in another chapter.

Let’s look at an example of code that will do something similar to sorting your movies in order. This code will sort an array in order of least to most, so first we must write the function that finds the smallest item in our array:

def findSmallest(arr):

smallest = arr[0]

smallest_index = 0

for i in range(1, len(arr)):

if arr[i] < smallest:

smallest = arr[i]

smallest_index = i

return smallest_index

We can now use this to write our selection sort:

def selectionSort(arr):

     newArr = []

     for i in range(len(arr)):

smallest = findSmallest(arr)

newArr.append(arr.pop(smallest))

     return newArr

print selectionSort([5, 3, 6, 2, 10])

Key Takeaways

In this chapter, you learned:

The memory in your computer is like a series of connected containers

Linked lists and arrays are used to store multiple elements

Elements are stored contiguously in an array – beside each other

Elements are stored all over the place in memory in a linked list – each element contains the address of the next element

Arrays allow random access and are faster for reading

Linked lists allow fast deletions and insertions

All elements in an array must be the same type – doubles, ints, etc.

Chapter 3: Breaking Down Recursion

Here's what you will learn:

All about a coding technique called recursion used in multiple algorithms. An understanding of recursion is required for later chapters.

How you can break problems down using a divide and conquer strategy into the base and recursive case. This helps you solve harder problems.

Recursion is one of the better ways to solve certain problems, but it's a topic you'll either love or hate. First, I'm using quite a lot of code to demonstrate this, so run it yourself – you'll get a better idea of how it all works. Second, I'll be discussing recursive functions and how you should step through them using a pen and paper; that way, you will better understand how they work.

You will also see a lot of pseudocode, a coded high-level description of the problem you need to solve.

Recursion

Let's say you bought a junk shop and find a strange suitcase, hidden away and locked. The previous owner tells you the key is likely in a box, but inside that box are loads more boxes. And those boxes contain even more boxes. You know the key is there somewhere, but what algorithm do you use to find it?

Try to think of one before you go any further.

Here's one way you could do it:

Place a load of boxes in a pile

Pick a box and look in it

If you find another box, add it to the pile of boxes

If you find a key, you win.

Repeat the procedure

Another approach could be:

Look in a box

If you find another box, go back to step 1

If you find the key, you win

Which of these approaches seems best?

In the first approach, a while loop is used. While there are boxes in the pile, pick a box and look in it:

def look_for_key(main_box):

   pile = main_box.make_a_pile_to_look_through()

   while pile is not empty:

box = pile.grab_a_box()

for item in box:

  if item.is_a_box():

pile.append(item)

  elif item.is_a_key():

print “found the key!”

Approach 2 uses recursion, a technique where functions call themselves. Here's the pseudocode:

def look_for_key(box):

  for item in box:

    if item.is_a_box():

look_for_key(item)

    elif item.is_a_key():

print “found the key!”

We get the same result with each approach, but the second is much clearer, and that is where recursion works – by providing a clearer solution.

Recursion doesn't provide any benefits in performance terms, and loops may even be the better option if performance is what you need. You need to choose which one suits your situation better.

Base Case and Recursive Case

So, recursive functions call themselves, making it very simple to write a function the wrong way, sending it into an infinite loop. Let's say you need a function to print a countdown:

> 5…4…3…2…1

It could be written recursively:

def countdown(i):

print i

countdown(i-1)

Try this code for yourself – you'll see that it runs, runs, and continues running forever.

> 5…4…3…2…1…0…-1…-2…-3…

When writing recursive functions, be sure to tell it when it needs to stop recursing. This is why a recursive function is always split into a base case and a recursive case. The latter is the part where the functions will call themselves, while the former is where it doesn't – that way, it cannot end in an infinite loop.

Let's give our function a base case:

def countdown(i):

   print i

   if i <= 0:

return

   else:

countdown(i-1)

Now it works as it should.

The Stack

The call stack is one of the more important programming concepts, and you need to understand it in terms of recursion.

Let's say you are having a party and have a whole list of things you need to do. Every item on your list is on a sticky note.

Remember those lists and arrays we talked about? Remember your shopping list where you needed to add or delete items? This big pile of sticky notes you have is easier to deal with. When an item is inserted, you just add it to the top of the pile. When you read an item, it's the topmost one, and then it is removed from the list. In this way, your list only has two actions:

Push – insert

Pop – remove and read

Here's how it works:

You pop the topmost sticky note

It tells you to get cake, sausage rolls, and beer

Each of these becomes a new element, and they are pushed onto the stack

This is a data structure called a stack, one of the simplest structures there is and one you've been using forever.

Internally, your computer uses a call stack. Here's a function to demonstrate how it works:

def greet(name):

       print “Hello, “ + name + “!”

       greet2(name)

       print “getting ready to say goodbye...”

       goodbye()

Here, you are greeted, and then two more functions are called. They are:

def greet2(name):

       print “how are you, “+ name + “?”

def goodbye():

       print “ok, goodbye!”

So, what happens when a function is called?

Let's say you call

greet(“simon”)

Your computer will allocate a memory container for the function call.

Now we want to use the memory, so we set the variable name to “simon” and save it in memory.

Whenever a function call is made, the variable values for the call are saved in memory. Next, we print

hello simon

Then call

greet2(“simon”)

Once again, a container of memory is allocated to store the call.

All these containers of memory are stored in a stack; each consecutive container is added to the top. You return from it when you print the call, and the top container is popped off the stack.

Now the next container is the greet function – that's where you returned to. When the greet2 function was called, it wasn't fully completed, and that's what this section is all about. When a function is called from another, the calling function gets paused in a state of partial completion. Every variable value for this function remains stored in memory.

Once the greet2 function is done, you return to the greet function and continue where you finished. You print

getting ready to say goodbye

And then the goodbye function is called. A container is placed on top of the stack for that function, and then you print

Ok, goodbye

And lastly, you return from the call and return to the greet function. Because there isn't anything else to do, you return from this function.

Call Stacks with Recursion

The call stack is also used by recursive functions, and we can see how this works by using the factorial function – factorial(5), commonly written as 5! and defined as:

5! = 5 * 4 * 3 * 2 * 1

In the same way, factorial(3) is:

3! = 3 * 2 * 1

The following recursive function calculates a number’s factorial:

def fact(x):

   if x == 1:

return 1

   else:

return x * fact(x-1)

Now, fact(3) is called. As you go through a function call like this, the stack will change – do not forget that the top container in your stack lets you know the current call to fact. Each call will have a copy of x but note that there is no way to access the copy of x in a different function.

Stacks play an important role in recursion. We mentioned two approaches to finding a key hidden in a box. In the first approach, we made a pile of boxes and always knew which boxes needed to be looked through. However, we didn't have that pile in the second approach, which used recursion.

How do you know which boxes still need to be searched without that pile?

In terms of an algorithm, it would look a little like this:

You look through the first box, A

Inside are two more boxes, B and C

You look through box B and find box D

You look in box D – it is empty

Your call stack now looks a bit like this:

Box D |
Box B |
Box A | Box C

The boxes you checked are in the left column, while the right columns indicate the boxes left to check.

Your pile of boxes is on the stack – the example above is full of partially completed function calls, each having a partially completed pile of boxes to search. The stack tracks all your boxes, so you don't have to.

However convenient it may be, there is a cost to using the stack – memory. Stacks can take up a lot of it because of all the function calls. If your stack grows too tall, your computer is required to reserve memory for all those calls, and you now have two options:

Write your code again, this time using a loop

Use tail recursion. That is outside this book's scope, so I won't be going into it here. Plus, not every language supports it.

Key Takeaways

Here's what you learned:

In recursion, a function will call itself

There are two operations in a stack – push() and pop()

Every function call is added to the stack

Call stacks can grow large and use up a lot of memory

Chapter 4: Let’s Get to Quick Sort

Here's what this chapter will cover:

The divide and conquer technique. Occasionally, you'll face a problem that no algorithm you've learned can solve. However, good programmers never give up; they keep looking for the answer and dip into many other techniques they've learned along the way to help solve the problem. One of those techniques is divide and conquer

The QuickSort algorithm, which uses the divide and conquer technique.

In the previous chapter, we looked at recursion, and what you learned will serve you well in this chapter. Divide and conquer is one of the best-known techniques in recursion to help you solve problems, and here's where we will bury ourselves in the inner workings of algorithms.

Algorithms are only truly useful if you can use them for more than one type of problem. With divide and conquer, you learn a brand new way to consider problem-solving, and when you encounter a problem you cannot solve, consider whether this technique can help you.

When you reach the end, you will understand and know how to use QuickSort, one of the biggest divide and conquer algorithms. This is one of the fastest sorting algorithms and one of the most elegant.

Divide and Conquer

Divide and conquer will take time to understand, so we'll look at it through a few examples.

The first is a visual example.

Let's say you have a large plot of land and want to start a business as a market gardener. The plot is 1680 by 640 square meters and needs to be divided into square plots of equal size. These plots need to be as large as possible, so the following options will not work:

Neither box is square in this division.

These boxes are all too small

These are not the same size

So, how do we determine the biggest square plot size for our land? We use divide and conquer, a recursive algorithm. Using this to solve a problem requires two steps:

Work out the base case – the simplest case possible

Divide your problem or decrease it until it turns into the base case.

Simple right?

To find the biggest square size, let's see divide and conquer in action.

First, work out your base case. It would be easier if the first side were a multiple of the other.

Let's say one side is 25 m and one is 50 m. In that case, your largest box size is 25 m x 25 m. You can divide that land in half and get two plots of that size.

The next job is to work out the recursive case; this is where the divide and conquer algorithm comes in. Divide and conquer dictates that the problem must reduce with each recursive call. How does that work with this problem?

We'll start by marking the largest possible squares on our 1680 x 640 plot of land:

We can make two equal-sized plots, but that still leaves some land. We can apply the divide and conquer algorithm to that plot too. Your plot started at 1680 x 640, and you've managed to split some of it. But there is still a plot of 640 x 400 to divide. Find the largest plot size that works for this segment, and you find the one that works for the entire plot. That is how you reduce a problem and solve it easier.

So, we apply the algorithm again on the 640 x 400 plot and discover that we can create a large square of 400 x 400, which still leaves us with a smaller plot, 240 x 400. We can get a box on that of 240 x 240, leaving another plot of 240 x 160. You can even draw a box on that, 160 x 160, leaving us with a plot of size 80.

And there you have it – the base case. 80 is a factor of 160; if you split the box up, nothing remains. That tells you the largest plot size for your original plot is 80 x 80.

However, you mustn't look at divide and conquer as nothing more than a simple problem-solving algorithm; you should consider it more of a way of thinking about a problem. Here's another example:

You have an array of numbers:

2, 4, 6

The numbers need to be added, and the total sum returned; using a loop, this is easy to do:

def sum(arr):

  total = 0

  for x in arr:

total += x

       return total

print sum([1, 2, 3, 4])

But how can we achieve the same thing using a recursive function?

Here's how:

1.    First, determine the base case, the simplest possible array. Think about what this could be before you move on – if your array has 0 or 1 element, you can sum it up easily

Base case

This is your base case.

2.    Each recursive call needs to take you closer to an empty array, so how do we reduce the size of the problem? Like this

Sum(2, 4, 6) = 12

And this is the same:

2 + sum(4, 6) = 2 + 10 = 12

Whichever way you do it, you get the same result – 12. However, in the second approach, a smaller array is passed into the sum function, thus decreasing the problem size.

This could be your sum function:

Don't forget that when you use recursion, it tracks the state.

If you get stuck when writing a recursive function with an array, try using a 0 or 1 element array as the base case first.

A Quick Look at Functional Programming

You might be asking yourself why you would need to use recursion when a loop will do just fine. This quick look at functional programming will answer that question for you.

Functional coding languages do not contain loops, so you have no choice but to use recursion when writing these functions. If you understand recursion, you won't have trouble learning functional programming.

Haskell is the most popular functional programming language. Using it, you would write a sum function like this:

sum [] = 0

sum (x:xs) = x + (sum xs)

The first line is the base case, and the second is the recursive case. So although it may look like the function has two definitions, it doesn't. The same statement could also be written, again in Haskell, with an if statement:

sum arr = if arr == []

then 0

else (head arr) + (sum (tail arr))

The first approach reads much easier than the second. Haskell relies heavily on recursion so it has lots of useful additions to ensure recursion is easy.

Let’s move on to the point of this chapter – the Quicksort algorithm.

Quicksort

You already know by now that Quicksort is a popular sorting algorithm, quicker than Selection Sort and commonly used in real-life problems. The standard library in C has the qsort function, a C implementation of Quicksort.

This algorithm also uses divide and conquer.

Let's see how it works with an array. First, think of the simplest array that a sorting algorithm could handle. Remember I said earlier that some algorithms could only work with sorted arrays? Well, not all arrays have to be sorted.

Those with nothing or a single element are used as the base case. Those arrays can be returned as they are because there isn't anything to sort:

def Quicksort (array):

     if len(array) < 2:

     return array

Let's consider larger arrays. If your array has two elements, it's still easy enough to sort:

3, 9

This is simple enough; you see if element 1 is smaller than element 2; if not, swap them around.

What about an array containing three elements?

22, 17, 9

Don't forget that we are using divide and conquer, so this array should be broken down to the base case. Here's how we can use Quicksort.

First, we choose one of those elements; that becomes the pivot:

22

Later, we'll discuss choosing the best pivot, but we'll use the first element in the array for now.

Next, we need to find all the elements smaller than the pivot and those larger. We call this partitioning, and now we have three things:

A sub-array containing the numbers less than the pivot number

The pivot number

A sub-array containing the numbers greater than the pivot

Note that the sub-arrays have not been sorted, just partitioned. However, if they had been sorted, it would be easy to sort the array.

9, 17, 22

If they were sorted, the entire thing could be combined like this:

left array + pivot + right array

That would give you a fully sorted array:

[9, 17] + [22] + [] = [9, 17, 22]

How are sub-arrays sorted?

Our Quicksort base case can already sort arrays containing two elements (the left sub-array) and those with nothing (the right sub-array). If Quicksort is called on both sub-arrays and the results combined, we get a sorted array:

Quicksort([17, 9]) +[22] + quicksort([])

> [9, 17, 22]

You can do this with any pivot you choose. Let's say you pick 17 as your pivot. Each sub-array only contains a single element, and sorting those is simple. Now you know how to sort arrays with three elements – the steps are:

1.    Choose a pivot

2.    Partition the array, so you have two sub-arrays; one with greater and one with lesser elements than the pivot

3.    Then Quicksort is recursively called on both sub-arrays

What if we had four elements in the array?

22, 17, 9, 4

Let's choose 22 as our pivot again. On the left is a sub-array with three elements; you already know how to sort those – Quicksort is called recursively.

That makes it easy to sort an array containing four elements; if you can do that, you can sort one with five elements. Why?

Because you have five pivots to choose from, and each gives you a different way of partitioning. No matter how you do it, each sub-array will contain 0 to 4 elements, so, regardless of the pivot, Quicksort can be called recursively on the sub-arrays. Those sub-arrays get sorted, and everything is combined into a sorted array. Using this logic, you can sort an array containing any number of elements

This is the Quicksort code:

def Quicksort (array):

  if len(array) < 2:

return array

  else:

pivot = array[0]

less = [i for i in array[1:] if i <= pivot]

greater = [i for i in array[1:] if i > pivot]

 return quicksort(less) + [pivot] + quicksort(greater)

print quicksort([10, 5, 2, 3])

Back to Big O

Why is Quicksort unique? Because its speed is dependent on your chosen pivot. Before returning to Quicksort, let's look at the common run times again.

Algorithm | Binary Search | Simple Search | QuickSort | Selection Sort | Traveling Salesperson
| O(log n) | O(n) | O(n log n) | O(n 2) | O(n!)
Array Size |  |  |  |  |
10 | 0.3 seconds | 1 second | 3.3 seconds | 10 seconds | 4.2 days
100 | 0.6 seconds | 10 seconds | 996 seconds | 16.3 minutes | 199 years (2.9*10)
1000 | 1 second | 100 seconds | 996 seconds | 27.7 hours | 2559 years (1.27*10)

This is just an example and is based on a slow-running computer performing 10 operations every second. This isn't precise; it just gives you an idea of the difference between the run times. In reality, most of today's computers are way faster than this.

Note that I also included an example algorithm for each run time – you can see that the selection sort algorithm is quite slow. Merge Sort is another sorting algorithm with a run time of O(log n), which is much quicker. Quicksort is somewhat tricky; it takes O(n 2) in its worst case – the same as selections ort. However, for the average case, it takes O(n log n), which begs the question, what do worst and average cases mean in this scenario? You might also ask that if Merge Sort is always O( n log n), while Quicksort is only O( n log n) in the average case, why don't we use Merge Sort all the time?

Let's find out.

Merge Sort vs. Quicksort

Let's say we have a function that prints all elements in a list

def print_items(list):

for item in list:

print item

This function will print every single element in the list. It runs in O(n) time because the entire list is looped over once. Now, if we altered the function to sleep for a second before it printed an item:

from time import sleep

def print_items2(list):

for item in list:

sleep(1)

print item

It pauses for a second before an element is printed. So, let's say we used both these functions to print a list of five elements – which would be the fastest? Both are O(n) time because they both loop through the list once. I think the first one would be – it isn't pausing before printing an element. So, although they both have the same Big O notation run time, the first is faster.

So, when writing Big O notation, what it really means is this:

c * n

In this, c is a constant, indicating a fixed amount of time taken by the algorithm. It could be

10 milliseconds * n

For print items while, for print_items2, it could be

1 second * n

Usually, the constant is ignored because it isn't considered an important factor when two algorithms each have a different Big O time. Look at the simple and binary searches we discussed in the first chapter. If these algorithms both had the constants, you might be excited to see that the constant for simple search is 1o milliseconds, while it's 1 second for the binary search, so surely simple search is quicker, yes?

Well, let's compare that with a search on a list of four billion elements.

The first constants looked like this:

Simple search – 10 ms * n

Binary search – 1 sec * log n

On the list of four billion, they look like this:

Simple search – 10 ms * 4 billion = 463 days

Binary search – 1 sec * 32 = 32 seconds

Binary search still works out much quicker – the constant didn't make any difference.

Sometimes, though, they do make a difference, and Merge Sort vs. Quicksort is just one example. Whenever one algorithm has a smaller constant than another, even though they have the same time of O( n log n), it will always be faster in practice.

So what is the average vs. worst-case?

Quicksort's performance is dependent on your chosen pivot. Let's say you pick the first array element as the pivot every time, and Quicksort is called on a ready-sorted array. It won't look to see if the array is sorted, so it will go ahead and try sorting it.

In this case, the array isn't split in half; one sub-array will be empty. This makes for a very long call stack.

So, what would happen if the middle element was always the pivot?

In this case, the array is split in half each time, so fewer recursive calls are needed. The base case is reached quicker, and we have a shorter call stack.

The first is the worst case, while the second is the best. The stack size in the worst case is O(n) and O(log n) in the best case.

If you were to choose an element as the pivot from the stack's first level, the rest would be split into sub-arrays. All the elements in the array are touched, taking O(n) time. At first glance, you would think you've touched every element on the stack level, but, in actual fact, you touch every element throughout every level. Even if you chose a different partition, you would still touch O(n) elements all the time. This means each level runs in O)n) time.

The call stack's height is O(log n), and because each level completes in O(n) time, the algorithm takes the following time in the best case:

O( n) * O(log n) = O(n log n)

The worst-case has O(n) levels, and the algorithm completes in:

O( n) * O( n) – O( n 2)

Now I'm going to surprise you and tell you that the best and average cases are the same. Quicksort's average time is always O( n log n) when a random element is chosen as the array. It is an incredibly fast algorithm and one of the best examples of divide and conquer.

Key Takeaways

Here's what you learned in this chapter:

Divide and Conquer breaks problems into smaller sub-problems. If you apply it to a list, the base case is most likely an array with 1 or no elements in it

A random element should be chosen as the pivot when you use Quicksort. The algorithm's average run time is O( n log n)

The constant does sometimes matter in the Big O notation and is why Quicksort beats Merge Sort hands down in terms of speed

In terms of a simple vs. binary search, the constant is rarely important. This is because, when lists grow, O(log n) is always much faster than O(n).

Chapter 5: Hash Tables for Storage

In this chapter, we'll cover:

What hash tables are and some of their many uses

What goes on in a hash table, including collisions, implementation, and hash functions, to help you understand how a hash table is performing.

You've just started a new job in a small grocery store and aren't familiar with the prices. So, whenever a customer comes to the checkout, you need to look their items up in a book, but the items aren't stored in alphabetical order. That means, to find the price of something, you need to do a simple search and check every item – that's going to take a while – O(n) time, to be precise. If that book were in alphabetical order, you could do a quick binary search, which would only take O(log n) time.

Even with the book in sorted order, it's still a pain to keep looking up prices, especially when your customer is getting increasingly annoyed with the time it takes. You know what you need? Another person beside you who knows all the prices – you ask, they immediately tell you the right price. Your new buddy, let's call her Bobbie, gives you the price for any item in O(1) time. It doesn't matter how many items are in the book; that girl is fast – even faster than binary search.

Items in Book | Simple Search O(n) | Binary Search O(log n) | Bobbie O(1)
100 | 10 seconds | 1 second | Instant
1000 | 1.6 minutes | 1 second | Instant
10000 | 16.6 minutes | 2 seconds | Instant

We could all do with a “Bobbie” at some time in our lives, but how do we get one?

Data structures, that's how.

We already looked at two of them – lists and arrays – so your grocery prices book could be implemented as an array:

(Milk, 1.69), (Eggs, 2.79), (Apple, 0.80)

Every array item is two items – the product name and the price. A binary search would help find the item price if the array were sorted by name, giving you a time of O(log n) per item. But that's not Bobbie's speed – we want instant time, O(1). That's what hash functions are for.

Hash Functions

So, what is a hash function?

It is a function that takes an input of string1 and gives you a number back. If you want me to be more technical, I would say they map a string to a number.

While it may look like there is no real pattern between the input string and the output number, hash functions do have a couple of requirements:

Consistency is key. For example, if you input “eggs” and get “2” back, you must get “2” every time you input “eggs.” If not, your hash table will fail.

Different words should be mapped to different numbers. For example, if a hash function always returns “2,” regardless of what you input, it's no good. Best case? Each different word must map to a unique number.

So, why is it useful to have a function that maps a string to a number?

Well, you could make your “Bobbie” using one of these.

Let's begin with an empty array:

             0                               1                              2                                3                               4

All product prices are then stored in this; let's start with eggs:

Eggs > 2

When you input “eggs” into the hash function, you get 2, so we store the price of the eggs at index 2:

|  | 2.79 |  |

             0                               1                              2                                3                               4

Next, we add Apple:

Apple > 1

And the hash function provides a “1,” so the apple's price is stored at index 1:

| 0.80 | 2.79 |  |

             0                               1                              2                                3                               4

Continue like this for all products; the array will fill up with prices.

So, when someone brings milk to the checkout, you don't have to search through the entire array for it; simply input “milk” as a string into the hash function, and it will return the index the price is stored at.

This saves you time because you don't have to search the array for prices, and there are a couple of reasons why this works:

Hash functions are consistent in mapping a name to the same index. Whenever “milk” is your input, you will always get the same index back. So, the hash function can be used first to determine what index the price of milk should be stored at and then again to locate where the price was stored.

Hash functions always store different strings to a different index. “Milk” is mapped to index 1, “Apple” is mapped to index 2, and so on. Each different string has a unique index.

Hash functions always know the size of the array and will only ever return a valid index number. If your array contains 10 items, the function won't return an index of 15 – it is invalid.

That's it; you built your “Bobbie.” All you have to do is put an array and hash function together, creating the hash table, a very useful data structure. However, unlike many data structures, the hash table has some additional logic.

While lists and arrays will map directly to memory, hash tables work a little differently, smarter if you like. The hash function determines the best place to store the elements.

Hash tables are complex data structures but are one of the most useful you will ever learn. You may also see them called dictionaries, maps, hash maps, and associative arrays, but they are incredibly fast regardless of what they are named. Remember chapter 2, where we said how fast it was to get an element from an array? Instant. And, because hash tables store data in arrays, they are just as fast.

The likelihood of you having to implement these yourself is incredibly slim because most languages already have a built-in hash table implementation; for example, in Python, they are called dictionaries.

You can use the dict function to make a new table:

>>> book = dict()

The new hash table is called 'book,' so let's add a few prices:

>>> book[“apple”] = 0.80

>>> book[“milk”] = 1.69

>>> book[“Eggs”] = 2.79

>>> print book

And you should see:

{'apple': 0.80, 'milk': 1.69, 'eggs': 2.79 }

That wasn't too difficult, so now we want to ask the price of an apple:

>>> print book[“apple”]

Which should return:

0.80

Hash tables contain key-value pairs – in our example, the key is the product name, while the price is the value, so we can say that they map keys to values.

Now let's look at some instances where hash tables are used.

Use Cases

We see hash tables used for many things; these are some of the more common:

For Lookups

Your smartphone is an excellent example because it has a built-in phone book. When you add your friends' details, you input their names and an associated phone number. So, if you were to create a phone book like this, it would need the following functionalities:

Add a name and an associated phone number

Input the name and retrieve the associated phone number

This is one of the best use cases for a hash table, and these are perfect for when you want:

To map one thing to another

Look for something

Creating a phone book is not difficult:

First, you create your new hash table:

>>> phone_book = dict()

As an aside, if you are using Python, there is a really easy way to create  a new hash table – just use a pair of curly braces like this:

>>> phone_book = {}

This is exactly the same as using >>> phone_book = dict()

The next step is to add some names and phone numbers:

>>> phone_book[“simon”] = 8946218

>>> phone_book[“emergency”] = 911

That is pretty much it!

If you want to find Simon’s phone number, all you do is input the key into the hash:

>>> print phone_book[“simon”]

8946218

Now think about doing this with an array instead. How would it be done?

This was just a small example, but hash tables are used for much larger-scale lookups. Think about the websites you visit. When you type a website name into your browser address bar, your computer needs to translate it into an IP address. For example:

Facebook.com | 173.252.120.6
Google.com | 74.125.239.133

All websites have their own IP address, and mapping the name to the address is called DNS resolution – hash tables are perfect for this.

Stopping Duplicated Entries

Let’s say you are manning the booths on voting day. We know that people are only allowed to vote once, but how do you know if a person has already voted? Simple – when a person comes to vote, you request their full name, and then you check against a list of everyone who has already voted.

If their name appears on the list, they cannot vote again. If not, put their name on the list, and they can cast their vote. What happens towards the end of the day, and the list of people who have cast their votes is long? Whenever a new person comes in, you have to look down this long list and see if their name is on it – and it won't be in alphabetical order!

There is a much better way – a hash.

First, you create a hash that tracks everyone who has already cast their vote:

>>> voted = {}

When a new person comes in, you check their name in the hash:

>>> value = voted.get(“billy”)

The get() function will give you back the value “billy” if his name is in the table. If note, it will return None.

This is a simple way of checking names. Here’s the code:

Here’s the code:

voted = {}

def check_voter(name):

  if voted.get(name):

print “They already voted!”

  else:

voted[name] = True

print “They can vote!”

Let's see it in action:

>>> check_voter(“billy”)

They can vote!

>>> check_voter(“sally”)

They can vote!

>>> check_voter(“sally”)

They already voted!

When you input the name “Billy,” it tells you they can vote; same with “Sally,” but when Sally tries to vote again, you get the message telling you they already voted.

If you stored all these names in a list, eventually, it would get really long and slow. A simple search would need to be run over every name, which takes time. If you use a hash table instead, the results are instant, making them great for stopping duplicated entries.

Using Them as a Cache

The last common use is for caching, a common term used by those who work on websites.

Let’s say you go to Facebook:

By typing Facebook.com in your browser address bar, you are requesting access to their server

After a split second’s thinking, the server produces the website

The website is displayed to you

When you log in to Facebook, you see your news feed, which is made up of stories collected by Facebook from all your friends’ news feeds. It collects these stories and shows them to you, but it could take a couple of seconds. To you, that seems a long time, but you must remember that Facebook has millions of users – a couple of seconds for each user can really add up, and their servers work so hard to sever everyone. Could Facebook be made any faster and have less work to do? We’ll come back to this in a minute.

Another example – your child continually questions you about the planets, and you need to run a quick Google search to get the answers. This takes a few minutes. Let’s say they ask you the same question repeatedly: “how far is the moon? Soon enough, you would know the answer without looking for it – 238,900 miles, if you were interested. That is how caching works – instead of calculating the data every time, the website remembers the information.

Let’s go back to Facebook. All the content you see on your Facebook page is tailored specifically to you. The servers consider what you might be interested in seeing whenever you log in. But when you aren’t logged in, all you see is the home page – everyone sees exactly the same thing. Facebook is constantly asked for the home page when a person logs out, so it stops its server from having to figure out what the home page might look like – instead, the home page is memorized and sent to every person who asks for it.

That is caching, and there are two advantages to it:

The web page appears much faster, like the example of the distance between the moon and the earth – next time you get asked the question, you can answer it without having to look it up.

Facebook doesn’t have much work to do, making it faster.

Caching is one of the most-used ways to speed things up, and all the biggest websites use it. All the cached data is stored in a hash. Facebook caches more than just the home page – it does the Contact, About, Terms and Conditions, and many more pages besides.

To do that, a mapping is required from the URL of the specific page to the data. When you open a  Facebook page, it looks to see if the page is in the hash.

This is the code:

cache = {}

def get_page(url):

  if cache.get(url):

return cache[url]

  else:

data = get_data_from_server(url)

cache[url] = data

return data

Here, the server will only do the work if the URL isn’t stored in the cache.

Before the data is returned, we ensure it gets stored in the cache. When someone else asks for that specific URL, the data is sent from the cache and the server doesn’t need to do the work.

Collisions

I said a while back that all the major programming languages have their own built-in version of a hash table; this means you will probably never have to write your own. For that reason, I won't go into too much detail about the internal workings of the hash table. However, you will still need to monitor performance, and to understand how hash tables perform, you need to know about collisions.

The rest of this chapter is dedicated to both those subjects.

Remember that I told you hash functions always map different inputs to different array slots? That was sort of a lie. The reality is that writing a hash function that does this is virtually impossible.

Here’s a simple example:

Let’s say you have an array with 26 slots

And a simple function that assigns array slots alphabetically.

Can you spot the problem already? You want to add the price of Apples, and it goes to the first slot – it is alphabetical, after all.

Next, you want to add bacon, which gets assigned to the second index. That’s great; it all works – until you want to add apricots. Because it is alphabetical, the hash assigns the first slot again.

But hang on! Apples have already been given the slot. What do we do?

When two items are assigned to the same slot, it is known as a collision.

This causes a big problem. Storing apricots there overwrites apples, and when you want the price of apples in the future, you get the price of apricots. Collisions are not good, and you need to find a way to work around them. Luckily, there are a few ways to deal with them.

The first and simplest way is to use a linked list in a slot where several keys are mapped. Take our first array slot, where we already have two items – apples and apricots. That slot would have a linked list in it. However, there is a trade-off. A search for bacon is still fast, but now, when you search for apricots, it’s a little slower. It's not an issue where you have small linked lists, but it is for bigger ones.

Okay, let’s take this to the ridiculous. You still have your array of 26 slots, but your store only sells food starting with the letter A. Your hash table will be virtually empty, except for the first slot, which has the biggest linked list you've ever seen! Every element in that table is parked in that linked list – that’s going to slow things right down.

You can learn two things from this:

The hash function is critical. In this case, it mapped the keys to one slot, but in an ideal world, it would map them across the hash evenly.

If you use linked lists that grow too big, they slow things down. Using the right hash function ensures that it won't happen.

Provided your hash function is a good one, it will significantly reduce the number of collisions, but how do you choose the right one? We’ll talk about that next.

Performance

At the beginning of this chapter, you worked at a small grocery store and wanted a system that instantly allows you to find prices. We learned that hash tables are incredibly fast. For the average case, they take O(1), which is constant time, for everything they do.

Although we mentioned constants before, we haven’t looked at constant time yet, and all it means is that the time remains the same, no matter how much is in your hash table. For example, a simple search is completed in linear time, while binary searches take log time, which is much faster. For lookups in a hash table, it’s constant time.

It doesn’t matter how many elements your hash table has – 1, 10, or a billion. It takes the same amount of time to retrieve something from it. This is the same time that retrieving an array element takes. Again, your array can be really small or huge; it still takes the same time.

So, in average cases, hash tables are fast but slow in the worst case, taking O(n) linear time. Look at the following table that compares run times for hash tables against lists and arrays:

| Hash Table – Average | Hash Table – Best | Arrays | Linked Lists
Search | O(1) | O(n) | O(1) | O(n)
Insert | O(1) | O(n) | O(n) | O(1)
Delete | O(1) | O(n) | O(n) | O(1)

Pay attention to the average case times for the hash table – they are the same speed as arrays at getting a value's index. They are also the same speed as lists at deleting and inserting. You get everything with a hash table – but only in the best/average case. In the worst case, they show slow run times for all operations. This is why you should avoid worst-case with a hash table, which means avoiding those collisions. To do that, you need the following:

Look at the average case for hash tables. Hash tables are as fast as arrays at searching (getting a value at an index). And they're as fast as linked lists at inserts and deletes. It's the best of both worlds! However, hash tables are slow at everything in the worst case. So you mustn't hit worst-case performance with hash tables. And that means avoiding collisions. To avoid collisions, you need two things:

Low load factor

Good hash function

Load Factor

Calculating a hash table’s load factor is simple.

Because hash tables store data in arrays, all you need to do is count how many array slots are occupied. For example, the following hash table’s load factor is 2/5, which equals 0.4:

| 1 |  | 0 |

That’s because two out of the five slots are occupied with data.

What about this array?

| 2 |

The answer is 1/3 because only one slot is full – the load factor is used to measure the number of empty slots left in the hash table.

Let’s say you need 100 product prices stored in a table with 100 slots. In the best case, each product would be placed in a slot of its own. The load factor for a table like this is 1, but if you only had 50 slots, the load factor would be 2 – the products could not all be given their own slot because there aren’t enough. If the load factor is 1, each item has its own slot; if it's more than 1, there aren’t enough slots for all the items.

When the load factor increases, it indicates that your hash table needs more slots, and we call this ‘resizing.’ How do we do that?

First, you need a bigger array, and a general rule is to create one twice the size.

Next, you use the hash function to insert all your items into the new hash table.

| 5 |  |  | 2 | 4 |  |

The new table’s hash factor is 3/8, which is much better. The lower the load factor, the slimmer the chance of collisions, and the higher chance of your table performing well. Try to follow the best practice of resizing when your load factor is more than 0.7.

So, it might have occurred to you that resizing takes a while. It does, and it isn’t cheap, either. You don’t want to do this any more than you really have to. However, even with resizing, the average case is still O(1).

Key Takeaways

In this chapter, you learned:

That hashes work well for mapping relationships between things, can eliminate duplicated data, and are good for caching data

You will rarely have to implement a hash table as most programming languages have their own implementation.

Hash tables are powerful and fast, allowing you to model your data differently

Hash tables are created by combining arrays and hash functions

You should avoid collisions by using the right hash function

Hash tables offer fast times for operations, such as insert, delete, and search

When your table’s load factor exceeds 0.7, the hash table should be resized

Chapter 6: Breadth-First Searches

In this chapter, you will learn:

How to use the graph data structure to model networks

The breadth-first search algorithm which runs on graphs and answers questions

Directed and undirected graphs

A sorting algorithm called topological sort which uncovers the dependencies between nodes

In this chapter, you will learn about graphs, and the first thing to tell you is what they are, and then we'll look at a graph algorithm called breadth-first search. This useful algorithm helps you identify the shortest distance between two items. But the shortest distance doesn't necessarily indicate the distance in miles!

The algorithm can be used to:

Write an AI that finds the least amount of moves for victory in chess or checkers

Write a spell-checker that provides the least number of edits between a misspelled word and the proper spelling

Find your nearest doctor

Introduction to Graphs

Let's say you are visiting San Francisco. You want to do a trip from Twin Peaks to the Golden Gate Bridge by bus, but you want the shortest possible trip there. You have several options, and none allow you to do it in just one bus.

What algorithm do you use to find the shortest path?

Ask yourself some questions:

Can I get there in one step? Where are all the places I can go in one step?

I can't get to the bridge, so can I get there in two steps?

I still can't get to the bridge? Can I do it in three steps?

Now you can see the bridge, so you can do it in three steps.

Other routes will take you to the same place but take longer. Your algorithm determined that three steps is the shortest distance.

We call this a shortest-path problem. It requires that the shortest distance or something is found – it could be the number of moves to win a game of chess, the shortest distance to your parents' house, or any problem that requires the shortest distance to be found. The algorithm for this is breadth-first search.

To work out the journey from Twin Peaks to the bridge, you need to do the following:

Develop a graph to model the problem

Use breadth-first search to solve it

Let's look at graphs.

What is a Graph?

A graph is a type of structure that models connections. For example, let's say you are playing cards with your friends. You want to show who owes money to whom. You could demonstrate that Simon owes Billy money like this:

Perhaps the whole graph would look like this:

Simon owes Billy, who owes Sally, who owes Molly, who owes Mike, who owes Simon. All graphs comprise nodes and edges, and that's all there is to a graph. One node can directly connect to multiple nodes, which are classed as the original node's neighbors. In the graph above, Billy is Simon's neighbor, but Molly isn't Billy's neighbor because they are not directly connected.

This is just a simple graph, but they are used to show the connection between things.

Breadth-First Search

So far, we've looked at a few search algorithms, and breadth-first search is another one. This algorithm is run on graphs and is used to find the answers to two questions:

Does the graph have a path between nodes A and B?

What's the shortest path between nodes A and B?

We saw this algorithm in action with the Golden Gate Bridge problem. That was the second question – the shortest path. Now we'll look deeper into the algorithm and see if we can answer the first question.

Let's say you own a farm, and you grow pears. You want to find a seller for your product, and you might just be connected to someone on Facebook who sells pears. It's pretty easy to look through your friends' list:

First, list all the friends you want to search

Next, look at every person individually and see if they sell pears

What if none of them do? Then you search the friends of your friends. 

When you look at each of your friends, make a list of their friends

This way, you search your and their friends looking for a pear seller in the network

So, for example, you look at your friend, Tony, and find he doesn't sell pears. But you add all his friends to your search list, and you'll start on that list once you've gone through your own friends.

This is the breadth-first search in action.

Find the Shortest Path

So, to recap, you want the following questions answered by breadth-first search:

Is there a path between nodes A and B? – Does your network contain a pear seller

What's the shortest path between nodes A and B? Who is the nearest pear seller to you?

You've seen how the first question is answered, so now we'll answer the second one.

Who is the nearest pear seller?

The friends on your Facebook list are first-degree connections. The friends of your friends are second-degree.

Ideally, you want a first-degree to second-degree connection and a second-to third-degree connection if possible. So, you don't look through the second-degree connections until you have checked the first-degree ones to make sure there is no pear seller. Breadth-first search does this automatically.

It works by radiating the search outwards from the first-degree connections to the second, third, and so on in degree order.

You could also look at this problem in terms of first-degree connections being added to the list, followed by second-degree, third, etc. Then you simply look down the list to see if there is a pear seller. You search the first-degree connections first, then the second, third, etc., until you find a pear seller. That way, the algorithm finds the nearest pear seller.

Breadth-first does two things: finds the path between A and B and the shortest path.

However, you will find this works only when the list is searched in the order it is written or added to. So, if you searched second-degree connections before the first-degree ones, the algorithm might find a pear seller who is a long distance away. So, searching the list in the order they were added is important, and this is done using a data structure called a queue.

Queues

Queues work in the same way they do in the real world. Let's say you are queuing with a friend to get into a theater show. You get into the theater first if you are before your friend in the queue.

Queues are much the same as stacks but with a fundamental difference – queues will not allow you to access a random element. Instead, they have just two operations – enqueue and dequeue.

If two items are enqueued, the first item queued is the first one dequeued. This can be used in a search list – the first person you add (enqueue) to the list is the first person removed (dequeued) from the list.

Queues are known as FIFO data structures, which stands for First In, First Out. A stack is a LIFO data structure – Last In, First Out.

Let's get on with implementing our breadth-first search algorithm:

First, the graph must be implemented in code. Don't forget that a graph has multiple nodes, each connected to its neighboring nodes.

So, how would a relationship like “Billy - > Billy” be expressed?

You already know how to express relationships – using a hash table. As a recap, hash tables let you map keys to values, so, in this example, you would map one node to every neighbor.

Here’s the Python code:

graph = {}

graph[“you”] = [“annie”, “billy”, “charlie”]

Here, we mapped “you” to an array so, when you call

graph[“you]

you get an array containing every neighbor stored in “you.”

Graphs are only nodes and edges, so this is the only thing you to have a Python graph. But what if you have a bigger graph containing many more names?

Here's the code you would need for that:

graph = {}

graph[“you”] = [“annie”, “billy”, “charlie”]

graph[“billy”] = [“khan”, “paula”]

graph[“annie”] = [“paula”]

graph[“charlie”] = [“timmy”, “joanna”]

graph[“khan”] = []

graph[“paula”] = []

graph[“timmy”] = []

graph[“joanna”] = []

Quick question: does the order you write your key-value pairs matter? Could you write the following?

graph[“charlie”] = [“timmy”, “joanna”]

graph[“khan”] = []

rather than

graph[“khan”] = []

graph[“charlie”] = [“timmy”, “joanna”]

Cast your mind back to the last chapter, and it will tell you the answer – the order does not matter. Because hash tables don’t have any specific ordering, you can add the pairs in whatever order you want.

Khan, Paula, Timmy, and Joanna have not got any neighbors. They may have a node pointing to them, but they do not point to anyone else.

This is a directed graph and is so-called because there is only a one-way relationship. Khan may be Billy’s neighbor, but Billy is not Khan’s neighbor.

The opposite of this is an undirected graph, where both nodes are neighbors to each other. So, Khan is Billy’s neighbor, and Billy is Khan's neighbor.

As a recap, this is how the implementation works.

The first step is to make a queue – in Python, the deque function is used:

from collections import deque

search_queue = deque()

search_queue += graph[“you”]

Remember, when you call graph[“you], you get a list of your neighbors, which are added to the search queue.

Here’s the rest:

while search_queue:

person = search_queue.popleft()

if person_is_seller(person):

print person + “is a pear seller!”

return True

else:

search_queue += graph[person]

return False

Lastly, you still need to add a function called person_is_seller to tell you when a specific person sells pears. You could use this:

def person_is_seller(name):

return name[-1] == ‘m’

This function will look for anyone with a name ending in 'm.' If it finds one, that person is a pear seller.

The breadth-first search function will traverse the queue and will continue until one of two things happens:

It finds a pear seller

The queue is empty and no pear seller found

Annie and Billy both have the same friend called Paula. That means Paula is added twice to the queue, once when Annie's friends go on the list and once when Billy's friends are added. That means the search queue contains two instances of Paula.

However, we only need to look at Paula once to know if she sells pears, so checking her name twice means doing extra work you don't need to do. When you look at a name, that person needs to be marked as checked so you don't look at them again.

Failing to do this could result in an infinite loop.

Let's say your graph looks like this:

First, all your neighbors are in the search queue.

You look at Paula and determine that she is not a pear seller. Her neighbors are then added to your search queue.

Then you look at yourself. You aren't a pear seller either, so all your neighbors are added to the queue.

This continues as an infinite loop – the search queue will simply flip between you and Paula.

Before you look at a  person, you must ensure they haven't been looked at before. That means retaining a list showing all those people already checked.

Here’s the final breadth-first search code, considering all that:

def search(name):

search_queue = deque()

search_queue += graph[name]

searched = []

while search_queue:

person = search_queue.popleft()

if not person in searched:

if person_is_seller(person):

print person + “is a pear seller!”

return True

else:

search_queue += graph[person]

searched.append(person)

return False

search(“you”)

Have a go at this code yourself and play about with the person_is function – change it to something else. Does it print what it should?

Running Time

When you search the whole network looking for a pear seller, you follow every edge (the connection between people.) This means you have a minimum running time of O(number of edges).

You also retain a queue containing all the people who need to be searched. Adding to the list takes O(1) – constant time. When you do this for each person, it takes O(number of people) time.

Key Takeaways

Here's what you learned:

The breadth-first search algorithm answers the question – is there a path between A and B?

If a path exists, the algorithm finds the shortest path

You can model a problem as a graph and then solve it using a breadth-first search

Directed graphs contain arrows to indicate the connections, and the relationship is one-way, following the arrows

Undirected graphs do not have arrows, and relationships are two-way.

Queues are classed as FIFO data structures– First In, First Out

Stacks are classed as LIFO data structures – Last In, First Out

Always check people in the exact order you added them to the search list. This means you need to use a queue. If not, you cannot contain the shortest path

When a person has been checked, they should not be checked again. If this is not dealt with, you could have an infinite loop.

Chapter 7: Dijkstra – Taking the Shortest Path

In this chapter:

We'll continue talking about graphs, and this time we'll cover weighted graphs. Weights are a way to add more weight or deduct it from graph edges.

We'll cover Dijkstra's algorithm, a popular shortest path algorithm that works well on weighted graphs

We'll also talk about graph cycles – hint, Dijkstra's doesn't work in these

The previous chapter looked at ways to get from A to B. When you use a satellite navigation system, you often want to find the fastest route to your destination. However, these algorithms look for the shortest path, which may not necessarily be the fastest. It is the shortest because it has the lowest number of parts, but when you add in travel time, you start to see that maybe there is a faster way.

We also used the breadth-first search algorithm, which helps you find which path has the least number of parts. But what if you don't want that path? What if you want the fastest? In that case, you would use Dijkstra's algorithm.

Let’s see how Dijkstra works by looking at a graph:

      6    1

        W

   2        5

As you can see, the segments all have a travel time, documented in minutes. Dijkstra's algorithm runs from start to finish in the shortest time possible.

If we used breadth-first, we would get the shortest path of Start - > A (6 minutes) - > Finish (1 minute), which equals 7 minutes. Is there another faster path? Well, Dijkstra's algorithm has four steps:

Locate the node you can reach in the least time – this is the 'cheapest' node

Update all this node's neighbor's costs – more about that in a bit

Repeat for each graph node

Work out your final path

Let's walk through those steps:

Step One:

From the start point, you need to decide whether to travel to node A or B. How long would it take to reach each one?

We know we can reach node A in 6 minutes and node B in 2 minutes. However, we don't know about the other nodes right now. Because we don't know how long it would take to reach the finish, we use infinity (more later). Node B is nearer as it is only 2 minutes.

Step Two:

Follow the edge from B to work out the travel time to all the neighbors for node B. And you just found your shorter path. In step one, it took 6 minutes to get to node A, but you can do it in 5 minutes by using node B.

When a shorter path is found for one of node B’s neighbors, you must update its cost. Here, we discovered:

A shorter path to node A – 5 minutes instead of 6

A shorter path to reach the finish – from infinity to 7 minutes

Step Three:

Now repeat all that.

Step one – locate the node you get to in the least amount of time. We did node B last time, so this time, go to node A as it has the next smallest time

Step two – update node A’s neighbor’s costs

Now we can get to the finish in just 6 minutes.

When you have run the algorithm for all nodes except the finish, you will know the following:

How long does it take to get to node B – 2 minutes

How long does it take to get to node B – 5 minutes

How long does it take to get to the finish – 6 minutes

Step four will have to wait for now – I’ll show you how to calculate the final path shortly. For now, here’s the final path – we go from Start -> B -> A -> Finish.

      6    1

        W

   2        5

If we’d used breadth-first, it would not have seen this as the shortest path because it consists of three parts. But, we can find an even shorter way with only two parts Start - > A - > Finish.

When we used breadth-first in the last chapter, it was to determine the shortest path, which meant the one with the least number of parts. However, with Dijkstra’s algorithm, each part can be assigned a weight (a number); the algorithm then looks for the path with the least total weight.

Terminology

Before we look at a few more examples, we should look at some terminology.

As mentioned, the graph edges have associated numbers in Dijkstra’s algorithm – these are weights.

Graphs that contain weights are weighted graphs, while those without are unweighted graphs.

A breadth-first search is used on unweighted graphs to find the shortest path, while Dijkstra’s is used on weighted graphs.

A graph may also contain a cycle that looks like this:

Having a cycle means starting and ending at the same node. Let’s say you want to determine the shortest path in a graph containing a cycle. Should you follow the cycle? Does it make sense?

You have two choices – follow the cycle or find a path to avoid it. Either way, you will end up back at the same node but using the cycle adds weight. And if you wanted to, you could follow it twice. However, you add more weight whenever you follow the cycle, so it will never provide you with the shortest path.

Lastly, we can’t forget the undirected and directed graphs we discussed earlier. Remember that the relationship is two-way in an undirected graph – that's a cycle. Each edge in an undirected graph simply provides another cycle.

Let’s get back to our examples.

A Book for a Guitar

Meet Johnny. He wants to trade a book for a guitar. Tim offers him his favorite movie poster or a rare recording of his favorite music plus $10 in exchange for the book. Annie is listening in and says she's heard there's a fantastic song on the recording and offers a drum set or saxophone in exchange for it. Simon pipes up that he wants to learn the drums and offers his guitar in exchange for the drum set.

That's great! Johnny now knows he can trade up to the guitar he wants. All he needs is a little cash, but he needs to work out the least he can spend to achieve his trades. Here's what the graph looks like.

15

52020

03010

      35

Here, every item Johnny could trade for is a node, and the weights indicate how much money would be needed to pay for a particular trade. He could trade the poster for the drums for $30 or the recording for the sax for $20. How will Johnny find the cheapest way to get the guitar he wants?

Here come’s Dijkstra’s to help out. Remember, it has four steps; this time, we'll cover all four. The final step will be to calculate the final path.

Before we start, we need to do a bit of work.

First, create a table showing the cost of each node – the cost indicates the expense of getting from one node to another.

NODE | COST
Recording | 5
Poster | 0
Sax | ∞
Drums | ∞
Guitar | ∞

Note the infinity sign - ∞ - this indicates that we haven't reached these nodes from the start yet. As we go along, this table will be updated. Later, you will also need a third column – the parent column. This is for calculating the final path, but we'll get to that shortly.

Let's get started on the algorithm.

Step One

Here, we need to find the cheapest node, the poster, as it is $0. Can we trade for the poster any cheaper? This is important, so think hard about it – are there any trades that will allow Johnny to get the poster for less than $0?

The answer is clearly no in this case because there is nothing cheaper than $0. Try looking at it this way. You are traveling from your house to work.

      6    3

        1   2

   2        3

The weights indicate the time in minutes. It will take you 2 minutes if you head towards the school and 6 minutes to take the park route. Can you head towards the park and reach the school in under 2 minutes? No, because it takes 6 minutes to get to the park, longer than it takes on the direct route to the school. So, is there a faster route to the park? Yes, you head to the school first, taking 2 minutes, and then to the park, an additional minute.

This is what Dijkstra's is all about – finding the cheapest node. In our case, there isn't one, so the poster is the right one.

Step Two

Next, you need to work out the cost of reaching its neighbors. We know how much the drums and sax cost because we set their value earlier. We know we can get directly from the poster to the drums and sax, so we set the poster as their parent node.

PARENT | NODE | COST
Book | Recording | 5
Book | Poster | 0
Poster | Sax | 30
Poster | Drums | 30
| Guitar | ∞

Now we repeat step one to find the cheapest node, which is the recording at $5.

Repeat step two again, and update its neighbor's values. That means the price of the drums and sax were updated, and we found that the cheapest route, so far, is to follow the edge from the recording.

1520

52020

03010

      3525

– that means the recording becomes the new parent for the sax and drums.

PARENT | NODE | COST
Book | Recording | 5
Book | Poster | 0
Recording | Sax | 20
Recording | Drums | 25
| Guitar | ∞

Repeat step one again – the next cheapest is the drums, so update its neighbors:

15

52020

40

03010

    35

Now you have your guitar price – you can trade the drums for it.

PARENT | NODE | COST
Book | Recording | 5
Book | Poster | 0
Recording | Sax | 20
Recording | Drums | 25
Drums | Guitar | 40

The drums are set as the parent, and the Saxophone is the last node.

15

52020

35

03010

    35

PARENT | NODE | COST
Book | Recording | 5
Book | Poster | 0
Recording | Sax | 20
Recording | Drums | 25
Saxophone | Guitar | 35

Johnny can now get the guitar cheaper by trading the saxophone, making his cheapest path $35.

Now, earlier I said that we would be calculating the final path. We know the cheapest/shortest path will cost $35, but how do we work it out? To start with, we look at the guitar's parent.

PARENT | NODE
Book | Recording
Book | Poster
Recording | Saxophone
Recording | Drums
Saxophone | Guitar

The guitar's parent is the saxophone, which means Johnny can trade the saxophone for the guitar. So that's the edge we follow.

Here's how to follow the edges:

The guitar has the saxophone as its parent

The saxophone has the recording as its parent.

So, from start to finish, Johnny trades the book for the recording, the recording for the saxophone, and the saxophone for the guitar. You can see the entire path when you follow the edges back through the parent nodes.

Negative-Weight Edges

In the previous example, Tim offered a trade – the book for a poster or recording. Let's say that Julie pops up and offers the recording in exchange for the poster, but she'll also give Johnny an extra $7. The cost of the trade to Johnny is nothing, and he makes $7 out of it.

So how is this shown on the graph?

    5

N

0

The edge between the recording and the poster has got a negative weight because if Johnny goes for the trade, he gets $7 back. Johnny now has two routes to choose from:

He can go from the book directly to the poster, which costs $0

Or he can go from the book to the recording, costing $5, and then to the poster. In the latter part, he receives $7 back, thus making a net profit of $2. That would be the sensible route to take.

Now, he can also trade between the poster and the saxophone and he has a choice of two paths:

5

      N

   0

        35

He can trade the book for the poster at the cost of $0 and then the poster for saxophone at the cost of $35 – the total cost is $35.

Or, he can trade the book for the recording at the cost of $5, trade the recording for the poster, and receive $7, then trade the poster for the saxophone at the cost of $35. The total cost is $33. So, the second path is the best, right? It's the cheapest.

Newsflash!

Dijkstra's algorithm will send you on the longer path. Why? This algorithm cannot be used if your graph has negative-weight edges because these edges will break Dijkstra's algorithm. Let's see how it works.

First, you need your table showing the costs:

NODE | COST
Recording | 5
Poster | 0
Sax | ∞

Next, we want the cheapest node and update the neighbors.

In this case, the poster is the cheapest at $0, which means there isn't any way to get to the poster cheaper. At least, that's what Dijkstra's will tell you, but you know different. For now, we'll update the neighbor's costs – the saxophone is now $35.

Now we move on to the next cheapest node that we haven't processed and update the neighbor's costs.

The poster node has already been processed, but now you need to update the cost to -2. That is a huge red flag. Once a node is processed, it indicates there isn't a cheaper way to reach it, but you just found one. Because the saxophone has no neighbors, the algorithm ends, and the final costs are:

NODE | COST
Recording | 5
Poster | -2
Sax | 35

The cost of getting the saxophone is $35, but you know another path that will only cost $33. The algorithm never found that path because it assumed there was no cheaper way to get to the poster node once it was processed. This assumption works only when the graph doesn't have negative-weight edges.

If you need to find the shortest paths in negative-weight graphs, use Bellman-Ford – this algorithm is not covered in this book, but you can find plenty of info about it on the internet.

Let's implement Dijkstra's algorithm in Python code, using this graph:

      6    1

        W

   2        5

This requires three hash tables, as you'll see throughout – graphs, costs, and parents.

The parent and costs tables will be updated as we go through the algorithm. First, though, the graph must be implemented using a hash table.

graph = {}

In the previous chapter, the node's neighbors were stored in a hash table like this:

graph[“you”] = [“annie”, “billy”, “charlie”]

However, this time, we need the neighbors stored and the cost of getting to each one. Some, like Start, have two neighbors; how are the edge weights represented? Can we not just use a hash table?

graph[“start”] = {}

graph[“start”][“a”] = 6

graph[“start”][“b”] = 2

The hash table is graph[“start”], and we can obtain all Start's neighbors like this:

>>> print graph[“start”].keys()

[“a”, “b”]

Start to A has an edge, as does Start to B. How do we find the weights?

>>> print graph[“start”][“a”]

2

>>> print graph[“start”][“b”]

6

Here are the remaining nodes and neighbors added to our graph:

graph[“a”] = {}

graph[“a”][“fin”] = 1

graph[“b”] = {}

graph[“b”][“a”] = 3

graph[“b”][“fin”] = 5

graph[“fin”] = {}

Note there are no neighbors for the finish node.

The graph hash table is:

Start | A | 6
B | 2
A | Finish | 1
B | A | 3
Finish | 5
Finish |

Now we need another hash table for each node's costs.

A | 6
B | 2
Finish | ∞

A node's cost indicates the length of time taken to get from Start to the node. We already know that Start to node B is 2 minutes and Start to node A is 6 minutes, even though you may find a shorter path. At this point, we don't know the length of time to get to Finish. Whenever we don't know this information, we use the infinity symbol (∞). How do we represent infinity in the Python language? Like this:

infinity = float(“inf”)

Let’s create that hash table in code::

infinity = float(“inf”)

costs = {}

costs[“a”] = 6

costs[“b”] = 2

costs[“fin”] = infinity

Lastly, the parent hash table:

A | Start
B | Start
Finish |

And here’s the code:

parents = {}

parents[“a”] = “start”

parents[“b”] = “start”

parents[“fin”] = None

Now we need to track the processed nodes so we don't process them again – this requires an array:

processed = []

That's everything set up; now, we can dive into the algorithm. Here's the code:

node = find_lowest_cost_node(costs)

while node is not None:

cost = costs[node]

neighbors = graph[node]

for n in neighbors.keys():

new_cost = cost + neighbors[n]

if costs[n] > new_cost:

costs[n] = new_cost

parents[n] = node

processed.append(node)

node = find_lowest_cost_node(costs)

That is how Dijkstra’s algorithm works. We'll look at the function code in a bit, but first, we want to see how the find_lowest_cost_node algorithm works. The steps are:

Find the lowest-cost node

Obtain that node's cost and its neighbors

Loop through all the neighbors

Every node will have a cost indicating the length of time taken to get to it from Start. We want to calculate the length of time to node A if we took the Start>node B> node A path rather than Start>node A.

Comparing the costs tells us that there is another shorter path, so the cost must be updated.

A | 5
B | 2
Finish | ∞

Because this path travels through node B, B must now be the new parent.

A | B
B | Start
Finish |

That takes us back to the start of the loop. The Finish node's neighbor is for.

What length of time does Start to Finish take, going through node B? If you made it 7 minutes, you were correct. Previously, it was infinity, but 7 minutes is lower, so we update the cost and parent for Finish:

A | 5
B | 2
Finish | 7

A | B
B | Start
Finish | B

Now, node B can be marked as processed because all the costs for its neighbors are up to date.

Move on and find the next node that needs processing. Obtain node A's cost and neighbors – it only has one neighbor, which is Finish.

Right now, we have a time of 7 minutes to reach Finish, but if we went through node A, how long would it take? If you answered 6, that's correct, so update the cost and parents again:

A | 5
B | 2
Finish | 6

A | B
B | Start
Finish | A

You found another shorter path by going through A.

Once all the nodes are processed, the algorithm finishes.

Using find_lowest_cost_node makes it easy to find the cheapest node. Here’s the code:

def find_lowest_cost_node(costs):

lowest_cost = float(“inf”)

lowest_cost_node = None

for node in costs:

cost = costs[node]

if cost < lowest_cost and node not in processed

:

lowest_cost = cost

lowest_cost_node = node

return lowest_cost_node

Key Takeaways

In this chapter, you learned:

We use the breadth-first search algorithm in unweighted graphs

We use Dijkstra's algorithm in weighted graphs

Dijkstra will not work when a graph has negative weights

Chapter 8: Feeding Greedy Algorithms

In this chapter, you will learn:

About NP-complete problems, which are those that do not have a quick algorithmic solutions

How to identify these problems easily, so you know you don't need to waste time looking for a speedy algorithm to solve them

How to use approximation algorithms to find a solution to these NP-complete problems

About one of the simplest strategies to solve problems, the greedy strategy

Let's dive right into it.

College Scheduling

Let's say you have a room in college and you need to hold the maximum possible number of lessons in it. Here are the classes you want to schedule:

LESSON | STGEOGRAPHY TIME | END TIME
Geography | 9.00 am | 10.00 am
English | 9.30 am | 10.30 am
Art | 10.00 am | 11.00 am
History | 10.30 am | 11.30 am
Mathematics | 11.00 am | 12 noon

Obviously, all these lessons cannot be held in the room because they overlap in time, but you want as many as possible. How do you choose which lessons to hold to ensure you get the maximum possible amount?

This doesn't sound easy to solve, but the algorithm is easier than you think.

Here's how the algorithm works:

Choose the lesson with the earliest finish time. This will be your first lesson

Next, choose a lesson that starts after the first class has finished, choosing the next one that ends the earliest. This is your second lesson

Continue until you get the answer.

Let's try this.

Geography ends first, so you choose that class

LESSON | STGEOGRAPHY TIME | END TIME |
Geography | 9.00 am | 10.00 am | Yes
English | 9.30 am | 10.30 am |
Art | 10.00 am | 11.00 am |
History | 10.30 am | 11.30 am |
Mathematics | 11.00 am | 12 noon |

Next, we need the class that starts after Geography ends and finishes the next soonest. We can't have English, because it overlaps with Geography but Art looks good:

LESSON | STGEOGRAPHY TIME | END TIME |
Geography | 9.00 am | 10.00 am | Yes
English | 9.30 am | 10.30 am | No
Art | 10.00 am | 11.00 am | Yes
History | 10.30 am | 11.30 am |
Mathematics | 11 am | 12 noon |

Lastly, History overlaps Art, but Mathematics will work:

LESSON | STGEOGRAPHY TIME | END TIME |
Geography | 9.00 am | 10.00 am | Yes
English | 9.30 am | 10.30 am | No
Art | 10.00 am | 11.00 am | Yes
History | 10.30 am | 11.30 am | No
Mathematics | 11.oo am | 12 noon | Yes

So, your three lessons are:

Geography – 9.00 am to 10.00 am

Art – 10.00 am to 11.00 am

Mathematics – 11.00 am to 12 noon

Some people believe that, because this is such an easy and obvious algorithm, it's probably wrong. However, that's where greedy algorithms step in – they are easy. Quite simply, you pick the optimal choice at each step.

In our example, when choosing a lesson, we choose the one that finishes the earliest. By choosing the “locally optimal” solution at each step, we get the “globally optimal” solution at the end. And this simple algorithm finds the best solution to our problems. Sure, they don't always work but writing them is simple. Here's another example.

The Knapsack Problem

Let's say you are a shoplifter. A greedy one. You've got a knapsack on your back, and you enter a store. There's so much you can steal, but you only have a certain amount of room in the knapsack. It can hold a maximum of 35 pounds, and you need to get the maximum amount in. How do you work it out?

Again, we could try the greedy strategy:

Choose the most expensive item that will go in the knapsack

Choose the next most expensive item that will go in your knapsack

Continue

However, this time the strategy doesn't work.

Let's assume you can steal three items:

A television costing $3,000 and weighing 30 pounds

A television costing $2,000 and weighing 20 pounds

A games console costing $1,500 and weighing 15 pounds

Don't forget; your knapsack takes a maximum of 35 pounds. If you choose the most expensive item, the television, you won't have room for anything else.  Sure, you managed to steal $3,000 worth of items, but you could have got more. In fact, by only stealing one item, you waste 5 pounds of weight. If you had chosen the television and the games console, you would have got the maximum weight of 35 pounds and the most money - $3,500 worth of goods.

It's clear that the greedy strategy isn't ideal in this situation, but it does get you quite close.

We'll look at calculating the right solution in the next chapter, but for now, as a thief, you really don't care about being perfect; pretty good is near enough for you.

So, what's the takeaway? Perfect isn't always the best; it can be an enemy. Sometimes, you only need to be close enough, and that's where greedy algorithms often provide the best solution. They are simple to write, and they tend to get close enough.

Here's our third and last example.

Set-Covering Problem

Let’s say you are starting your own radio show and you want to reach viewers in every state. You need to determine what stations you should broadcast your show on to reach the maximum listeners. However, each station costs money, so you need the minimum number of stations to reach the maximum number of customers.

You obtain a list of the radio stations and the regions each covers. As usual, there’s some overlap, and you need to work out which stations to use.

This might sound easy, but it’s not. In fact, it’s very hard.

Here’s how it's done:

List all the possible subsets of the stations – this is known as the power set; in our example, we have 2^ n possible subsets

Choose the subset that has the smallest number of stations covering every state

And here’s where the problem lies – the amount of time needed to calculate all possible station subsets. Because there are 2^ n possible subsets, it takes O(s^ n) time. If you only had a small handful of stations, no more than 10, you could do it, but the reality is, there are thousands of stations. What will happen?

In all honesty, no algorithm could possibly do this fast enough, so what do you do?

Approximation Algorithms

And the greedy algorithms save us again. This algorithm comes as close as we can get:

Choose the station that covers the maximum number of states not covered by another – if a few have already been covered, that's okay

Repeat until you've covered all states

We call this an approximation algorithm, and these work when it's going to take too much time to work out an exact solution.

These algorithms are judged on two factors:

Their speed

How close they get to the optimal solution

Greedy algorithms are one of the best choices because they are simple and fast. In this case, it runs in O( n^2) time, with n representing the number of stations.

Let's look at how this is represented in code:

We'll keep things simple and use a subset of states and stations.

First, you list all the states you need to cover:

states_needed = set([“mt”, “wa”, “or”, “id”, “nv”, “ut”,

“ca”, “az”])

An array is passed in and is then turned into a set. Sets are similar to lists with one exception: an item can only show once – no duplicates are allowed.

Let’s say this was your list:

>>> arr = [1, 2, 2, 3, 3, 3]

And it was converted to this:

>>> set(arr)

set([1, 2, 3])

Note that the numbers 1, 2, and 3 only show up once because it's a set.

Next, you need a list of every station you want to choose from. I’ve used a hash:

stations = {}

stations[“kone”] = set([“id”, “nv”, “ut”])

stations[“ktwo”] = set([“wa”, “id”, “mt”])

stations[“kthree”] = set([“or”, “nv”, “ca”])

stations[“kfour”] = set([“nv”, “ut”])

stations[“kfive”] = set([“ca”, “az”])

We have our key-value pairs – the station names are the keys, and the states each cover are the values.

So, the station called Kone covers three states – Idaho, Nevada, and Utah.

Note that the values are all sets too. As you will see shortly, using sets for everything will make things much easier.

Lastly, you need to store your chosen set of stations:

final_stations = set()

How do we work out what stations to use?

There isn't necessarily only one right answer. You will need to look at every station and choose the one with most states not covered by another. We'll call this best_station:

best_station = None

states_covered = set()

for station, states_for_station in stations.items():

The second line, states_covered, is a set with all the states covered by this station but not by others. Using a for loop lets you look at every station to find the best one. Here's the for loop's body:

covered = states_needed & states_for_station

if len(covered) > len(states_covered):

best_station = station

states_covered = covered

What do you make of the first line?

covered = states_needed & states_for_station

That's an odd one; what's going on?

Sets

Let's say you have a set containing a list of fruits and another containing a list of vegetables.

Fruits:

Tomato

Apple

Peach

Vegetables:

Tomato

Peas

Potatoes

You can do quite a bit when you've got two sets:

Set Union – this means combining the two sets

Set Intersection – this means identifying those items that appear in both sets – in our case, that is 'tomato'

Set Difference – this means subtracting items in the first set from the second

Here’s an example:

>>> fruits = set([“apple”, “tomato”, “peach”])

>>> vegetables = set([“potatoes”, “peas”, “tomato”])

>>> fruits | vegetables

set([“apple”, “potatoes”, “peas”, “tomato”, “peach”])

>>> fruits & vegetables

set([“tomato”])

>>> fruits – vegetables

set([“apple”, “peach”])

>>> vegetables – fruits

Let’s get back to our code:

That line we looked at:

covered = states_needed & states_for_station

It's a set intersection – 'covered' contains a set of the states contained in both states_needed and states_for_station, which means it contains all the states covered by the station.

Next, we need to know if more states are covered by this station than the current best_station:

if len(covered) > len(states_covered):

  best_station = station

  states_covered = covered

If it does, this station will become the new best_station.

Once the for loop has finished, best_station can be added to the final station list:

final_stations.add(best_station)

Update states_needed; we can now remove the states covered by this station:

states_needed -= states_covered

And continue looping until there's nothing left in states_needed.

Here is the entire code:

while states_needed:

   best_station = None

   states_covered = set()

   for station, states in stations.items():

covered = states_needed & states

if len(covered) > len(states_covered):

best_station = station

states_covered = covered

states_needed -= states_covered

final_stations.add(best_station)

Lastly, print the stations and it should look like this:

>>> print final_stations

set(['ktwo', 'kthree', 'kone', 'kfive'])

Did this do what you thought it would? You could have chosen a different set of stations – 2, 3, 4, and 5. Let’s see the run time comparison between the exact and greedy algorithms:

Number of Stations | O(n!) Exact Algorithm | O(n2) Greedy Algorithm
5 | 3.2 seconds | 2.5 seconds
10 | 102.4 seconds | 10 seconds
32 | 13.6 years | 102.4 seconds
100 | 4 x 1021 years | 16.67 minutes

As you can see, the greedy algorithm is always faster.

NP-Complete Problems

We needed every possible set calculated to solve our set-covering problem. This might have put you in mind of the traveling salesperson problem we looked at earlier in the book, where a salesperson needed to get to five cities in the shortest possible route.

To do that, all possible routes needed to be calculated – how many routes would this be?

Let's break the traveling salesperson down into steps.

We'll start small – we've only got two cities, so we only have two routes to choose from:

Route 1

St Marin - > San Francisco

Route 2

San Francisco - > St Marin

But aren't these both the same routes? Surely both are the same distance? That isn't necessarily the case. Some major cities have many one-way systems, so you might need to take a longer route to get out of the city and onto the highway.

You might ask yourself if there is a certain city you should start from in the traveling salesperson problem. Let's say you are that salesperson and you live in San Francisco. You need to get to four more cities, but San Francisco would be your starting point.

In some problems, the start city will not be set. Let's say you are a parcel delivery company and need to deliver a package to San Francisco Bay. The package arrives by plane at one of 50 parcel delivery points in the area, where it is loaded on a truck that goes all over the place delivering parcels. Which of these delivery points should the package be flown to? Because the starting point is not known, you would need to work out that location and compute the best path.

Back to our two routes – both have the same running time, but the easiest example is when the start point is not defined.

What if we had three cities? How many routes would there be now? If Berkeley were your starting point, that would give you an additional two cities:

Route 1:

Berkeley - > Marin - > San Francisco

Route 2

San Francisco - > Marin - > Berkeley

This gives us six routes, two for each possible starting point:

Routes 1 and 2 - Starting point Berkeley

Berkeley - > Marin - > San Francisco

Berkeley - > San Francisco - > Marin

Routes 3 and 4 – Starting point Marin

Marin - > San Francisco - > Berkeley

Marin - > Berkeley – San Francisco

Routes 5 and 6 – Starting point San Francisco

San Francisco - > Marin -> Berkeley

San Francisco - > Berkeley -  > Marin

So, with three cities, we get six routes. What about four cities?

We'll add Fremont now and use that as our starting point. How many routes are there?

Once again, we have six routes and they are pretty similar to the previous ones, when we only viisted three cities:

Routes 1 and 2 - Starting point Fremont

Fremont -> Berkeley - > Marin - > San Francisco

Fremont - > Berkeley - > San Francisco - > Marin

Routes 3 and 4 – Starting point Fremont

Fremont - > Marin - > San Francisco - > Berkeley

Fremont - > Marin - > Berkeley – San Francisco

Routes 5 and 6 – Starting point Fremont

Fremont - > San Francisco - > Marin -> Berkeley

Fremont  - > San Francisco - > Berkeley -  > Marin

Can you see the pattern? We added the fourth city and used it as the starting point. That left three cities, and we already know there are six routes for three cities.

You could start at any one of these cities, and each would give you six possible routes. So, four cities x six routes = 24 possible routes.

Whenever you add a new city to the route, the number of routes you must calculate increases. So how many routes do you think there are for six cities?

The answer is an incredible 720 possible routes; with seven cities, it's over 5,000, and more than 40,000 for eight cities. If you had 10 cities, it would produce more than three million possible routes! This is called the factorial function (We discussed it earlier), so 10! = 3,628,800.

You can see that it doesn't take much for the number of possible routes to increase beyond comprehension, and this is why you must computer the right solution for this problem when many cities are involved.

The set-covering and traveling salesperson problems share a common factor – both require you to determine all possible solutions and choose the shortest or smallest one, which means both are NP-complete problems.

All I can say to you at this point is that not all problems are easy to solve; some are famous for being hard, and set-covering and traveling salesperson are just two. Many people don't believe an algorithm could be written to solve these problems satisfactorily.

How To Identify an NP-complete problem

Let's say Jeremy is setting up his fantasy football team and needs to pick some players. He knows what skills and abilities he wants – play well in wet weather, thrives under pressure, good running back, good quarterback, etc. He has made a list of players where each has some skills.

He needs to create a team where all his required skills are fulfilled, but he has a limit on the team size.

This is set-covering, and an approximation algorithm will solve the problem:

Choose a player who covers the most skills that have not yet been covered

Repeat until he has a team with all his required skills, or the team is full.

You will find NP-complete problems everywhere, and it's good to know if this is what you are trying to solve. Once you know that, you can stop trying to find the perfect solution and use approximation instead.

It isn't always easy to tell if a problem is NP-complete with only minimal difference between an easily solvable and NP-complete problem. We talked about shortest path problems earlier, and you now know how to get from A to B in the shortest route.

But what if you needed to connect multiple points and still find the shortest path? Well, that is the traveling salesperson problem, and you know it is NP-complete. In short, there isn't a fool-proof way of telling, but there are a few things that give it away:

                When you only have a few items, the algorithm is quick, but it slows significantly with a larger number

                Every “combination of X” usually tells you it is an NP-complete problem

                If you can't break a problem down into sib-problems and find you have to calculate all  possible versions of X, there's a good chance it's NP-complete

                If there's a hard-to-solve sequence in your problem, like the traveling salesperson, it could be NP-complete

                If there's a hard-to-solve set in your problem, like the radio stations, it could be NP-complete

                If your problem can be restated as a traveling salesperson or set-covering problem, it definitely is NP-complete.

Key Takeaways

Here's what you learned in this chapter:

                Sets are similar to lists but cannot contain duplicated entries

                Sets invite many interesting operations, such as difference, intersect, and union

                We use greedy algorithms to get locally optimal solutions that hopefully end in a globally optimal solution

                There is no quick solution to NP-complete problems – at least not a known one

                If your problem is NP-complete, forget trying for a perfect solution and use approximation algorithms instead

                Greedy algorithms are fast and easy to write, making excellent approximation algorithms.

Chapter 9: Dynamic Programming

In this chapter, you will learn:

Dynamic programming. We use this technique to solve tough problems by splitting them into smaller problems and solving them individually.

How to build a solution, using  plenty of hands-on examples

Let’s go straight back to the knapsack problems we looked at earlier.

You are a shoplifter with a knapsack that holds three items but only has a maximum weight of 4 pounds. What should you steal to ensure you get the most value? Your items are:

A television worth $3,000 and weighing four pounds

A radio worth $2,000 and weighing three pounds

A computer worth $1,500 and weighing 1 pound.

A Simple Answer

The easiest way to do this would be to try all variations to find which set of goods provides the best value. But, although this does work, it is tedious and slow. To steal three items, you have to calculate no less than eight sets; for four items, it would be 16 sets. It doubles the number of sets you must calculate whenever you add an item. This takes an excruciatingly slow O(2^n) time.

This isn’t practical but remembers we looked at approximation algorithms in the previous chapter. If you used approximation, you could get as near to but not exactly the optimal solution.

So, how do we determine the best solution?

Dynamic Programming

So how do you calculate the optimal solution?

Dynamic programming

The answer lies in dynamic programming. The DP algorithm begins by solving smaller sub-problems to solve the entire problem. Using the knapsack problem as the example, the algorithm solves sub-knapsacks first and then works its way up to solving the bigger problem.

Before we go on, I need to tell you that dynamic programming is an advanced concept, and while I will use lots of examples and keep it as simple as I can, you might struggle to grasp it at first – don’t worry; keep going over it, and it will all fall into place.

We’ll start by seeing how the algorithm works; once you’ve seen this, you’ll likely have some questions, but I’ll try to answer them all for you.

All dynamic programming algorithms begin with a grid; no exceptions. Here’s the knapsack problem grid:

| 1 | 2 | 3 | 4
Computer |  |  |  |
Radio |  |  |  |
Television |  |  |  |

It’s pretty simple; four columns denoting the weights from one to four pounds and three rows denoting the items. You might wonder why you need a column for each weight – it’s to help you work out the sub-knapsack values.

So, our grid is empty to begin with, but you will fill every cell; once you have, you will solve the problem.

Make sure to follow this carefully so you understand it:

The Computer Row

Later, we’ll look at the formula to calculate the grid, but first, we’ll walk through it. The first row is the computer row, which indicates you are trying to fit this item into the knapsack. Every cell asks you to make a decision – do you steal the item or not?

Don’t forget; you want to find the right set of items to fill the knapsack and give you the best value.

The first cell in this row shows a capacity of 1 pound in weight. This means it will fit into your knapsack. So, this cell’s value is $1,500, and it is a computer.  Let’s start completing the grid:

| 1 | 2 | 3 | 4
Computer | $1,500 C |  |  |
Television |  |  |  |
Radio |  |  |  |

Each cell will eventually contain a list of the items that can go into the knapsack at any point in time.

The next cell has a capacity of two pounds – again, the computer fits. The same applies to every cell in this row. However, as this is only our first row, we can only choose from one item – the computer. We can go ahead and complete the first row:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television |  |  |  |
Radio |  |  |  |

You might be wondering why we are doing this when the knapsack clearly weighs four pounds. Why do we need to worry about the other weights? I told you earlier that dynamic programming solves smaller sub-problems before solving the main one. We are solving those smaller problems here – it will become clear as you read on, I promise.

Also, we want to maximize the knapsack’s value.

The first row in the grid is our best guess at this stage. So, this tells us that we could place goods to a maximum value of $1,500 in the knapsack. We know that isn’t the end, so our best guess will be refined as we move through the algorithm.

The Television Row

Let's move on to the next row, the one for the television. Now we can bring this item into the equation and, at every point, the items in this row and the one above it can be stolen – nothing below it. So you can choose between the television and the computer or take both.

Let's get to the first cell in this row, with a capacity of a pound. Right now, you can fit a maximum value of $1,500 in the knapsack.

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television |  |  |  |
Radio |  |  |  |

So, should the television be a target?

Your knapsack capacity is one pound, and the television won’t fit – it weighs four pounds. So, the maximum value for a one-pound knapsack remains at $1,500. The same applies to the next two cells, with weights of two and three pounds, respectively.

When we get to the fourth cell, things change. It has a maximum capacity of four pounds, and that’s what the television weighs, so we update the rows on the grid:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio |  |  |  |

The old maximum value was $1,500, but now that has changed to $3,000. As you see, the estimate is gradually refined as you go through each item.

The Radio Row

We’ll do exactly the same for the radio, which weighs three pounds, We know it won't fit in the first two cells, but it will fit the third – the previous estimate for three pounds of space was $1,500, but now that changes to $2,000, the value of the radio.

It’s when we get to the four-pound cell that things get interesting. This is very important – the current best guess for this weight is $3,000, and while you can add the radio, it only has a value of $2,000.

$3,000 television vs. $2,000 radio

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R |

That’s worse than the current estimate, but we need to consider something else – the radio weighs in at three pounds, which leaves you one pound of free space.

$3,000 television vs. ($2,000 radio + one pound of free space)

What was the maximum value you worked out that could go in that space?

Our best guess tells us that the computer will go in that space worth $1,500.  So this is your comparison.

$3,000 television vs. ($2,000 radio + $1,500 computer)

Now you should understand why we have been calculating the maximum values for the smaller knapsacks. When you have got free space, you can look back through the sub-problems to find out what fits. In terms of value for money, the computer and radio, worth a collective $3,500, are better than the television at $3,000.

In the end, the grid looks like this:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C

And that is the answer – the knapsack will take a maximum value of $3,500, comprising two items.

You might think I used something different to work out the last cell, but that’s because I didn’t tell you the full complexity – it wasn’t necessary. What you do need to know is that the values in all cells are calculated using the following formula:

cell[i][j] = max of

Where i indicates the row and j indicates the column, and the remaining space’s value is cell [i-1][j – weight of item]

Frequently Asked Questions

Let me try to answer some of your questions.

You discover a fourth item you can steal – an iPad – what happens if you add it to the list?

Would you need to do all your calculations again? No. That’s the beauty of dynamic programming – it builds your solution progressively. Right now, our maximum values are:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C

So, with a knapsack that takes a maximum of four pounds of weight, you can take $3,500 worth of items. That might have been the final value for now, but that changes when you add a new row.

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C
iPad |  |  |  |

This lets you calculate a new maximum value. Try completing the new row yourself before we move on.

We’ll start at the first cell again. The iPad will fit into a 1-pound knapsack. The previous maximum value for that column was $1,500, but the iPad is worth $2,000 – we’ll take that one.

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C
iPad | $2,000 I |  |  |

The computer and the iPad fit into the two-pound knapsack, and the same for the third cell, as you won’t get any better:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C
iPad | $2,000 I | $3,500 I + C | $3, 500 I + C |

Once again, it’s the final cell where things get interesting. Our current maximum value is $3,500. If you stole the iPad, you would still have three pounds of space worth $2,000. And $2,000 for the iPad and a further $2,000 from the older sub-problem (hint, radio, 3 pounds) makes a new maximum of $4,000.

This is the current new grid:

| 1 | 2 | 3 | 4
Computer | $1,500 C | $1,500 C | $1,500 C | $1,500 C
Television | $1,500 T | $1,500 T | $1,500 T | $3,000 T
Radio | $1,500 R | $1,500 R | $2,000 R | $3,500 R + C
iPad | $2,000 I | $3,500 I + C | $3, 500 I + C | $4, 000 I + R

Is it possible for a column’s value to decrease?

Try to come up with an answer to this before you read the answer.

The answer is no because the current maximum estimate is being stored at every iteration. This means an estimate will never be worse than before; it can only stay the same or increase.

What would happen if the row order were changed?

What do you think? Would the answer be any different? Let’s say your rows are in a different order – television, radio, computer. What would your grid look like? Try to complete it yourself before you look at the answer.

Here’s what it should look like:

| 1 | 2 | 3 | 4
Television | 0 | 0 | 0 | $3,000 T
Radio | 0 | 0 | $2,000 R | $3,000 T
Computer | $1,500 C | $1,500 C | $2,000 R | $3,500 R + C

The answer is nothing would happen; the final estimate stays the same because it doesn’t matter what order the rows are in.

Could the grid be filled in column-wise instead of row-wise?

Again, have a go yourself. In this particular problem, it makes no difference, but it may make a difference with another problem.

If I added a smaller item, what would happen?

Let’s say there’s a bracelet you could steal; it’s worth $1,000 and weighs just half a pound.

Currently, the grid assumes that we only have integers as values. If you opted to put the bracelet in your knapsack, you would have three and a half pounds left over. What is the maximum value that would fit in here?

You cannot answer that question. So far, the only values you have calculated are for 1, 3, 3, and 4-pound knapsacks – three and a half pounds is a floating-point number, not an integer, so you would need to change your grid to something like this:

| 0.5 | 1 | 1.5 | 5 | 2.5 | 3 | 3.5 | 4
Television |  |  |  |  |  |  |  |
Radio |  |  |  |  |  |  |  |
Computer |  |  |  |  |  |  |  |
Bracelet |  |  |  |  |  |  |  |

Can fractions of items be stolen?

Let’s say you are in a grocery store and can steal bags of sugar and rice. If you cannot fit a whole bag in your knapsack, you could open it and take out as much as will fit. So now you can steal fractions of items, but how does dynamic programming handle this?

The answer is it can’t. Dynamic programming requires one of two things – you steal the item, or you don’t; there’s no provision for fractions. However, it’s not all bad news. You can use a greedy algorithm to solve the problem. First, you take the maximum possible amount of the item with the highest value. When that has gone, you do the same with the item with the next highest value, and so on.

Let’s say you have these items:

Saffron - $6 per pound

Amaranth - $3 per pound

Quinoa - $2 per pound

Saffron is the most expensive per pound, so you take as much as you can carry. If you can fill your knapsack, all well and good – that’s your best answer. However, if you take all the saffron and still have room, you take amaranth. If taking all the amaranth doesn’t fill up the knapsack, you take the quinoa, and so on until your knapsack is full.

How to optimize a travel itinerary

Let’s say you are heading off on vacation to London. You’ve only got two days in the city and many things you want to do. How do you work out what you can fit in?

First, you list everything you want to do, how much time it will take, and rate it based on how badly you want to do it. It would look like this:

Using this list, work out what you have time to do.

This is the same as the knapsack problem, only this time, you have a set amount of time rather than space in a knapsack. And rather than items to steal, you have places to visit. See if you can draw the grid before I show you the answer.

The grid should look something like this:

| ½ | 1 | 1 ½ | 2
Tower of London |  |  |  |
Buckingham Palace |  |  |  |
London Eye |  |  |  |
Madame Tussauds |  |  |  |
The Shard |  |  |  |

Were you right?

Now try filling the grid in to work out what you can fit in?

It should look like this:

| ½ | 1 | 1 ½ | 2
Tower of London | 7 T | 7 T | 7 T | 7 T
Buckingham Palace | 7 T | 13 T + B | 13 T + B | 13 T + B
London Eye | 7 T | 13 T + B | 16 T + L | 22 T + B + L
Madame Tussauds | 7 T | 13 T + B | 16 T + L | 22 T + B + L
Shard | 8 S | 15 T + S | 21 T + B + S | 24 T + L + S

How do you handle items that are dependent on each other?

Let’s say you wanted to add Paris to your travel itinerary, so you add some items to your travel list:

This will take time because you must first travel to Paris from London, which is a half-day trip. If you wanted to do it all, it would take you four and a half days. Wouldn’t it?

Well, no. You only need to travel to Paris once, so each of your places should only take a day; that brings it down to three and a half days – half a day to travel and three days to see everything.

If you placed the Eiffel tower into your travel “knapsack,” Versailles would decrease in time – it will only take a day. How can this be modeled in dynamic programming?

It can’t. While dynamic programming is powerful, solving sub-problems to solve the original problem, it can only work with discrete sub-problems. This means they are not dependent on other sub-problems, so we cannot use dynamic programming to solve the Paris problem.

Could it be that we need three or more sub-knapsacks to solve it?

The best solution may well require more than two items. The algorithm is set up to combine no more than two sub-knapsacks, but they can both have their own sub-knapsacks.

Could it be that the best solution cannot completely fill the knapsack?

Yes. Let’s say you also had an emerald you could steal. It’s a big one, weighing three and a half pounds, and its value is a million dollars. That beats everything else, so it’s a no-brainer to put it in your knapsack. However, it leaves half a pound of space, and there is nothing else that will go in that space.

Longest Common Substring

It isn’t always easy to devise a solution to a dynamic programming problem, so this section will look at this. First, a few general tips:

No matter what the dynamic programming problem is, the solution will always include a grid

Typically, you want to optimize the cell values

In the knapsack problem, those values were the values associated with the goods.

All cells in the grid are a separate sub-problem, so you need to consider how the overall problem can be divided into those sub-problems. This will help you determine your axes.

Here’s another example. Let’s say you own dictionary.com. A person types a word in, and you provide them with the definition.

But what if the word is spelled wrongly? You need to be able to guess the word they want. Let’s say Johnny wants the word ‘hash’ but instead types in ‘pash’ by accident. 

That word does not exist in your dictionary, but there is a list of similar words. This list would potentially be thousands of words long in the real world, but it will only be two for this example.

So, Johnny types ‘pash,’ but what word did he want? ‘Hash’ or ‘hasta?’

The Grid:

What would the gird look like? To answer that, three questions need answering:

What values go in the cells?

How can this be split into sub-problems?

What are the grid axes?

Dynamic problems require you to maximize something, and, in this example, you want the longest substring in common between two words? What is the substring shared by “pash” and “hasta?”

Remember, you want to optimize the cell’s values, which will likely be numbers in this case – the length of the longest substring in common between the two words.

How can we split this into sub-problems? We could compare the substrings. For example, instead of trying to compare ‘hash’ and ‘pash,’ you could compare ‘has’ and ‘pas.’ Each cell’s value is the longest common substring’s length, and this also helps you determine the axes – in this case, the axes are the two words. So, your grid would look like this:

| H | A | S | H
P |  |  |  |
A |  |  |  |
S |  |  |  |
H |  |  |  |

Now, this isn’t the easiest to grasp, which is why it is near the end of this book.

Completing the Grid

So, what formula do we use to complete each cell? You already know the solution to this because ‘hash’ and ‘pash’ both share a common substring of length 3 – ‘ash.’

But that doesn’t tell you what formula you need to use. You might hear data scientists joking about the Feynman algorithm, named after a famous physicist. That algorithm works like this:

Write the problem

Think about it really, really hard

Write the solution

Aren’t data scientists fun!

In reality, the formula for this problem isn’t all that easy to calculate. You need to experiment and find what works. Think of algorithms as recipes – sometimes, you need to tweak things a little rather than following them exactly. Think of them as frameworks, something you can build on.

Have a go at finding the solution yourself. I’ll help you a little – this is what part of the grid will look like:

| H | A | S | H
P | 0 | 0 |  |
A |  |  |  |
S |  |  | 2 | 0
H |  |  |  | 3

What values should be in the other cells? Keep in mind that every cell is a sub-problem’s value. Why do the cells in the above grid have those values?

Once you’ve had a go yourself, read on. It doesn’t matter if you get it wrong – what’s important is trying.

The Solution

This is what the final grid looks like:

| H | A | S | H
P | 0 | 0 | 0 | 0
A | 0 | 1 | 0 | 0
S | 0 | 0 | 2 | 0
H | 0 | 0 | 0 | 3

The formula I used to complete each cell is:

If the letters do not match, the value is 0

If the letters do match, the value is the neighbor at the top left of the cell plus 1

In pseudocode, it looks like this:

if word_a[i] == word_b[j]:

cell[i][j] = cell[i-1][j-1] + 1

else:

cell[i][j] = 0

Okay, now we have two choices for the word. Johnny inputs ‘pash’ – does he mean ‘hasta’ instead? Here’s the ‘pash’ vs. ‘hasta’ grid:

| H | A | S | T | A
P | 0 | 1 | 1 | 0 | 0
A | 0 | 1 | 0 | 0 | 1
S | 0 | 0 | 2 | 0 | 0
H | 0 | 0 | 0 | 0 | 0

You need to be aware that the last cell may not always be the final solution in dynamic programming like it is in the knapsack problem. In the longest common substring problem, the final solution is the biggest number, no matter where it is in the grid.

Back to the original problem – which string shares the longest common substring with ‘pash?’ ‘Pash’ and ‘hash’ both share a substring of 3, but “pash’ and ‘hasta’ only share a substring of 2.

Johnny probably wanted to type ‘hash.’

Longest Common Subsequence

Now let’s say that Johnny types ‘host’ by mistake. Did he mean ‘hash’ or ‘host?’

We can use the substring formula from above to compare the words.

| H | O | S | H
H | 1 | 0 | 0 | 0
A | 0 | 0 | 0 | 0
S | 0 | 0 | 1 | 0
H | 1 | 0 | 0 | 2

| H | O | S | H
H | 1 | 0 | 0 | 1
O | 0 | 1 | 0 | 0
S | 0 | 0 | 2 | 0
T | 0 | 0 | 0 | 0

And they both share a common longest common substring of 2, but ‘hosh’ is closer to ‘hash.’

Here, you are comparing the substrings but what you should be comparing is the longest common subsequence. This tells us how many sequential letters two words have in common. How is this calculated?

Here’s part of the grid for “hash and ‘hosh.’

| H | O | S | H
H | 1 | 1 |  |
O | 1 |  |  |
S |  | 1 | 2 | 2
T |  |  |  |

So, what is the formula?

The longest common subsequence and substring are similar, as are the formulas. Have a go at solving it before I tell you the answer.

Solution

This is the final grid:

| H | O | S | H
H | 1 | 1 | 1 | 1
A | 1 | 1 | 1 | 1
S | 1 | 1 | 2 | 1
H | 2 | 1 | 1 | 4

| H | O | S | H
H | 1 | 1 | 1 | 1
O | 1 | 2 | 1 | 1
S | 1 | 1 | 4 | 1
T | 1 | 1 | 1 | 1

The formula here is:

Where there is no match, choose the largest top-left neighbor

Where there is a match, use the top-left neighbor’s value plus one

And this is the pseudocode:

if word_a[i] == word_b[j]:

cell[i][j] = cell[i-1][j-1] + 1

else:

cell[i][j] = max(cell[i-1][j], cell[i][j-1])

This is a tough subject, but how often is it used?

Biologists use the longest common subsequence to look at DNA strands and find similarities. This allows them to tell us the similarities between diseases, animals, etc. Right now, this is being used to try to cure MS.

Think about whether you have ever used ‘diff.’ This lets you know if two files differ in any way, and this is done using dynamic programming.

We also mentioned string similarity. Dynamic programming is used in the Levenshtein distance to measure the similarities between strings. Levenshtein distance is popularly used in spell checking, checking whether a person is misusing copyrighted data, and so on

Have you ever used word wrap in MS Word or similar problems? Dynamic programming helps it work to find the right place to wrap a word, ensuring consistency in the line length.

Key Takeaways

Here’s what you learned in this chapter:

Dynamic programming works well to optimize something that has constraints

It works to solve sub-problems where the original problem can be split down

All dynamic programming solutions will have a grid

It typically involves optimizing the cell’s values

Every cell is an individual sub-problem, so you need to consider if and how your problem can be divided

Dynamic programming solutions cannot be calculated using a set formula.

Chapter 10: Who’s your KNN?

Here’s what you will learn in this chapter:

How to use KNN to build a classification system

What feature extraction is

What regression is – number prediction, such as future stock values, or whether a user will enjoy a movie

About KNN’s limitations and use-cases

Let’s dive straight into this one.

Classification: Lemons vs. Limes

Classifying lemons vs. limes

Do you know the difference between a lemon and a lime? They both look similar in some ways but different in others. Here’s how I think of it.

In my mind, I have a graph. The larger, yellow fruits are lemons, while the smaller green fruits are limes. Imagine that the color axis runs from green at the bottom to yellow at the top, and the size axis runs from small to large. In this graph, limes are on the bottom-left, while lemons are top-right.

But what if you get a fruit that’s somewhere in between the two? How do you classify it?

One of the easiest ways to do this is to examine the fruit’s neighbors.

000

COLOR00

0000

0                    

000

0000

Strange fruit

SIZE

Look at this fruit’s three nearest neighbors. More are lemons than limes, so the fruit is most likely a lemon.

That is KNN or k-nearest neighbors in action, the popular classification algorithm. This is one of the simplest and most useful of all classification algorithms, so let’s see it in use in a real example.

How to Build a Recommendation System

Let’s say you own a movie streaming business and want to give your customers a recommendation system similar to those on Netflix, Amazon, etc. This is similar to the lemons and limes problem.

All your users can be plotted on one graph by similarity; those with similar movie tastes are all plotted together.

So, we have six users:

Johnny

Joe

Sally

Michelle

Usaf

Lorraine

We want to recommend a few movies for Johnny, so we need to find the five users near him. Joe, Sally, Michelle, Usaf, and Lorraine all have similar movie tastes, so Johnny will likely watch the movies they watch. Try to draw the graph that would show the five closest neighbors to Johnny.

Once the graph is built, it is simple to build a recommendations system.

If Sally like a movie, you can recommend it to Johnny.

But something is missing. The users were graphed by similarity, but how do we know the similarities between users?

Feature Extraction

In the fruit example, lemons and limes were compared based on their size and color – those are the features for comparison. Let’s add a third fruit to the equation:

________________________________________________________

Size     2   3  4

Yellow     1   2  4

The features can be extracted and the fruit added to a graph:

C

COLOR

B

A

SIZE

You can see that fruits A and B are close in size, but C is much bigger. We want to measure how close A and B are, and the best way to do that is with the Pythagorean formula.

This formula can be used to tell us how close (or far) A and B are:

1

So, here you can see a distance of 1 between A and B, and, using that formula, you can find all the other distances. This also confirms what the graph showed you visually – A and B are similar to one another.

So, let’s say we are looking at Netflix users instead. First, the users must go on a graph, meaning each one must be converted to a set of coordinates – we did this with the fruit example.

Once the users have been put on the graph, you can measure the distances between each one.

Let’s see how users are converted into sets of numbers.

When a user opens a Netflix account, they must rate movie categories based on their like or dislike of a category. Now you have some ratings for each user.

| Johnny | Joe | Michael
Comedy | 3 | 4 | 2
Action | 4 | 3 | 5
Drama | 4 | 5 | 1
Horror | 1 | 1 | 3
Romance | 4 | 5 | 1

You can see from this that Johnny and Joe are fans of Romance movies but not Horror, while Michel loves Action films but can’t stand Romance films. In our lemons and limes problems, the fruits were each represented by a set of coordinates, each with two numbers. In this problem, there are five numbers.

Fruit -> (2, 2)

Netflix users -> (3, 4, 4, 1, 4)

While a mathematician would tell you that your distance is now calculated in five dimensions rather than two, it doesn’t change the formula – you just use sets of five numbers rather than two.

The Pythagorean distance formula is relatively flexible – your sets could have thousands of numbers, and it would still work.

So, your next question is likely to be, what is distance in terms of these five numbers? What does it mean? The distance lets you know the similarity between the sets.

The distance separating Johnny and Joe is:

(3-4)2 + (4 – 3)2 + (4 – 5)2 + (1 -1)2 +(4 – 5)2

=

=

= 2

As you can see, there are significant similarities between Johnny and Joe, but what about Johnny and Michael? Try to work that out before you carry on.

If you got an answer of 24, you were right. This tells you that Johnny’s tastes are more similar to Joe’s than Michael’s.

That means we can easily recommend good movies for Johnny to watch; if Joe enjoys a movie, it can be recommended for Johnny and vice versa.

That is a recommendation system in a nutshell.

Netflix users are often asked to continue rating movies, thus ensuring their personal recommendations are better – the more movies they rate, the easier it is for Netflix to see the similarities between users.

Regression

What if you wanted more than a recommendation system? What if you wanted to guess a user would rate a movie? To do that, you would take the 5 nearest people to her. As an aside, the number 5 is unimportant – it could be any number of nearest people. This is why the algorithm is k-nearest neighbors – the k represents any number.

Let’s say you want to guess the rating for Titanic? Let’s see how Joe, Sally, Michelle, Usaf, and Lorraine rated it:

Joe: 5

Sally: 4

Michelle: 4

Usaf: 5

Lorraine: 3

If we averaged their ratings, we would get a rating of 4.2.

This is known as regression – with KNN, you do two main things – classification and regression:

Classification - categorizing things/people into groups

Regression – predicting responses

Regression is incredibly useful. Let’s say you own a bakery and need to bake fresh bread rolls daily. You need to predict how many to make per day, and you have certain features you can use:

The weather rated 1 to 5 – 1 = bad weather, 5 = excellent weather

Is it a weekend? Or holiday? If yes, 1, if no, 0

Is there a big game on the television? If yes, 1, if no, o

You also know how many rolls you have sold previously for these and other features.

A: (5, 1, 0) = 300 rolls

B: (3, 1, 1) = 225 rolls

C: (1, 1, 0) = 75 rolls

D: (4, 0, 1) = 200 rolls

E: (4, 0, 0) = 150 rolls

F: (2, 0, 0) =  50 rolls

Today is a Saturday, and the weather is excellent. Based on your data, predict how many rolls you will sell.

We’ll use KNN for this, where K = 4. First, you need to work out the four nearest neighbors.

(4, 1, 0) = ?

So, the distances are below, and we can see that the four nearest are A, B, D, and E:

A: 1 <-

B: 2 <-

C: 9

D: 2 <-

E: 1 <-

F: 5

If you average out the rolls you sold on those 4 days, which equals 218.75 – that is the number of rolls you need to bake today.

Picking Good Features

We needed our users to rate movie categories to work out what movies to recommend. What if we asked them to rate images of dogs? Then we would see all those users who gave the images similar ratings, but this would not give you the information you want – the features in the dog images have nothing to do with the type of movies a user likes.

Or you could ask them to rate movies but only ask them to rate the Harry Potter movies. That isn't going to tell you much about their taste, either.

When you use KNN, you must choose the right features for comparison, and that means:

Choosing features with a direct correlation to the movies you want to recommend

Choosing features with no bias, i.e., asking users to only rate kids' movies, doesn't tell you whether they like any other movie category

What do you think of recommendation systems? Let's say you rated one Netflix series higher than another, but you watch the lower-rated one more. Can you improve on this system?

And your bakery. Think about a couple of good and a couple of bad features you could have picked. Perhaps you need to bake more rolls on a Tuesday, or you get a flurry of orders the day after a newspaper ad. How can you improve this system?

There isn't a one-size-fits-all approach to choosing good features; it's down to you to determine the best ones by considering everything that affects the calculations.

Introduction to Machine Learning

KNN is one of the most useful algorithms there is, and it opens the door to the world of machine learning, a way to make your computer work more intelligently. We've seen one example already – the recommendation system – but there are some other examples you should know about.

OCR

This stands for Optical Character Recognition and means having the ability to photograph some text and have your computer read it. This system is used a great deal in digitizing books, but how does it work?

Consider the number below:

9

If this were a handwritten character scanned into a computer, how would you figure out what it was? That's where KNN comes in:

Go through multiple images of numbers, extracting each one's features

When a new image appears, extract its features and look for its nearest neighbors

This is similar to the lemons and limes problem. In simple terms, OCR algorithms are used to measure curves, lines, and points. When a new character is presented, the features can be extracted.

It's worth bearing in mind that it's far harder to extract features in OCR than in our fruit example. However, you also need to consider that even the most complex technology can be used to build on the simplest of ideas – KNN is the most common example of this.

The same ideas could be used in facial and speech recognition. Think about when you upload some photos to Facebook; sometimes, Facebook can automatically tag certain people in the images – that's machine learning at work.

The first step in OCR is called training, where the algorithm examines the images and extracts the features. Almost every machine learning algorithm has this first step – like a person starting a brand new job, the computer needs to be trained before it can do the job.

In the next example, we'll look at spam filters. They, too, have a training step.

Spam Filters

Another common use is the spam filter, which uses a very simple algorithm – the Naïve Bayes classifier. First, this classifier must be trained on certain data.

Let's say you receive an email with a subject line telling you that you've won a million dollars. Is this a spam email?

First, the sentence in the subject line should be broken down into its individual words. Then, each word is examined to determine the probability of it appearing in a spam email. For the purposes of this example, the word “million” will only appear in emails classified as spam. The Naïve Bayes classifier determines the probability of something being spam and is applied similarly to KNN.

For example, Naïve Bayes could be used in fruit classification problems – you have a large, yellow, oval fruit; what is the probability of it being a lemon?

It is another very simple but effective algorithm.

Stock Market Predictions

Predicting whether stock prices will go up or down is not easy using machine learning. How do you choose good features? If the stock market rose yesterday, it rises today – is that a good feature? What about if you said the market always drops in February? Would that be a good feature? There is no guarantee that using past numbers will help you predict performance in the future. Far too many variables are in place to predict the future with any certainty.

Key Takeaways

I hope you now know what you can and can't do with KNN and machine learning. Here's what you learned in this chapter:

KNN is a classification and regression algorithm that looks at the k-nearest neighbors

Classification is about categorizing things or people into groups

Regression is about predicting responses

Feature extraction is about converting items into coordinates – lists of numbers – that we can compare

One of the most important parts of KNN being successful is choosing the right features.

Chapter 11: The Best Way to Learn Algorithms

You already know that you should learn data structures and algorithms but do you wonder why? The answer is simple – master these, and you can use them to understand and solve problems in the real world. For example, let's say you are a web developer; during your design work, you might need to use a binary tree to find the hierarchy in your web pages.

So, how best do you learn these algorithms? I've shown you some easy ways to understand them, but you need a plan to ensure you learn conveniently and efficiently:

Find the Best Resources

We live in a digital world, and most of us live our lives on the internet – that's your best starting point. There are many free and paid online courses and plenty of tutorials, lectures, videos, books, and more. The sheer amount makes it tough to find the material you want.

Not knowing what you are looking for means you will often come across poor materials that don't really help you learn efficiently or will teach you incorrectly. Instead of piquing your interest and enthusiasm, they do the opposite.

Make sure you find the most reliable platforms to learn from – GitHub is one of the best places to start. One of the best ways to learn is to practice – find a platform that encourages you and lets you repeatedly practice until you grasp what you need to learn.

Make Sure You Have a Thorough Understanding of the Fundamentals

If you were asked to write an article entirely in German, could you do it? Sure, if you were a native German speaker, but if you don't know any German, you wouldn't be able to do it.

That's the case with algorithms and data structures. If you don't know or understand the fundamentals, you cannot even begin to start solving problems. Once you have found the right resources to learn from, start at the beginning:

Learn the uses of each algorithm and data structure, how to use them, and implement them all using your choice of programming language

Acquire a deep understanding of how they all work – this way, you can build your foundations

Learn how data structures should be restructured according to the use case

Understand time and space complexity

Start by coding on a whiteboard or pen and paper – this will help you learn better and will help you in coding interviews later down the line

These are the basic algorithms and data structures you need to grasp:

Array

Strings

Tuple and Sets

Lists and Two-Dimensional Lists

HashMap and HashTable

Linked Lists

Stack and Queues

Recursion

Trees

Priority Queues

Graphs

Dynamic Programming

Trie

Once you understand these, you can move on to more complex structures.

Increase Your Abilities in Solving Problems

How many problems do you need to solve successfully before you can say you understand data structures? How much time should you spend on a problem? All I can say to you here is this – quality first. It doesn't matter how much you do; if none of it works, it's wasted time.

Choose a simple data structure and work on solving a dozen simple problems using it. Then move on to medium problems. You move on to hard problems only when you have done that and have a great understanding of the structure.

It doesn't really matter how many problems you solve – the important part is leveling up from easy to medium to hard. Some days you will find the problems easy; other days, you will struggle. If you do, don't worry. Work on a problem for no more than two hours at a  time. If you get it, great. If not, try again.

Never lose hope. Even professional coders get stuck on problems!

Space Your Repetitions

You might have solved many different problems, but when someone asks you to solve one of them again, you struggle. You have problems remembering what you've done, so how will you ever get on?

I'll be honest with you. Some people will tell you just to keep reading and solving problems, but it won't work. The human brain has a limited learning capacity – after a while, no more will sink in, and you risk forgetting everything you already learned.

The key to learning revolves around practicing and spacing out your repetition. The latter is a memory method that requires you to review concepts and recall them at intervals until you have learned them fully.

The ideal interval is four days. Then you move to 10 days and then a month. In time, you will fall into the habit of revising at set intervals

Keep Practicing

To move from being good at data structures and algorithms to be one of the best, you have to practice. So, once you've been learning for a couple of months, you should begin practicing what you learned. You need to practice a lot – not just easy problems but intermediate and hard ones too.

Try to find an interactive website where you have virtually unlimited practice questions to help you practice and offer the chance to enter coding contests. These contests are one of the best ways to challenge yourself and improve.

Spot the Patterns

You will start spotting patterns when you have been solving problems for a while. Throughout this book, you have seen a lot of problems, and solving even more will help compound what you learned; most of the problems you will go on to solve will be similar to or combinations of other problems you have already solved. You will start to see patterns in the code and the logic and how you can reuse certain things, depending on the use case.

The best thing to do is keep your common code isolated from the rest and get plenty of practice on it. Why? Because there are plenty of benefits to isolating reused techniques and practicing them:

You will learn to code those techniques easily and in one hit. This shows you have a good grasp of data structures and how to implement them.

You can code the techniques without risking compile or runtime errors.

You will know how the code can be restructured to fit new problems

At the end of the day, no one method or technique for learning will suit everyone. Follow the tips I've set out above, and you will honestly be able to say that you understand data structures and algorithms because:

You understand the fundamentals

You understand each structure's core implementation and method calls

You'll have worked on several hundred problems by now, all varying in difficulty level

You've learned the habit of spaced repetition

You know the common codes that you can reuse for different problems

Conclusion

Well done for making it to the end of my book. I hope you enjoyed it and found it useful.

Algorithms aren't always easy to understand, and some books make them seem downright complicated. I've tried to make them easy for you to understand and enjoyable to learn. I've used real-world examples to explain some of them, giving you a foolproof way of understanding exactly how they work and what they are for – that way, you'll know exactly which algorithm to use in whatever problem you are trying to solve.

Here's a recap of what you learned:

Chapter 1 introduced you to algorithms and binary search, with a discussion of time and space complexity and the Big O notation.

Chapter 2 looked at the Selection Sort algorithm, linked lists, and arrays, while chapter 3 discussed recursion and call stacks.

In chapter 4 we dived into the Quicksort algorithm and learned how divide and conquer works.

Chapter 5 examined the subject of hash tables and discussed implementation, collisions, and hash functions so you can understand their performance.

In chapter 6, we examined the breadth-first search algorithm and how it works to find the shortest path in a graph, before moving on to the most common shortest path algorithm in chapter 7 – Dijkstra’s algorithm.

Chapter 7 looked at how Dijkstra’s algorithm works, what you can and can’t use it for – it won’t work on graphs with negative weights,) and we also looked at the breadth-first search.

Chapter 8 discussed greedy algorithms and NP-complete problems, including how to identify NP-complete problems and how to solve them – when a standard algorithm simply doesn’t work, greedy and approximation algorithms can do the trick.

Chapter 9 delved into dynamic programming, and how to solve difficult problems by using a grid to break a problem into smaller problems. Once the smaller problems are solved, the solution to the original problem becomes clearer.

Chapter 10 talked about the KNN (K-Nearest Neighbors) algorithm and how to build classification systems using it. You learned about feature extraction and solving prediction problems using regression. You also got a brief introduction to machine learning.

There is much more to algorithms than what was covered here, but you now have a great understanding of the major ones and should be excited enough to go out and discover more.

I wish you all the success and luck in the world on your data science journey.

Thank you for buying and reading/listening to our book. If you found this book useful/helpful please take a few minutes and leave a review on Amazon.com or Audible.com (if you bought the audio version).

References

“Basics of Greedy Algorithms Tutorials & Notes | Algorithms | HackerEarth.” 2016. HackerEarth. 2016. https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/.

“Basics of Hash Tables Tutorials & Notes | Data Structures | HackerEarth.” 2016. HackerEarth. 2016. https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/.

Baum, Johannes. 2020. “5 Ways to Find the Shortest Path in a Graph.” Medium. December 3, 2020. https://betterprogramming.pub/5-ways-to-find-the-shortest-path-in-a-graph-88cfefd0030f.

Brownlee, Jason. 2020. “4 Types of Classification Tasks in Machine Learning.” Machine Learning Mastery. April 7, 2020. https://machinelearningmastery.com/types-of-classification-in-machine-learning/.

“Demystifying Dynamic Programming.” 2017. FreeCodeCamp.org. July 31, 2017. https://www.freecodecamp.org/news/demystifying-dynamic-programming-3efafb8d4296/.

GeeksforGeeks. 2017. “Searching Algorithms - GeeksforGeeks.” GeeksforGeeks. 2017. https://www.geeksforgeeks.org/searching-algorithms/.

“Greedy Algorithm with Examples.” 2020. Guru99.com. February 6, 2020. https://www.guru99.com/greedy-algorithm.html.

“Greedy Algorithms Introduction - Javatpoint.” n.d. Www.javatpoint.com. https://www.javatpoint.com/greedy-algorithms.

Gustin, Eric. 2020. “The Four Sorting Algorithms You Need to Know.” Medium. July 18, 2020. https://ericgustin.medium.com/the-four-sorting-algorithms-you-need-to-know-9dd14f6ba13b.

“Let Us Understand Searching Algorithms -.” 2020. August 5, 2020. https://codersera.com/blog/let-us-understand-searching-algorithms/.

Nilanjan. 2021. “Recursion for Dummies.” Medium. August 8, 2021. https://levelup.gitconnected.com/recursion-for-dummies-bb66f0e60a9e.

Sharma, Abhishek. 2020. “Decision Tree vs. Random Forest - Which Algorithm Should You Use?” Analytics Vidhya. May 11, 2020. https://www.analyticsvidhya.com/blog/2020/05/decision-tree-vs-random-forest-algorithm/.

“Sorting Algorithms Explained with Examples in Python, Java, and C++.” 2019. FreeCodeCamp.org. December 4, 2019. https://www.freecodecamp.org/news/sorting-algorithms-explained-with-examples-in-python-java-and-c/.

“Time Complexity and Space Complexity.” 2021. GeeksforGeeks. July 11, 2021. https://www.geeksforgeeks.org/time-complexity-and-space-complexity/.

“What Is an Algorithm? Definition, Types, Complexity, Examples.” 2021. GeeksforGeeks. October 17, 2021. https://www.geeksforgeeks.org/what-is-an-algorithm-definition-types-complexity-examples/.

Zhang, Ramy. 2018. “Data Structures for Dummies: Hash Tables.” Medium. July 6, 2018. https://medium.com/@ramyjzh/data-structures-for-dummies-hash-tables-579ddd1a4389.