Grokking Algorithms

grokking algorithms

grokking algorithms

An illustrated guide for programmers and other curious people

Aditya Y. Bhargava

Audio by Paper2Audio.

For online information and ordering of this and other Manning books, please visit manning dot com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact

Special Sales Department

Manning Publications Co.

20 Baldwin Road, P.O Box 761

Shelter Island, N.Y 11964

Email: orders@manning.com 2016 by Manning Publications Co. All rights reserved.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher.

Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps.

Recognizing the importance of preserving what has been written, it is Manning's policy to have the books we publish printed on acid-free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine.

Manning Publications Co.

20 Baldwin Road

Shelter Island, N.Y 11964

Development editor: Jennifer Stout

Technical development editor: Damien White

Project manager: Tiffany Taylor

Copyeditor: Tiffany Taylor

Technical proofreader: Jean-Francois Morin

Typesetter: Leslie Haimes

Cover and interior design: Leslie Haimes

Illustrations by the author

I.S.B.N: 9781617292231

Printed in the United States of America

1 2 3 4 5 6 7 8 9 10 – E.B.M – 21 20 19 18 17 16 For my parents, Sangeeta and Yogesh

preface

I first got into programming as a hobby. Visual Basic 6 for Dummies taught me the basics, and I kept reading books to learn more. But the subject of algorithms was impenetrable for me. I remember savoring the table of contents of my first algorithms book, thinking "I'm finally going to understand these topics!" But it was dense stuff, and I gave up after a few weeks. It wasn't until I had my first good algorithms professor that I realized how simple and elegant these ideas were.

A few years ago, I wrote my first illustrated blog post. I'm a visual learner, and I really liked the illustrated style. Since then, I've written a few illustrated posts on functional programming, Git, machine learning, and concurrency.

By the way: I was a mediocre writer when I started out. Explaining technical concepts is hard. Coming up with good examples takes time, and explaining a difficult concept takes time. So it's easiest to gloss over the hard stuff.

I thought I was doing a pretty good job, until after one of my posts got popular, a coworker came up to me and said, "I read your post and I still don't understand this." I still had a lot to learn about writing.

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

Kudos to Manning for giving me the chance to write this book and letting me have a lot of creative freedom with it. Thanks to publisher Marjan Bace, Mike Stephens for getting me on board, Bert Bates for teaching me how to write, and Jennifer Stout for being an incredibly responsive and helpful editor. Thanks also to the people on Manning's production team: Kevin Sullivan, Mary Piergies, Tiffany Taylor, Leslie Haimes, and all the others behind the scenes. In addition, I want to thank the many people who read the manuscript and offered suggestions: Kayren Bensdon, Rob Green, Michael Hamrah, Ozren Harlovic, Colin Hastie, Christopher Haupt, Chuck Henderson, Pawel Kozlowski, Amit Lamba, Jean-Francois Morin, Robert Morrison, Sankar Ramanathan, Sander Rossel, Doug Sparling, and Damien White.

Thanks to the people who helped me reach this point: the folks on the Flaskhit game board, for teaching me how to code; the many friends who helped by reviewing chapters, giving advice, and letting me try out different explanations, including Ben Vinegar, Karl Puzon, Alex Manning, Esther Chan, Anish Bhatt, Michael Glass, Nikrad Mahdi, Charles Lee, Jared Friedman, Hema Manickavasagam, Hari Raja, Murali Gudipati, Srinivas Varadan, and others; and Gerry Brady, for teaching me algorithms. Another big thank you to algorithms academics like C.L.R.S, Knuth, and Strang. I'm truly standing on the shoulders of giants.

Dad, Mom, Priyanka, and the rest of the family: thank you for your constant support. And a big thank you to my wife Maggie. There are many adventures ahead of us, and some of them don't involve staying inside on a Friday night rewriting paragraphs.

Finally, a big thank you to all the readers who took a chance on this book, and the readers who gave me feedback in the book's forum. You really helped make this book better.

about this book

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

I lead with examples. Instead of writing symbol soup, my goal is to make it easy for you to visualize these concepts. I also think we learn best by being able to recall something we already know, and examples make recall easier.

So when you're trying to remember the difference between arrays and linked lists (explained in chapter 2), you can just think about getting seated for a movie. Also, at the risk of stating the obvious, I'm a visual learner. This book is chock-full of images.

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

Roadmap

The first three chapters of this book lay the foundations:

• Chapter 1 You'll learn your first practical algorithm: binary search. You also learn to analyze the speed of an algorithm using Big O notation. Big O notation is used throughout the book to analyze how slow or fast an algorithm is.

• Chapter 2 You'll learn about two fundamental data structures: arrays and linked lists. These data structures are used throughout the book, and they're used to make more advanced data structures like hash tables (chapter 5).

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

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

The rest of the book presents algorithms with broad applications:

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

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

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

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

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

How to use this book

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

I strongly recommend executing the code for the examples yourself. I can't stress this part enough. Just type out my code samples verbatim (or download them from manning dot com U.R.L or github dot com U.R.L), and execute them. You'll retain a lot more if you do.

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

Who should read this book

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

• Hobbyist coders

• Coding boot camp students

- Computer science grads looking for a refresher

• Physics/math/other grads who are interested in programming

Code conventions and downloads

All the code examples in this book use Python 2.7. All code in the book is presented in a fixed-width font like this to separate it from ordinary text. Code annotations accompany some of the listings, highlighting important concepts.

You can download the code for the examples in the book from the publisher's website at manning dot com U.R.L or from github dot com U.R.L.

I believe you learn best when you really enjoy learning—so have fun, and run the code samples!

About the author

Author Online

Purchase of Grokking Algorithms includes free access to a private web forum run by Manning Publications where you can make comments about the book, ask technical questions, and receive help from the author and from other users. To access the forum and subscribe to it, point your web browser to manning dot com U.R.L. This page provides information on how to get on the forum once you are registered, what kind of help is available, and the rules of conduct on the forum.

Manning's commitment to our readers is to provide a venue where a meaningful dialog between individual readers and between readers and the author can take place. It isn't a commitment to any specific amount of participation on the part of the author, whose contribution to Author Online remains voluntary (and unpaid). We suggest you try asking the author some challenging questions lest his interest stray! The Author Online forum and the archives of previous discussions will be accessible from the publisher's website as long as the book is in print.

In this chapter

- You get a foundation for the rest of the book.

- You write your first search algorithm (binary search).

- You learn how to talk about the running time of an algorithm (Big O notation).

- You're introduced to a common technique for designing algorithms (recursion).

Introduction

An algorithm is a set of instructions for accomplishing a task. Every piece of code could be called an algorithm, but this book covers the more interesting bits. I chose the algorithms in this book for inclusion because they're fast, or they solve interesting problems, or both. Here are some highlights:

- Chapter 1 talks about binary search and shows how an algorithm can speed up your code. In one example, the number of steps needed goes from 4 billion down to 32!

- A G.P.S device uses graph algorithms (as you'll learn in chapters 6, 7, and 8) to calculate the shortest route to your destination.

• You can use dynamic programming (discussed in chapter 9) to write an A.I algorithm that plays checkers.

In each case, I'll describe the algorithm and give you an example. Then I'll talk about the running time of the algorithm in Big O notation. Finally, I'll explore what other types of problems could be solved by the same algorithm.

What you'll learn about performance

The good news is, an implementation of every algorithm in this book is probably available in your favorite language, so you don't have to write each algorithm yourself! But those implementations are useless if you don't understand the trade-offs. In this book, you'll learn to compare trade-offs between different algorithms: Should you use merge sort or quicksort? Should you use an array or a list? Just using a different data structure can make a big difference.

What you'll learn about solving problems

You'll learn techniques for solving problems that might have been out of your grasp until now. For example:

• If you like making video games, you can write an A.I system that follows the user around using graph algorithms.

• You'll learn to make a recommendations system using k-nearest neighbors.

• Some problems aren't solvable in a timely manner! The part of this book that talks about N.P-complete problems shows you how to identify those problems and come up with an algorithm that gives you an approximate answer.

More generally, by the end of this book, you'll know some of the most widely applicable algorithms. You can then use your new knowledge to learn about more specific algorithms for A.I, databases, and so on. Or you can take on bigger challenges at work.

You'll need to know basic algebra before starting this book. In particular, take this function: f of x equals x times 2. What is f of 5? If you answered 10, you're set.

Additionally, this chapter (and this book) will be easier to follow if you're familiar with one programming language. All the examples in this book are in Python. If you don't know any programming languages and want to learn one, choose Python—it's great for beginners. If you know another language, like Ruby, you'll be fine.

Binary search

Suppose you're searching for a person in the phone book (what an old-fashioned sentence!). Their name starts with K. You could start at the beginning and keep flipping pages until you get to the Ks. But you're more likely to start at a page in the middle, because you know the Ks are going to be near the middle of the phone book.

Or suppose you're searching for a word in a dictionary, and it starts with O. Again, you'll start near the middle.

Now suppose you log on to Facebook. When you do, Facebook has to verify that you have an account on the site. So, it needs to search for your username in its database. Suppose your username is karlmageddon. Facebook could start from the As and search for your name—but it makes more sense for it to begin somewhere in the middle.

This is a search problem. And all these cases use the same algorithm to solve the problem: binary search.

Binary search is an algorithm; its input is a sorted list of elements (I'll explain later why it needs to be sorted). If an element you're looking for is in that list, binary search returns the position where it's located. Otherwise, binary search returns null.

Image summary: A black and white sketch of a person looking at a computer monitor displaying a screen of abstract, geometric patterns. It is an illustration, with no data or analytical result to report.

For example:

Image summary: A diagram illustrating the concept of a pointer or index using two examples of a phone book in a container. In the first case, the entry for Kramerica Industries is found in the book at entry 1440, which is returned as the result. In the second case, Vandelay Industries is not in the book, resulting in a NULL return. The point is to demonstrate how a lookup process returns a specific address when a record exists and a null value when it does not.

Here's an example of how binary search works. I'm thinking of a number between 1 and 100.

Table summary: A sequence of numbers starting at 1, 2, 3, and continuing up to 100.

You have to try to guess my number in the fewest tries possible. With every guess, I'll tell you if your guess is too low, too high, or correct. Suppose you start guessing like this: 1, 2, 3, 4 .... Here's how it would go.

Image summary: A two-panel comic strip depicting a guessing game. In the first panel, a man guesses 1, and a woman responds that it is too low, while a number line shows 1 crossed out. In the second panel, the man guesses 2, and the woman again responds that it is too low, while the number line shows both 1 and 2 crossed out. The illustration depicts the process of elimination in a linear search.

Image summary: A cartoon depicting a man guessing a number, saying "7", while a woman responds "TOO LOW" and the man shouts "ARGH!". Above them is a row of boxes from 1 to 100, with the first several numbers crossed out. The illustration depicts the frustration of a trial-and-error guessing game.

This is simple search (maybe stupid search would be a better term). With each guess, you're eliminating only one number. If my number was 99, it could take you 99 guesses to get there!

A better way to search

Here's a better technique. Start with 50.

A bad approach to number guessing

Image summary: A comic strip depicting a person suggesting the number 50, to which another person responds that it is too low. To the right, a number line from 1 to 100 shows all numbers from 1 to 50 crossed out with a caption stating they are all too low. The image humorously illustrates the concept of a search space where all values below a certain threshold are rejected.

Too low, but you just eliminated half the numbers! Now you know that 1 to 50 are all too low. Next guess: 75.

Image summary: A comic strip showing two people in a conversation. One person says "75" in a speech bubble, and the other responds with "TOO HIGH!" in another bubble. It is a cartoon depicting a disagreement or negotiation over a numerical value.

Too high, but again you cut down half the remaining numbers! With binary search, you guess the middle number and eliminate half the remaining numbers every time. Next is 63 (halfway between 50 and 75).

Image summary: A two-panel comic strip showing a man proposing numbers and a woman reacting. In the first panel, the man says "63" and the woman responds "TOO HIGH!"; in the second panel, the man says "57" and the woman responds "YES!". The image depicts a simple process of iterative adjustment to reach an acceptable value.

This is binary search. You just learned your first algorithm! Here's how many numbers you can eliminate every time.

Image summary: A diagram showing a sequence of numbers in boxes connected by arrows, starting at 100 items and halving at each stage to 50, 25, 13, 7, 4, 2, and finally 1. The sequence is labeled as 7 steps, illustrating a logarithmic reduction process.

Whatever number I'm thinking of, you can guess in a maximum of seven guesses—because you eliminate so many numbers with every guess!

Suppose you're looking for a word in the dictionary. The dictionary has 240,000 words. In the worst case, how many steps do you think each search will take?

Simple Search: _ _ Steps

Binary Search: _ _ Steps

Simple search could take 240,000 steps if the word you're looking for is the very last one in the book. With each step of binary search, you cut the number of words in half until you're left with only one word.

Image summary: A diagram showing a sequence of numbers starting from 240,000 and repeatedly halving until reaching 1. The values progress through three rows, consistently dividing by two at each step, illustrating a geometric decay process ending at unity.

So binary search will take 18 steps—a big difference! In general, for any list of n, binary search will take log base 2 of n steps to run in the worst case, whereas simple search will take n steps.

Logarithms

You may not remember what logarithms are, but you probably know what exponentials are. log base 10 of 100 is like asking, 01c How many 10s do we multiply together to get 100?01d The answer is 2: 10 times 10. So log base 10 of 100 equals 2. Logs are the flip of exponentials.

Math summary: This expression demonstrates the relationship between exponents and logarithms using base ten and base two. It shows that raising a base to a specific power produces a result, while the logarithm of that result returns the original power, such as two to the power of five equaling thirty two and the base two logarithm of thirty two equaling five.

Logs are the flip of exponentials.

In this book, when I talk about running time in Big O notation (explained a little later), log always means log 2 . When you search for an element using simple search, in the worst case you might have to look at every single element. So for a list of 8 numbers, you'd have to check 8 numbers at most. For binary search, you have to check log n elements in the worst case. For a list of 8 elements, log 8 == 3 , because 2 ^3 == 8 . So for a list of 8 numbers, you would have to check 3 numbers at most. For a list of 1,024 elements, log 1,024 = 10 , because 2 superscript 10 == 1,024 . So for a list of 1,024 numbers, you'd have to check 10 numbers at most.

Note

I'll talk about log time a lot in this book, so you should understand the concept of logarithms. If you don't, Khan Academy (khanacademy dot org) has a nice video that makes it clear.

Note

Binary search only works when your list is in sorted order. For example, the names in a phone book are sorted in alphabetical order, so you can use binary search to look for a name. What would happen if the names weren't sorted?

Let's see how to write binary search in Python. The code sample here uses arrays. If you don't know how arrays work, don't worry; they're covered in the next chapter. You just need to know that you can store a sequence of elements in a row of consecutive buckets called an array. The buckets are numbered starting with 0: the first bucket is at position #0, the second is #1, the third is #2, and so on.

The binary search function takes a sorted array and an item. If the item is in the array, the function returns its position. You'll keep track of what part of the array you have to search through. At the beginning, this is the entire array:

Code summary: This snippet initializes the boundary pointers for a binary search, setting a low index at the start and a high index at the end of the list to define the initial search range.

Image summary: A hand-drawn diagram showing a row of four boxes, each containing a dot, with arrows pointing to the first and last boxes labeled "LOW" and "HIGH" respectively. A bracket beneath the boxes is labeled "THESE ARE ALL THE NUMBERS WE ARE SEARCHING THROUGH," depicting the initial state of a search range.

these are all the

numbers we are

searching through

Each time, you check the middle element:

Math summary: This computation determines the middle index and the corresponding value for a search process. It calculates the middle index by taking the average of the low and high bounds and then uses that index to retrieve a guess from the list.

mid is rounded down by Python automatically if (low + high) isn't an even number.

If the guess is too low, you update low accordingly:

Code summary: This logic implements a boundary update for a binary search, shifting the lower bound to narrow the search range when the current guess is lower than the target item.

Image summary: A simple diagram showing a sequence of four boxes. The first two boxes are empty except for a central dot, with arrows above them labeled LOW and NEW HIGH, respectively. The final two boxes contain large X marks. The diagram illustrates a transition from a low state to a new high state, followed by a termination or invalidation of the sequence.

And if the guess is too high, you update high. Here's the full code:

Code summary: binary_search efficiently locates the index of a target item within a sorted list. It repeatedly halves the search area by comparing the target to the middle element, adjusting the lower or upper boundaries to discard the half where the item cannot exist. The process continues until the item is found or the search range is exhausted, returning the index of the item or None if it is not present.

Exercises

1.1 Suppose you have a sorted list of 128 names, and you're searching through it using binary search. What's the maximum number of steps it would take?

1.2 Suppose you double the size of the list. What's the maximum number of steps now?

Any time I talk about an algorithm, I'll discuss its running time. Generally you want to choose the most efficient algorithm—whether you're trying to optimize for time or space.

Back to binary search. How much time do you save by using it? Well, the first approach was to check each number, one by one. If this is a list of 100 numbers, it takes up to 100 guesses.

Image summary: A sketch of a wristwatch where the face displays various Big O notation complexities, including O(n!), O(2^n), O(n^3), and O(n), with an arrow pointing toward O(n!). The drawing uses computational complexity symbols as clock markers to humorously represent the passage of time or growth rates.

If it's a list of 4 billion numbers, it takes up to 4 billion guesses. So the maximum number of guesses is the same as the size of the list. This is called linear time.

Binary search is different. If the list is 100 items long, it takes at most 7 guesses. If the list is 4 billion items, it takes at most 32 guesses. Powerful, eh? Binary search runs in logarithmic time (or log time, as the natives call it). Here's a table summarizing our findings today.

Image summary: A comparison table showing the number of guesses required for Simple Search versus Binary Search as the number of items increases. For 100 items, Simple Search takes 100 guesses while Binary Search takes 7; for 4 billion items, Simple Search takes 4 billion guesses while Binary Search takes only 32. The takeaway is that Binary Search, with logarithmic time complexity O(log n), is significantly more efficient than Simple Search, which has linear time complexity O(n).

Big O notation

Big O notation is special notation that tells you how fast an algorithm is. Who cares? Well, it turns out that you'll use other people's algorithms often—and when you do, it's nice to understand how fast or slow they are. In this section, I'll explain what Big O notation is and give you a list of the most common running times for algorithms using it.

Run times for search algorithms

Algorithm running times grow at different rates

Bob is writing a search algorithm for nasa. His algorithm will kick in when a rocket is about to land on the Moon, and it will help calculate where to land.

This is an example of how the run time of two algorithms can grow at different rates. Bob is trying to decide between simple search and binary search. The algorithm needs to be both fast and correct.

On one hand, binary search is faster. And Bob has only 10 seconds to figure out where to land—otherwise, the rocket will be off course. On the other hand, simple search is easier to write, and there is less chance of bugs being introduced. And Bob really doesn't want bugs in the code to land a rocket! To be extra careful, Bob decides to time both algorithms with a list of 100 elements.

Let's assume it takes 1 millisecond to check one element. With simple search, Bob has to check 100 elements, so the search takes 100 ms to run. On the other hand, he only has to check 7 elements with binary search ( log 2 100 is roughly 7), so that search takes 7 ms to run. But realistically, the list will have more like a billion elements. If it does, how long will simple search take?

How long will binary search take? Make sure you have an answer for each question before reading on.

Image summary: A conceptual diagram comparing simple search and binary search, using two hourglass-like containers and a clock. Simple search is associated with a time of 100 ms, while binary search is associated with 7 ms. The illustration highlights that binary search is significantly faster than simple search.

Bob runs binary search with 1 billion elements, and it takes 30 ms ( log 2 1,000,000,000 is roughly 30). “32 ms!” he thinks. “Binary search is about 15 times faster than simple search, because simple search took 100 ms with 100 elements, and binary search took 7 ms. So simple search will take 30 times 15 = 450 ms, right? Way under my threshold of 10 seconds.” Bob decides to go with simple search. Is that the right choice?

No. Turns out, Bob is wrong. Dead wrong. The run time for simple search with 1 billion items will be 1 billion ms, which is 11 days! The problem is, the run times for binary search and simple search don't grow at the same rate.

Table summary: Binary search is significantly faster than simple search as the number of elements increases. For 100 elements, simple search takes 100ms. When scaled to 10,000 elements, simple search slows to 10seconds while binary search takes only 14ms. At 1,000,000,000 elements, the gap widens drastically, with simple search taking 11days and binary search taking 32ms.

That is, as the number of items increases, binary search takes a little more time to run. But simple search takes a lot more time to run. So as the list of numbers gets bigger, binary search suddenly becomes a lot faster than simple search. Bob thought binary search was 15 times faster than simple search, but that's not correct. If the list has 1 billion items, it's more like 33 million times faster.

That's why it's not enough to know how long an algorithm takes to run—you need to know how the running time increases as the list size increases. That's where Big O notation comes in.

Big O notation tells you how fast an algorithm is. For example, suppose you have a list of size n. Simple search needs to check each element, so it will take n operations. The run time in Big O notation is O(n) . Where are the seconds? There are none—Big O doesn't tell you the speed in seconds. Big O notation lets you compare the number of operations. It tells you how fast the algorithm grows.

Here's another example. Binary search needs log n operations to check a list of size n. What's the running time in Big O notation? It's O( log n ). In general, Big O notation is written as follows.

Image summary: A hand-drawn diagram of the Big O notation O(n), with arrows pointing to the 'O' and the '(n)'. The 'O' is labeled as "BIG O" and the '(n)' is labeled as "NUMBER OF OPERATIONS". The diagram serves to define the basic components of Big O notation used to describe algorithmic complexity.

This tells you the number of operations an algorithm will make. It's called Big O notation because you put a "big O" in front of the number of operations (it sounds like a joke, but it's true!).

Now let's look at some examples. See if you can figure out the run time for these algorithms.

Visualizing different Big O run times

Here's a practical example you can follow at home with a few pieces of paper and a pencil. Suppose you have to draw a grid of 16 boxes.

Algorithm 1

One way to do it is to draw 16 boxes, one at a time. Remember, Big O notation counts the number of operations. In this example, drawing one box is one operation. You have to draw 16 boxes. How many operations will it take, drawing one box at a time?

What Big O notation looks like

Image summary: A hand-drawn 4-by-4 grid containing numbers 1 through 16 arranged sequentially from left to right, top to bottom. A line is drawn connecting the numbers 5, 6, and 3. This is a simple illustration of a numbered grid with a partial path traced through it.

What's a good algorithm to draw this grid?

Image summary: A three-frame sequence of sketches showing a hand using a pen to draw a grid on a piece of paper, adding one square at a time. The sequence illustrates the process of drawing a grid one box at a time.

It takes 16 steps to draw 16 boxes. What's the running time for this algorithm?

Drawing a grid one box at a time

Algorithm 2

Try this algorithm instead. Fold the paper.

Image summary: A simple line drawing of a piece of paper being folded or flipped, indicated by a curved arrow. It is a conceptual illustration of a folding action, with no data or analytical result to report.

In this example, folding the paper once is an operation. You just made two boxes with that operation!

Fold the paper again, and again, and again.

Image summary: A sketch showing a piece of paper being folded in three stages, with arrows indicating the direction of each fold. The sequence demonstrates the process of folding a flat sheet into a small, compact square.

Unfold it after four folds, and you'll have a beautiful grid! Every fold doubles the number of boxes. You made 16 boxes with 4 operations!

Image summary: A series of four diagrams showing a square piece of paper being folded an increasing number of times, from 1 fold to 4 folds. As the number of folds increases, the number of crease lines and the resulting grid of smaller rectangular sections grow. The point is to illustrate how repeated folding exponentially increases the number of divisions on the paper.

You can “draw” twice as many boxes with every fold, so you can draw 16 boxes in 4 steps. What's the running time for this algorithm? Come up with running times for both algorithms before moving on.

Answers: Algorithm 1 takes big O of n time, and algorithm 2 takes big O of log n time.

Big O establishes a worst-case run time

Suppose you're using simple search to look for a person in the phone book. You know that simple search takes O(n) time to run, which means in the worst case, you'll have to look through every single entry in your phone book. In this case, you're looking for Adit. This guy is the first entry in your phone book.

So you didn't have to look at every entry—you found it on the first try. Did this algorithm take O (n) time? Or did it take O (1) time because you found the person on the first try?

Simple search still takes O(n) time. In this case, you found what you were looking for instantly. That's the best-case scenario. But Big O notation is about the worst-case scenario.

So you can say that, in the worst case, you'll have to look at every entry in the phone book once. That's O(n) time. It's a reassurance—you know that simple search will never be slower than O(n) time.

Note

Along with the worst-case run time, it's also important to look at the average-case run time. Worst case versus average case is discussed in chapter 4.

Some common Big O run times

Here are five Big O run times that you'll encounter a lot, sorted from fastest to slowest:

• Big O of log n, also known as log time. Example: Binary search.

• O(n), also known as linear time. Example: Simple search.

• Big O of n times log n. Example: A fast sorting algorithm, like quicksort (coming up in chapter 4).

• O ( n squared ). Example: A slow sorting algorithm, like selection sort (coming up in chapter 2).

- O(n!). Example: A really slow algorithm, like the traveling salesperson (coming up next!).

Suppose you're drawing a grid of 16 boxes again, and you can choose from 5 different algorithms to do so. If you use the first algorithm, it will take you O(log n) time to draw the grid. You can do 10 operations per second. With O( log n ) time, it will take you 4 operations to draw a grid of 16 boxes ( log 16 is 4). So it will take you 0.4 seconds to draw the grid. What if you have to draw 1,024 boxes? It will take you log 1,024 = 10 operations, or 1 second to draw a grid of 1,024 boxes. These numbers are using the first algorithm.

The second algorithm is slower: it takes O(n) time. It will take 16 operations to draw 16 boxes, and it will take 1,024 operations to draw 1,024 boxes. How much time is that in seconds?

Here's how long it would take to draw a grid for the rest of the algorithms, from fastest to slowest:

Table summary: Processing time increases significantly as the number of boxes grows, with the fastest method maintaining near-constant speed while others scale poorly. For 1024 boxes, the fastest method takes only 1.0sec, whereas the method with O(nLogn) complexity takes 1.7min, the O(n squared) method takes 17min, and the O(n factorial) method takes 1.2days. This trend is evident at 256 boxes as well, where times range from 0.8sec for the fastest method up to 1.8hrs for the O(n factorial) approach.

There are other run times, too, but these are the five most common.

This is a simplification. In reality you can't convert from a Big O run time to a number of operations this neatly, but this is good enough for now. We'll come back to Big O notation in chapter 4, after you've learned a few more algorithms. For now, the main takeaways are as follows:

- Algorithm speed isn't measured in seconds, but in growth of the number of operations.

• Instead, we talk about how quickly the run time of an algorithm increases as the size of the input increases.

- Run time of algorithms is expressed in Big O notation.

- O( log n ) is faster than O(n), but it gets a lot faster as the list of items you're searching grows.

Give the run time for each of these scenarios in terms of Big O.

1.3 You have a name, and you want to find the person's phone number in the phone book.

1.4 You have a phone number, and you want to find the person's name in the phone book. (Hint: You'll have to search through the whole book!)

1.5 You want to read the numbers of every person in the phone book.

1.6 You want to read the numbers of just the As. (This is a tricky one! It involves concepts that are covered more in chapter 4. Read the answer—you may be surprised!)

The traveling salesperson

You might have read that last section and thought, “There's no way I'll ever run into an algorithm that takes O(n!) time.” Well, let me try to prove you wrong! Here's an example of an algorithm with a really bad running time. This is a famous problem in computer science, because its growth is appalling and some very smart people think it can't be improved. It's called the traveling salesperson problem.

You have a salesperson.

The salesperson has to go to five cities.

Image summary: A hand-drawn map showing the locations of Marin, Berkeley, San Francisco, Fremont, and Palo Alto, with pins marking the specific positions of each city. The purpose of the drawing is to illustrate the relative geographic positions of these cities in the San Francisco Bay Area.

This salesperson, whom I'll call Opus, wants to hit all five cities while traveling the minimum distance. Here's one way to do that: look at every possible order in which he could travel to the cities.

Image summary: A series of three hand-drawn diagrams comparing different travel paths between the same set of points, with total distances listed below each. The first path is the longest at 120 miles, the second is the shortest at 103 miles, and the third is 133 miles. The figure illustrates how choosing different sequences of movement between locations results in different total travel distances.

He adds up the total distance and then picks the path with the lowest distance. There are 120 permutations with 5 cities, so it will take 120 operations to solve the problem for 5 cities. For 6 cities, it will take 720 operations (there are 720 permutations). For 7 cities, it will take 5,040 operations!

Table summary: A mapping of cities to specific operations. For example, city 6 corresponds to operation 72 phi, city 7 to 5 phi 4 phi, and city 8 to 4 phi 32 phi. The list extends to city 15, which is associated with operation 13 phi 7674368 phi phi, and includes an entry where city 3 phi maps to a sequence of large numeric values: 265252859, 812191, and 058636308483000000.

In general, for n items, it will take n factorial operations to compute the result. So this is big O of n factorial time, or factorial time. It takes a lot of operations for everything except the smallest numbers. Once you're dealing with 100 plus cities, it's impossible to calculate the answer in time—the Sun will collapse first.

This is a terrible algorithm! Opus should use a different one, right? But he can't. This is one of the unsolved problems in computer science.

There's no fast known algorithm for it, and smart people think it's impossible to have a smart algorithm for this problem. The best we can do is come up with an approximate solution; see chapter 10 for more.

One final note: if you're an advanced reader, check out binary search trees! There's a brief description of them in the last chapter.

Recap

- Binary search is a lot faster than simple search.

- O( log n ) is faster than O(n), but it gets a lot faster once the list of items you're searching through grows.

- Algorithm speed isn't measured in seconds.

- Algorithm times are measured in terms of growth of an algorithm.

- Algorithm times are written in Big O notation.

In this chapter

- You learn about arrays and linked lists—two of the most basic data structures. They're used absolutely everywhere. You already used arrays in chapter 1, and you'll use them in almost every chapter in this book. Arrays are a crucial topic, so pay attention! But sometimes it's better to use a linked list instead of an array. This chapter explains the pros and cons of both so you can decide which one is right for your algorithm.

- You learn your first sorting algorithm. A lot of algorithms only work if your data is sorted. Remember binary search? You can run binary search only on a sorted list of elements. This chapter teaches you selection sort. Most languages have a sorting algorithm built in, so you'll rarely need to write your own version from scratch. But selection sort is a stepping stone to quicksort, which I'll cover in the next chapter. Quicksort is an important algorithm, and it will be easier to understand if you know one sorting algorithm already.

To understand the performance analysis bits in this chapter, you need to know Big O notation and logarithms. If you don't know those, I suggest you go back and read chapter 1. Big O notation will be used throughout the rest of the book.

How memory works

Imagine you go to a show and need to check your things. A chest of drawers is available.

Image summary: A line drawing of a chest of drawers featuring eight drawers arranged in two columns of four, with a decorative scalloped edge on the top right side. It is a simple illustration of a piece of furniture.

Each drawer can hold one element. You want to store two things, so you ask for two drawers.

Image summary: A comic strip showing a man requesting "Two DRAWERS, PLEASE!" while gesturing with two fingers, and a clerk responding, "MONSIEUR CAN USE THESE DRAWERS," while pointing to two open drawers in a chest. The image is a play on words, contrasting the request for curtains (drawers) with the physical furniture provided.

You store your two things here.

Image summary: A drawing showing two open drawers. The drawer on the left, labeled "UMBRELLA", contains an umbrella, and the drawer on the right, labeled "BUNNY", contains a bunny. The image depicts a simple mapping of specific objects to their corresponding labeled containers.

And you're ready for the show! This is basically how your computer's memory works. Your computer looks like a giant set of drawers, and each drawer has an address.

Image summary: A hand-drawn diagram showing a grid of memory cells, with an arrow pointing from a hexadecimal memory address, fe0ffeeb, to a specific cell in the top row. This depicts the concept of a memory address mapping to a specific physical or virtual location in memory.

fe empty set ffeeb is the address of a slot in memory.

Each time you want to store an item in memory, you ask the computer for some space, and it gives you an address where you can store your item. If you want to store multiple items, there are two basic ways to do so: arrays and lists. I'll talk about arrays and lists next, as well as the pros and cons of each. There isn't one right way to store items for every use case, so it's important to know the differences.

Arrays and linked lists

Sometimes you need to store a list of elements in memory. Suppose you're writing an app to manage your todos. You'll want to store the todos as a list in memory.

Should you use an array, or a linked list? Let's store the todos in an array first, because it's easier to grasp. Using an array means all your tasks are stored contiguously (right next to each other) in memory.

Image summary: A hand-drawn diagram representing memory allocation as a grid of cells. Some cells are filled with specific tasks like "BRUNCH", "BOCCE", and "TEA" under a "YOUR TO-DO LIST" label, some are hatched to indicate "MEMORY IN USE BY SOMEONE ELSE", and others are empty, labeled as "FREE MEMORY". The diagram illustrates how a shared memory resource is partitioned between user tasks, other users, and available space.

Now suppose you want to add a fourth task. But the next drawer is taken up by someone else's stuff!

can't Add A Task Here, Already Occupied

Table summary: A list containing the items BRUNCH, BOCCE, and TEA.

Image summary: A simple line drawing of a clipboard containing a checklist with three items: Brunch, Bocce, and Tea. Only the box for Tea is checked. The image depicts a completed selection from a short list of activities.

It's like going to a movie with your friends and finding a place to sit—but another friend joins you, and there's no place for them. You have to move to a new spot where you all fit. In this case, you need to ask your computer for a different chunk of memory that can fit four tasks. Then you need to move all your tasks there.

If another friend comes by, you're out of room again—and you all have to move a second time! What a pain. Similarly, adding new items to an array can be a big pain. If you're out of space and need to move to a new spot in memory every time, adding a new item will be really slow. One easy fix is to “hold seats”: even if you have only 3 items in your task list, you can ask the computer for 10 slots, just in case. Then you can add 10 items to your task list without having to move. This is a good workaround, but you should be aware of a couple of downsides:

- You may not need the extra slots that you asked for, and then that memory will be wasted. You aren't using it, but no one else can use it either.

- You may add more than 10 items to your task list and have to move anyway.

So it's a good workaround, but it's not a perfect solution. Linked lists solve this problem of adding items.

Linked lists

With linked lists, your items can be anywhere in memory.

Image summary: A hand-drawn grid representing memory allocation, with some cells labeled as "FREE MEMORY," others containing words like "BRUNCH," "BOCCE," and "TEA," and several shaded cells labeled as "MEMORY IN USE BY SOMEONE ELSE." The diagram illustrates how memory is partitioned into available, occupied, and reserved blocks.

Each item stores the address of the next item in the list. A bunch of random memory addresses are linked together.

: Image summary: A hand-drawn grid of cells containing words and numbers. The top row includes "BRUNCH" in the second cell and a curved arrow pointing from the second cell to the fourth cell, labeled "03". The middle row contains "BOCCE" in the fourth cell and a curved arrow pointing from the fourth cell to the third cell, labeled "12". The bottom row contains "TEA" in the third cell. Several cells are filled with diagonal hatching. The image is a sketch of a word or logic puzzle.

It's like a treasure hunt. You go to the first address, and it says, "The next item can be found at address 123." So you go to address 123, and it says, "The next item can be found at address 847," and so on. Adding an item to a linked list is easy: you stick it anywhere in memory and store the address with the previous item.

With linked lists, you never have to move your items. You also avoid another problem. Let's say you go to a popular movie with five of your friends.

The six of you are trying to find a place to sit, but the theater is packed. There aren't six seats together. Well, sometimes this happens with arrays. Let's say you're trying to find 10,000 slots for an array. Your memory has 10,000 slots, but it doesn't have 10,000 slots together.

You can't get space for your array! A linked list is like saying, "Let's split up and watch the movie." If there's space in memory, you have space for your linked list.

If linked lists are so much better at inserts, what are arrays good for?

Arrays

Websites with top-10 lists use a scummy tactic to get more page views. Instead of showing you the list on one page, they put one item on each page and make you click Next to get to the next item in the list. For example, Top 10 Best T.V Villains won't show you the entire list on one page. Instead, you start at #10 (Newman), and you have to click Next on each page to reach #1 (Gustavo Fring). This technique gives the websites 10 whole pages on which to show you ads, but it's boring to click Next 9 times to get to #1. It would be much better if the whole list was on one page and you could click each person's name for more info.

Linked lists have a similar problem. Suppose you want to read the last item in a linked list. You can't just read it, because you don't know what address it's at. Instead, you have to go to item #1 to get the address for item #2. Then you have to go to item #2 to get the address for item #3. And so on, until you get to the last item. Linked lists are great if you're going to read all the items one at a time: you can read one item, follow the address to the next item, and so on. But if you're going to keep jumping around, linked lists are terrible.

Arrays are different. You know the address for every item in your array. For example, suppose your array contains five items, and you know it starts at address 00. What is the address of item #5?

Image summary: A diagram of an array containing five contiguous memory slots, indexed from 00 to 04. An arrow points to the final slot, labeled as "THE FIFTH ELEMENT," illustrating that in zero-based indexing, the fifth element is located at index 04.

Simple math tells you: it's 04. Arrays are great if you want to read random elements, because you can look up any element in your array instantly. With a linked list, the elements aren't next to each other, so you can't instantly calculate the position of the fifth element in memory—you have to go to the first element to get the address to the second element, then go to the second element to get the address of the third element, and so on until you get to the fifth element.

Terminology

The elements in an array are numbered. This numbering starts from 0, not 1. For example, in this array, 20 is at position 1.

Image summary: A hand-drawn diagram of a horizontal array divided into four cells containing the numbers 10, 20, 30, and 40, with index labels 0, 1, 2, and 3 positioned below each respective cell. The figure illustrates the basic structure of a zero-indexed array where values are stored at specific numerical positions.

And 10 is at position 0. This usually throws new programmers for a spin. Starting at 0 makes all kinds of array-based code easier to write, so programmers have stuck with it. Almost every programming language you use will number array elements starting at 0. You'll soon get used to it.

The position of an element is called its index. So instead of saying, “20 is at position 1,” the correct terminology is, “20 is at index 1.” I'll use index to mean position throughout this book.

Here are the run times for common operations on arrays and lists.

Table summary: Lists offer faster insertion at O(1) compared to arrays at O(n), while arrays provide faster reading at O(1) compared to lists at O(n).

Math summary: This expression defines the time complexity for common array and list operations. It specifies that big O of n represents linear time and big O of one represents constant time.

Question: Why does it take O(n) time to insert an element into an array? Suppose you wanted to insert an element at the beginning of an array. How would you do it? How long would it take? Find the answers to these questions in the next section!

Exercise

2.1 Suppose you're building an app to keep track of your finances.

1. Groceries 2. Movie 3. S.F.B.C Membership

Every day, you write down everything you spent money on. At the end of the month, you review your expenses and sum up how much you spent. So, you have lots of inserts and a few reads. Should you use an array or a list?

Inserting into the middle of a list

Suppose you want your todo list to work more like a calendar. Earlier, you were adding things to the end of the list.

Now you want to add them in the order in which they should be done.

Image summary: A drawing of a clipboard containing a checklist with four items: Brunch, Bocce, Drink Tea, and Buy Tea. The caption below reads "Unordered," illustrating a list of tasks where the sequence of completion is not specified.

Image summary: A drawing of a clipboard with a checklist containing four items: Brunch, Bocce, Buy Tea, and Drink Tea. None of the checkboxes are marked, depicting a simple to-do list.

What's better if you want to insert elements in the middle: arrays or lists? With lists, it's as easy as changing what the previous element points to.

Image summary: Two hand-drawn grids showing the movement of words across cells. In the first grid, the word BRUNCH moves from cell 01 to 03, and the word TEA moves from cell 12 to 22, while BOCCE is positioned at 13. In the second grid, the words shift again: BRUNCH remains in the top row, BOCCE moves to 13, BUY TEA moves to 14, and DRINK TEA moves to 22. The sequence illustrates a process of rearranging or evolving text within a structured grid.

But for arrays, you have to shift all the rest of the elements down.

Image summary: A hand-drawn diagram showing a task list grid with the tasks BRUNCH, BOCCE, and DRINK TEA. A new task, BUY TEA, is being inserted before DRINK TEA, with an arrow indicating that DRINK TEA must be shifted down to accommodate it. The diagram illustrates the process of inserting a new item into a sequential schedule.

And if there's no space, you might have to copy everything to a new location! Lists are better if you want to insert elements into the middle.

Deletions

What if you want to delete an element? Again, lists are better, because you just need to change what the previous element points to. With arrays, everything needs to be moved up when you delete an element.

Unlike insertions, deletions will always work. Insertions can fail sometimes when there's no space left in memory. But you can always delete an element.

Here are the run times for common operations on arrays and linked lists.

Table summary: ARRAYs provide faster reading at O(1) compared to LISTS at O(n), while LISTS are more efficient for insertion and deletion, both at O(1), whereas ARRAYs require O(n) for these operations.

It's worth mentioning that insertions and deletions are O (1) time only if you can instantly access the element to be deleted. It's a common practice to keep track of the first and last items in a linked list, so it would take only O (1) time to delete those.

Which are used more: arrays or lists? Obviously, it depends on the use case. But arrays see a lot of use because they allow random access. There are two different types of access: random access and sequential access.

Sequential access means reading the elements one by one, starting at the first element. Linked lists can only do sequential access. If you want to read the 10th element of a linked list, you have to read the first 9 elements and follow the links to the 10th element. Random access means you can jump directly to the 10th element. You'll frequently hear me say that arrays are faster at reads. This is because they provide random access.

A lot of use cases require random access, so arrays are used a lot. Arrays and lists are used to implement other data structures, too (coming up later in the book).

2.2 Suppose you're building an app for restaurants to take customer orders. Your app needs to store a list of orders. Servers keep adding orders to this list, and chefs take orders off the list and make them. It's an order queue: servers add orders to the back of the queue, and the chef takes the first order off the queue and cooks it.

Image summary: A diagram depicting a queue system in a kitchen, where servers add order slips to the back of an order queue and chefs pull them off from the front. This illustrates a first-in, first-out mechanism for processing orders.

Would you use an array or a linked list to implement this queue?

(Hint: Linked lists are good for inserts/deletes, and arrays are good for random access. Which one are you going to be doing here?)

2.3 Let's run a thought experiment. Suppose Facebook keeps a list of usernames. When someone tries to log in to Facebook, a search is done for their username. If their name is in the list of usernames, they can log in. People log in to Facebook pretty often, so there are a lot of searches through this list of usernames. Suppose Facebook uses binary search to search the list.

Binary search needs random access—you need to be able to get to the middle of the list of usernames instantly. Knowing this, would you implement the list as an array or a linked list?

2.4 People sign up for Facebook pretty often, too. Suppose you decided to use an array to store the list of users. What are the downsides of an array for inserts? In particular, suppose you're using binary search to search for logins. What happens when you add new users to an array?

2.5 In reality, Facebook uses neither an array nor a linked list to store user information. Let's consider a hybrid data structure: an array of linked lists. You have an array with 26 slots. Each slot points to a linked list. For example, the first slot in the array points to a linked list containing all the usernames starting with a. The second slot points to a linked list containing all the usernames starting with b, and so on.

Image summary: A diagram depicting a hash table structure where an array of pointers leads to three separate linked lists. Each list groups usernames starting with the same letter, such as "A", "B", and "C". This structure demonstrates how a hash table uses chaining with linked lists to handle multiple entries that map to the same array index.

Suppose Adit B signs up for Facebook, and you want to add them to the list. You go to slot 1 in the array, go to the linked list for slot 1, and add Adit B at the end. Now, suppose you want to search for Zakhir H. You go to slot 26, which points to a linked list of all the Z names. Then you search through that list to find Zakhir H.

Compare this hybrid data structure to arrays and linked lists. Is it slower or faster than each for searching and inserting? You don't have to give Big O run times, just whether the new data structure would be faster or slower.

Selection sort

Let's put it all together to learn your second algorithm: selection sort. To follow this section, you need to understand arrays and lists, as well as Big O notation. Suppose you have a bunch of music on your computer. For each artist, you have a play count.

Table summary: RADIOHEAD has the highest play count at 156, followed closely by KISHORE KUMAR with 141. Other artists include WILCO with 111, NEUTRAL MILK HOTEL with 94, BECK with 88, THE STROKES with 61, and THE BLACK KEYS with the fewest plays at 35.

You want to sort this list from most to least played, so that you can rank your favorite artists. How can you do it?

One way is to go through the list and find the most-played artist. Add that artist to a new list.

Table summary: RADIOHEAD has the highest play count with 156, followed by KISHORE KUMAR with 141 and WILCO with 111. Other artists include NEUTRAL MILK HOTEL at 94, BECK at 88, THE STROKES at 61, and THE BLACK KEYS with the lowest count of 35.

1. Radiohead

is the most played artist...

Table summary: RADIOHEAD has a play count of 156.

2. Add it to A new list

Do it again to find the next-most-played artist.

Table summary: KISHORE KUMAR has the highest play count at 141, followed by WILCO with 111. Other artists include NEUTRAL MILK HOTEL with 94, BECK with 88, THE STROKES with 61, and THE BLACK KEYS with 35.

1. Kishor Kumar is the Next most-played artist

Table summary: RADIOHEAD has the highest play count with 156, followed by KISHORE KUMAR with 141.

2. so it is the Next artist added to the new list

Keep doing this, and you'll end up with a sorted list.

Table summary: RADIOHEAD has the highest play count at 156, followed by KISHORE KUMAR with 141 and WILCO with 111. Other artists include NEUTRAL MILK HOTEL with 94, BECK with 88, THE STROKES with 61, and THE BLACK KEYS with 35.

Let's put on our computer science hats and see how long this will take to run. Remember that O(n) time means you touch every element in a list once. For example, running simple search over the list of artists means looking at each artist once.

1. Radiohead

2. Kishor Kumar

3. the Black Keys

4. Neutral Milk Hotel

5. Beck

6. the Strokes

7. will C-O h

items

To find the artist with the highest play count, you have to check each item in the list. This takes O(n) time, as you just saw. So you have an operation that takes O(n) time, and you have to do that n times:

: Image summary: A diagram illustrating an algorithm's time complexity by showing three sequential lists of artists. Each list is processed in O(n) time, and the process is repeated n times. The total complexity is the result of performing an O(n) operation n times, demonstrating a total time complexity of O(n^2).

This takes big O of n times n time or big O of n squared time.

Sorting algorithms are very useful. Now you can sort

- Names in a phone book

• Travel dates

• Emails (newest to oldest)

Checking fewer elements each time

Maybe you're wondering: as you go through the operations, the number of elements you have to check keeps decreasing. Eventually, you're down to having to check just one element. So how can the run time still be O (n squared) ? That's a good question, and the answer has to do with constants in Big O notation. I'll get into this more in chapter 4, but here's the gist.

You're right that you don't have to check a list of n elements each time. You check n elements, then n minus 1, n minus 2 through 2, 1. On average, you check a list that has 1 over 2 times n elements. The runtime is Big O of n times 1 over 2 times n. But constants like 1 over 2 are ignored in Big O notation (again, see chapter 4 for the full discussion), so you just write Big O of n times n or Big O of n squared.

Selection sort is a neat algorithm, but it's not very fast. Quicksort is a faster sorting algorithm that only takes O(n log n) time. It's coming up in the next chapter!

Example Code Listing

We didn't show you the code to sort the music list, but following is some code that will do something very similar: sort an array from smallest to largest. Let's write a function to find the smallest element in an array:

Code summary: findSmallest identifies the position of the minimum element in a list. It initializes a tracker with the first element and its index, then iterates through the remaining items to update these trackers whenever a smaller value is encountered. The procedure returns the index of the smallest value found.

Now you can use this function to write selection sort:

Code summary: selectionSort organizes an unsorted array into a sorted one by repeatedly identifying the smallest remaining element. In each iteration, the algorithm uses a findSmallest subroutine to locate the minimum value, removes it from the original collection, and appends it to a new array until all elements have been transferred.

Recap

- Your computer's memory is like a giant set of drawers.

- When you want to store multiple elements, use an array or a list.

- With an array, all your elements are stored right next to each other.

- With a list, elements are strewn all over, and one element stores the address of the next one.

• Arrays allow fast reads.

• Linked lists allow fast inserts and deletes.

- All elements in the array should be the same type (all int, all doubles, and so on).

In this chapter

- You learn about recursion. Recursion is a coding technique used in many algorithms. It's a building block for understanding later chapters in this book.

- You learn how to break a problem down into a base case and a recursive case. The divide-and-conquer strategy (chapter 4) uses this simple concept to solve hard problems.

I'm excited about this chapter because it covers recursion, an elegant way to solve problems. Recursion is one of my favorite topics, but it's divisive. People either love it or hate it, or hate it until they learn to love it a few years later.

I personally was in that third camp. To make things easier for you, I have some advice:

- This chapter has a lot of code examples. Run the code for yourself to see how it works.

- I'll talk about recursive functions. At least once, step through a recursive function with pen and paper: something like, “Let's see, I pass 5 into factorial, and then I return 5 times passing 4 into factorial, which is ...”, and so on. Walking through a function like this will teach you how a recursive function works.

This chapter also includes a lot of pseudocode. Pseudocode is a high-level description of the problem you're trying to solve, in code. It's written like code, but it's meant to be closer to human speech.

Recursion

Suppose you're digging through your grandma's attic and come across a mysterious locked suitcase.

Grandma tells you that the key for the suitcase is probably in this other box.

Image summary: A sketch of an open main box containing several smaller nested boxes arranged inside it. The drawing illustrates a hierarchical organization of containers, depicting the concept of nesting objects within a larger box.

This box contains more boxes, with more boxes inside those boxes. The key is in a box somewhere. What's your algorithm to search for the key? Think of an algorithm before you read on.

Here's one approach.

Image summary: A flowchart depicting a recursive search process. The process begins by making a pile of boxes; while the pile is not empty, a box is grabbed. If a key is found, the process ends; if another box is found, it is added to the pile and the process repeats. The diagram illustrates a loop for searching through nested containers until a target item is found.

1. Make a pile of boxes to look through.

2. Grab a box, and look through it.

3. If you find a box, add it to the pile to look through later.

4. If you find a key, you're done!

5. Repeat.

Here's an alternate approach.

Image summary: A flowchart depicting a recursive process. The first step is to go through every item in a box; if a key is found, the process ends, but if another box is found, the process loops back to the start to examine the contents of that new box. The diagram illustrates how a recursive search can handle nested structures.

1. Look through the box.

2. If you find a box, go to step 1.

3. If you find a key, you're done!

Which approach seems easier to you? The first approach uses a while loop. While the pile isn't empty, grab a box and look through it:

Code summary: look_for_key implements a depth-first search to locate a key within a nested structure of boxes. It maintains a pile of boxes to explore, iteratively extracting a box and inspecting its contents. If a nested box is found, it is added to the pile for future search; if the key is found, the process terminates and reports the discovery.

The second way uses recursion. Recursion is where a function calls itself. Here's the second way in pseudocode:

Code summary: look_for_key is a recursive search algorithm designed to find a key nested within a collection of boxes. It iterates through each item in a box, triggering a recursive call whenever another box is encountered to explore deeper levels of nesting, and terminates the search by signaling when a key is located.

Both approaches accomplish the same thing, but the second approach is clearer to me. Recursion is used when it makes the solution clearer. There's no performance benefit to using recursion; in fact, loops are sometimes better for performance. I like this quote by Leigh Caldwell on Stack Overflow: "Loops may achieve a performance gain for your program.

Recursion may achieve a performance gain for your programmer. Choose which is more important in your situation!"

Many important algorithms use recursion, so it's important to understand the concept.

Base case and recursive case

Because a recursive function calls itself, it's easy to write a function incorrectly that ends up in an infinite loop. For example, suppose you want to write a function that prints a countdown, like this:

Code summary: This sequence performs a simple countdown from 3 to 1.

You can write it recursively, like so:

Code summary: The countdown function implements a recursive loop to print a sequence of descending integers, starting from a given value i and continuing until the recursion depth is reached or the process is interrupted.

Write out this code and run it. You'll notice a problem: this function will run forever!

Image summary: A flow diagram showing a recursive process where a block labeled "PRINT i" leads to a block labeled "CALL COUNTDOWN WITH i-1", which then loops back to the print block. This structure illustrates a recursive countdown function that prints a value and then calls itself with a decremented value.

Code summary: This sequence represents a countdown that transitions from positive integers to negative integers, decrementing by one at each step.

(Press Ctrl-C to kill your script.)

Infinite loop

When you write a recursive function, you have to tell it when to stop recursing. That's why every recursive function has two parts: the base case, and the recursive case. The recursive case is when the function calls itself. The base case is when the function doesn't call itself again ... so it doesn't go into an infinite loop.

Let's add a base case to the countdown function:

Code summary: countdown is a recursive function that prints a sequence of descending integers starting from a given input i. It uses a base case to stop execution once the value reaches zero or less, and a recursive case to decrement the value and call itself, effectively counting down to zero.

Now the function works as expected. It goes something like this.

Image summary: A flowchart depicting a recursive countdown function. The process begins by printing the current value i; it then branches to a base case that ends the process if i is less than or equal to 1, or to a recursive case that calls the countdown function again with the value i minus 1. This structure illustrates how a recursive function uses a base case to terminate a repeating loop.

The stack

This section covers the call stack. It's an important concept in programming. The call stack is an important concept in general programming, and it's also important to understand when using recursion.

Suppose you're throwing a barbecue. You keep a todo list for the barbecue, in the form of a stack of sticky notes.

Image summary: A simple line drawing of a stack of papers or a small booklet, with the word "TUDO" written on the top page. It is a basic illustration with no data or analytical result to report.

Remember back when we talked about arrays and lists, and you had a todo list? You could add todo items anywhere to the list or delete random items. The stack of sticky notes is much simpler.

When you insert an item, it gets added to the top of the list. When you read an item, you only read the topmost item, and it's taken off the list. So your todo list has only two actions: push (insert) and pop (remove and read).

Image summary: A diagram illustrating the push and pop operations of a stack data structure. The push operation shows a hand adding a new item to the top of the stack, while the pop operation shows a hand removing and reading the topmost item. The point is to visualize the Last-In, First-Out (LIFO) mechanism of a stack.

Let's see the todo list in action.

Image summary: A three-panel diagram illustrating a stack data structure. The first panel shows a "TODO" item being popped off a stack; the second panel shows the popped item reading "Get Food," which is then broken down into smaller tasks; the third panel shows the new tasks—buns, burgers, and baking a cake—being pushed back onto the stack. The diagram demonstrates how a single high-level task can be expanded into multiple sub-tasks using a Last-In, First-Out (LIFO) stack mechanism.

This data structure is called a stack. The stack is a simple data structure. You've been using a stack this whole time without realizing it!

The call stack

Your computer uses a stack internally called the call stack. Let's see it in action. Here's a simple function:

Code summary: The greet function manages a sequential greeting process by printing a welcome message, triggering a secondary greeting via greet2, and then coordinating the transition to a final farewell through the bye function.

This function greets you and then calls two other functions. Here are those two functions:

Code summary: This script defines two simple utility functions to handle basic social interactions: greet2, which takes a name as an argument to print a personalized greeting, and bye, which prints a standard farewell message.

Let's walk through what happens when you call a function.

Code summary: This snippet provides a conceptual note for a Python example, instructing the reader to treat the print function as if it were not a function for the sake of simplifying the demonstration.

Suppose you call greet("maggie"). First, your computer allocates a box of memory for that function call.

Image summary: A simple line drawing of a rectangular prism or block. It is a basic geometric sketch with no data or analytical result to report.

Now let's use the memory. The variable name is set to "maggie". That needs to be saved in memory.

Image summary: A simple line drawing of a rectangular box or label. The top section contains the word GREET and the bottom section contains the text NAME: MAGGIE. It is a basic illustrative graphic with no data to report.

Every time you make a function call, your computer saves the values for all the variables for that call in memory like this. Next, you print hello, maggie! Then you call greet2("maggie"). Again, your computer allocates a box of memory for this function call.

Image summary: A diagram showing a current function call pointing to a stack of two frames. The top frame is labeled GREET 2 and the bottom frame is labeled GREET, with both frames containing the variable NAME set to MAGGIE. The figure depicts a recursive function call stack where the same function is called multiple times with the same argument.

Your computer is using a stack for these boxes. The second box is added on top of the first one. You print how are you, maggie?

Then you return from the function call. When this happens, the box on top of the stack gets popped off.

Image summary: A sketch showing two rectangular blocks, one labeled GREET and the other GREETZ, both containing a field for NAME with the value MAGGIE. A hand reaches toward the blocks, illustrating a concept of versioning or variation of a greeting function where the input remains the same but the function identifier changes.

Now the topmost box on the stack is for the greet function, which means you returned back to the greet function. When you called the greet2 function, the greet function was partially completed. This is the big idea behind this section: when you call a function from another function, the calling function is paused in a partially completed state.

All the values of the variables for that function are still stored in memory. Now that you're done with the greet2 function, you're back to the greet function, and you pick up where you left off. First you print getting ready to say bye.... You call the bye function.

Image summary: A simple line drawing of a rectangular box containing the words BYE, GREET, and NAME: MAGGIE. This is a conceptual illustration used to represent a data structure or a basic object, with no analytical result to report.

A box for that function is added to the top of the stack. Then you print ok bye! and return from the function call.

Image summary: A simple line drawing showing a hand pushing a block labeled "BYE" on top of another block labeled "GREET" with the name "MAGGIE" written below it. The illustration depicts the process of replacing a greeting with a farewell.

And you're back to the greet function. There's nothing else to be done, so you return from the greet function too. This stack, used to save the variables for multiple functions, is called the call stack.

Exercise

3.1 Suppose I show you a call stack like this.

Image summary: A hand-drawn diagram of a stack of two memory blocks. The top block is labeled GREET2 and the bottom is labeled GREET; both blocks contain a field for NAME assigned to MAGGIE. The diagram illustrates how the same variable name is stored in different memory locations or versions.

What information can you give me, just based on this call stack?

Now let's see the call stack in action with a recursive function.

The call stack with recursion

Recursive functions use the call stack too! Let's look at this in action with the factorial function. factorial (5) is written as 5!, and it's defined like this: 5! = 5 * 4 * 3 * 2 * 1. Similarly, factorial (3) is 3 * 2 * 1. Here's a recursive function to calculate the factorial of a number:

Code summary: This recursive function calculates the factorial of a number x by repeatedly multiplying the current value by the factorial of the value minus one, using a base case of one to terminate the recursion.

Now you call fact (3). Let's step through this call line by line and see how the stack changes. Remember, the topmost box in the stack tells you what call to fact you're currently on.

Table summary: A step-by-step trace of a recursive factorial function call, fact(3), and its corresponding call stack. The process begins with the first call where x is 3, moves through an else block to call fact(x minus 1), and continues until it reaches the base case where x equals 1. The call stack notes emphasize that each function call maintains its own distinct value for the variable x and that the call where x equals 1 is the first to be popped off the stack and return a value.

Image summary: A hand-drawn diagram showing three rectangular blocks labeled FACT, stacked vertically. Each block contains a row divided into two cells, with an X in the left cell and a number (1, 2, or 3) in the right cell. The top block is tilted, as if being placed onto the stack. The diagram illustrates the process of accumulating or stacking individual facts.

Image summary: A hand-drawn diagram illustrating the recursive process of a factorial function call. It shows two states of the call stack: one where x is 2 and returns 2, and a subsequent state where x is 3, which multiplies its value by the returned 2 to return 6. The diagram demonstrates how recursive function calls build upon previous return values to calculate a final result.

Notice that each call to fact has its own copy of x. You can't access a different function's copy of x.

The stack plays a big part in recursion. In the opening example, there were two approaches to find the key. Here's the first way again.

Image summary: A flowchart depicting a recursive search process. Starting with a pile of boxes, the logic dictates that as long as the pile is not empty, the user grabs a box; if that box contains another box, it is added back to the pile, whereas finding a key ends the process. The takeaway is that this creates an infinite loop of searching as long as boxes contain more boxes.

This way, you make a pile of boxes to search through, so you always know what boxes you still need to search.

Image summary: A sketch depicting a pile of boxes, with an arrow pointing to the rightmost box labeled "THE NEXT Box to SEARCH." The illustration serves as a visual metaphor for a sequential search process through a collection of items.

But in the recursive approach, there's no pile.

Image summary: A flowchart depicting a recursive process. The process starts with the instruction to go through every item in a box; if a key is found, the process ends, but if another box is found, the flow loops back to the start to repeat the search within that new box. The takeaway is a visual representation of a recursive search algorithm.

If there's no pile, how does your algorithm know what boxes you still have to look through? Here's an example.

Image summary: A two-part diagram showing a closed box labeled A on the left, followed by an arrow pointing to the same box opened on the right. The opened box reveals two smaller boxes inside, labeled B and C. The illustration depicts a nested structure where Box A contains Boxes B and C.

Image summary: A two-part diagram illustrating a sequence of events. The first part shows a box labeled B with the text "YOU CHECK Box B," and an arrow points to the second part, which shows Box B open to reveal a smaller gift-wrapped box inside with the text "IT CONTAINS Box D." The diagram depicts a nesting scenario where checking one box reveals another inside.

Image summary: A simple diagram showing a wrapped gift box labeled D on the left, an arrow pointing right, and an open, empty box labeled D on the right. The text below describes the sequence: "YOU CHECK Box D" followed by "IT IS EMPTY." The diagram illustrates the process of checking a specific container and finding it void of contents.

At this point, the call stack looks like this.

Image summary: A hand-drawn diagram showing a stack of three boxes labeled Box D, Box B, and Box A. A dashed line encircles the right side of all three boxes, with an arrow and text identifying this area as "BOXES STILL TO CHECK." The diagram illustrates a process of tracking which parts of the boxes remain to be inspected.

The “pile of boxes” is saved on the stack! This is a stack of half-completed function calls, each with its own half-complete list of boxes to look through. Using the stack is convenient because you don't have to keep track of a pile of boxes yourself—the stack does it for you.

Using the stack is convenient, but there's a cost: saving all that info can take up a lot of memory. Each of those function calls takes up some memory, and when your stack is too tall, that means your computer is saving information for many function calls. At that point, you have two options:

• You can rewrite your code to use a loop instead.

• You can use something called tail recursion. That's an advanced recursion topic that is out of the scope of this book. It's also only supported by some languages, not all.

Recap

• Recursion is when a function calls itself.

• Every recursive function has two cases: the base case and the recursive case.

- A stack has two operations: push and pop.

• All function calls go onto the call stack.

• The call stack can get very large, which takes up a lot of memory.

In this chapter

- You learn about divide-and-conquer. Sometimes you'll come across a problem that can't be solved by any algorithm you've learned. When a good algorithmist comes across such a problem, they don't just give up. They have a toolbox full of techniques they use on the problem, trying to come up with a solution. Divide-and-conquer is the first general technique you learn.

- You learn about quicksort, an elegant sorting algorithm that's often used in practice. Quicksort uses divide-and-conquer.

You learned all about recursion in the last chapter. This chapter focuses on using your new skill to solve problems. We'll explore divide and conquer (D&C), a well-known recursive technique for solving problems.

This chapter really gets into the meat of algorithms. After all, an algorithm isn't very useful if it can only solve one type of problem. Instead, D&C gives you a new way to think about solving problems. D&C is another tool in your toolbox. When you get a new problem, you don't have to be stumped. Instead, you can ask, "Can I solve this if I use divide and conquer?"

At the end of the chapter, you'll learn your first major D&C algorithm: quicksort. Quicksort is a sorting algorithm, and a much faster one than selection sort (which you learned in chapter 2). It's a good example of elegant code.

Divide & conquer

D&C can take some time to grasp. So, we'll do three examples. First I'll show you a visual example. Then I'll do a code example that is less pretty but maybe easier. Finally, we'll go through quicksort, a sorting algorithm that uses D&C.

Suppose you're a farmer with a plot of land.

Image summary: A hand-drawn diagram of a rectangular area filled with small, dense marks. The horizontal dimension is labeled as 1680 meters and the vertical dimension is labeled as 640 meters. The image serves to define the physical dimensions of a specific area.

You want to divide this farm evenly into square plots. You want the plots to be as big as possible. So none of these will work.

Image summary: A simple line drawing of a rectangle divided into two equal sections by a vertical line. It is a basic geometric sketch with no data or analytical result to report.

Image summary: A hand-drawn grid of intersecting horizontal and vertical lines forming a series of small rectangles. It is a simple sketch of a grid or mesh, with no data or analytical result to report.

Image summary: A hand-drawn grid consisting of six rectangular sections of varying sizes. It is a simple sketch with no data or analytical result to report.

How do you figure out the largest square size you can use for a plot of land? Use the D&C strategy! D&C algorithms are recursive algorithms. To solve a problem using D&C, there are two steps:

1. Figure out the base case. This should be the simplest possible case.

2. Divide or decrease your problem until it becomes the base case.

Let's use D&C to find the solution to this problem. What is the largest square size you can use?

First, figure out the base case. The easiest case would be if one side was a multiple of the other side.

Image summary: A diagram comparing two geometric representations of an area. On the left, a rectangular region with a width of 50 meters and a height of 25 meters is filled with small dashes; on the right, an equal sign leads to a square with sides of 25 meters by 25 meters, though the top label indicates 25 meters for only half the width. The figure illustrates a mathematical or spatial equivalence between these two areas.

Suppose one side is 25 meters (m) and the other side is 50 m. Then the largest box you can use is 25 m × 25 m. You need two of those boxes to divide up the land.

Now you need to figure out the recursive case. This is where D&C comes in. According to D&C, with every recursive call, you have to reduce your problem. How do you reduce the problem here? Let's start by marking out the biggest boxes you can use.

Image summary: A hand-drawn diagram of a rectangular farm area divided into three sections. The first two sections are labeled as two boxes, each with a width of 640m, and the final section is labeled as farm space still left to split up with a width of 400m; the total height of the area is 640m. The diagram illustrates the current allocation and remaining available space of the farm.

You can fit two 640 times 640 boxes in there, and there's some land still left to be divided. Now here comes the "Aha!" moment. There's a farm segment left to divide. Why don't you apply the same algorithm to this segment?

Image summary: A hand-drawn diagram showing a rectangular plot of land being transformed into a new farmland area. The resulting area is labeled as 400 meters wide and 640 meters long and is designated to be split up. The diagram illustrates the layout and dimensions of land intended for agricultural subdivision.

So you started out with a 1680 times 640 farm that needed to be split up. But now you need to split up a smaller segment, 640 times 400. If you find the biggest box that will work for this size, that will be the biggest box that will work for the entire farm. You just reduced the problem from a 1680 times 640 farm to a 640 times 400 farm!

Euclid's algorithm

“If you find the biggest box that will work for this size, that will be the biggest box that will work for the entire farm.” If it's not obvious to you why this statement is true, don't worry. It isn't obvious. Unfortunately, the proof for why it works is a little too long to include in this book, so you'll just have to believe me that it works. If you want to understand the proof, look up Euclid's algorithm. The Khan academy has a good explanation here: khanacademy dot org U.R.L.

Image summary: A hand-drawn diagram of a rectangle divided into two sections. The total width is labeled 400m, the top section has a height of 240m, and the bottom section has a height of 400m. The drawing serves as a basic geometric layout with specified dimensions.

Let's apply the same algorithm again. Starting with a 640 times 400 meter farm, the biggest box you can create is 400 times 400 meters.

And that leaves you with a smaller segment, 400 times 240 meters.

Image summary: A diagram showing a container partially filled with a substance, with an arrow pointing to a zoomed-in view of the substance's internal structure. The zoomed-in region is labeled with dimensions of 24 micrometers in height and 40 micrometers in width, depicting a dense distribution of small particles. The figure illustrates the microscopic scale and composition of the substance within the container.

And you can draw a box on that to get an even smaller segment, 240 times 160 meters.

Image summary: A diagram showing a transformation from a rectangle to a smaller square. The original rectangle has a height of 240m and a total width composed of a shaded region of 240m and an unshaded region of 160m; it is then converted into a square with a height of 240m and a width of 160m filled with small dashes. The point is to illustrate a reduction in the horizontal dimension of the area.

And then you draw a box on that to get an even smaller segment.

Image summary: A hand-drawn diagram illustrating a base case transformation. A rectangle with a width of 160 meters is divided into a top section of 80 meters and a bottom shaded section of 160 meters; an arrow points to a resulting area of 160 meters by 80 meters filled with small marks. The figure depicts the geometric setup for a base case scenario.

Hey, you're at the base case: 80 is a factor of 160. If you split up this segment using boxes, you don't have anything left over!

Image summary: A hand-drawn diagram of two adjacent squares, each labeled with dimensions of 80m by 80m. The squares are surrounded by radiating dashed lines, suggesting a source of emission or a field of influence centered on the area. The drawing depicts a specific spatial layout with defined dimensions and an associated radiating effect.

So, for the original farm, the biggest plot size you can use is 80 times 80 m.

Image summary: A hand-drawn grid representing a square area, with the top edge and right edge both labeled as 80m. The drawing depicts an 80 meter by 80 meter square region divided into a grid of smaller cells.

To recap, here's how D&C works:

1. Figure out a simple case as the base case.

2. Figure out how to reduce your problem and get to the base case.

D&C isn't a simple algorithm that you can apply to a problem. Instead, it's a way to think about a problem. Let's do one more example.

Image summary: A simple drawing of three adjacent boxes containing the handwritten numbers 2, 4, and 6 in sequence. The image depicts a basic counting or numbering sequence.

You're given an array of numbers.

You have to add up all the numbers and return the total. It's pretty easy to do this with a loop:

Code summary: This function calculates the total sum of a numeric array by iterating through each element and accumulating them into a running total, ultimately returning the final sum.

But how would you do this with a recursive function?

Step 1: Figure out the base case. What's the simplest array you could get? Think about the simplest case, and then read on. If you get an array with 0 or 1 element, that's pretty easy to sum up.

Image summary: A handwritten diagram illustrating the base cases for a summation operation. It shows that for an empty set of elements, the sum is empty, and for a set containing a single element, 7, the sum is 7. The purpose is to define the starting conditions for a recursive or iterative sum.

So that will be the base case.

Step 2: You need to move closer to an empty array with every recursive call. How do you reduce your problem size? Here's one way.

Math summary: This expression calculates the sum of a single value. The operation takes the input value of two hundred forty six and returns it as the final result.

It's the same as this.

Math summary: This expression calculates a final result of twelve. It adds two to the sum of forty six, which is simplified as two plus ten to reach the total.

In either case, the result is 12. But in the second version, you're passing a smaller array into the sum function. That is, you decreased the size of your problem!

Your sum function could work like this.

Image summary: A flow diagram depicting a recursive algorithm for calculating a total sum. It starts with getting a list and then branches: if the list is empty, it returns zero; otherwise, it calculates the total sum as the first number in the list plus the sum of the remaining items. The diagram illustrates the logic of a recursive summation process.

Here it is in action.

: Image summary: A handwritten diagram illustrating a recursive sum function. The left side shows the recursive breakdown of summing the list [2, 4, 6], where the first element is added to the sum of the remaining list until the base case of a single-element list is reached. The right side shows the process of summing those values back up, starting from the base case of 6, adding 4 to get 10, and then adding 2 to reach the final result of 12. The point is to demonstrate how recursion breaks a problem down to a base case and then aggregates the results.

Remember, recursion keeps track of the state.

none of these

none of these function calls complete until you hit the base case!

Image summary: A handwritten diagram illustrating the process of recursive summation for a list containing 2, 4, and 6. The left side shows the recursive descent, where the function sum calls itself repeatedly, peeling off the first element of the list until it reaches the base case of a single-element list. The right side shows the recursive ascent, where the results are summed back up from the base case to reach the final total of 12. The diagram demonstrates how recursion saves the state of partially completed function calls to compute a final result.

this is the first

function call that

actually completes

When you're writing a recursive function involving an array, the base case is often an empty array or an array with one element. If you're stuck, try that first.

Sneak peak at functional programming

“Why would I do this recursively if I can do it easily with a loop?” you may be thinking. Well, this is a sneak peek into functional programming! Functional programming languages like Haskell don't have loops, so you have to use recursion to write functions like this. If you have a good understanding of recursion, functional languages will be easier to learn. For example, here's how you'd write a sum function in Haskell:

Code summary: The sum function calculates the total of a list by recursively adding the head element to the result of processing the remainder of the list, using zero as the base case for an empty list.

Notice that it looks like you have two definitions for the function. The first definition is run when you hit the base case. The second definition runs at the recursive case. You can also write this function in Haskell using an if statement:

: Code summary: This recursive function calculates the total sum of a list of numbers by adding the first element to the sum of the remaining elements, using a base case of zero for empty lists to terminate the recursion.

But the first definition is easier to read. Because Haskell makes heavy use of recursion, it includes all kinds of niceties like this to make recursion easy. If you like recursion, or you're interested in learning a new language, check out Haskell.

Exercises

4.1 Write out the code for the earlier sum function.

4.2 Write a recursive function to count the number of items in a list.

4.3 Find the maximum number in a list.

4.4 Remember binary search from chapter 1? It's a divide-and-conquer algorithm, too. Can you come up with the base case and recursive case for binary search?

Quicksort

Quicksort is a sorting algorithm. It's much faster than selection sort and is frequently used in real life. For example, the C standard library has a function called qsort, which is its implementation of quicksort. Quicksort also uses D&C.

Let's use quicksort to sort an array. What's the simplest array that a sorting algorithm can handle (remember my tip from the previous section)? Well, some arrays don't need to be sorted at all.

Math summary: This expression identifies cases where there is no need to sort arrays. It specifies these cases as an empty array and an array containing only the single element twenty.

..se. You

Code summary: quicksort implements a recursive sorting algorithm that organizes an array by breaking it down into smaller sub-problems. It uses a base case to return arrays with fewer than two elements, as they are already sorted by definition.

Let's look at bigger arrays. An array with two elements is pretty easy to sort, too.

Math summary: This operation performs a comparison between the first and second elements of an array. If the first element is not smaller than the second, the two values are swapped to ensure they are in the correct order.

What about an array of three elements?

Image summary: A simple grid of three boxes containing the handwritten numbers 33, 15, and 10. The image depicts a basic sequence of decreasing numerical values.

Remember, you're using D&C. So you want to break down this array until you're at the base case. Here's how quicksort works. First, pick an element from the array. This element is called the pivot.

We'll talk about how to pick a good pivot later. For now, let's say the first item in the array is the pivot.

Now find the elements smaller than the pivot and the elements larger than the pivot.

: Image summary: A hand-drawn diagram illustrating a partitioning step in a sorting algorithm. A pivot value of 33 is used to divide numbers, with values smaller than 33 (15 and 10) placed in a box to the left and an empty array to the right for numbers greater than 33. The diagram demonstrates the mechanism of partitioning data around a pivot element.

This is called partitioning. Now you have

- A sub-array of all the numbers less than the pivot

• The pivot

- A sub-array of all the numbers greater than the pivot

The two sub-arrays aren't sorted. They're just partitioned. But if they were sorted, then sorting the whole array would be pretty easy.

Image summary: A hand-drawn figure showing three separate shapes containing numbers: a rectangle split into two sections containing 10 and 15, a diamond containing 33, and an empty pair of brackets. It appears to be a set of mathematical or logical puzzles or placeholders.

If the sub-arrays are sorted, then you can combine the whole thing like this—left array + pivot + right array—and you get a sorted array. In this case, it's [10, 15] + [33] + = [10, 15, 33], which is a sorted array.

How do you sort the sub-arrays? Well, the quicksort base case already knows how to sort arrays of two elements (the left sub-array) and empty arrays (the right sub-array). So if you call quicksort on the two sub-arrays and then combine the results, you get a sorted array!

: Code summary: This implementation of quicksort recursively sorts an array by selecting a pivot element and partitioning the remaining elements into two sub-arrays: those smaller than the pivot and those larger. These sub-arrays are sorted independently and then concatenated with the pivot in the middle to produce a fully sorted array.

This will work with any pivot. Suppose you choose 15 as the pivot instead.

Image summary: A simple diagram showing three shapes containing numbers: a square with 10, a diamond with 15, and another square with 33. The image presents a sequence of numbers in different geometric containers.

Both sub-arrays have only one element, and you know how to sort those. So now you know how to sort an array of three elements. Here are the steps:

1. Pick a pivot.

2. Partition the array into two sub-arrays: elements less than the pivot and elements greater than the pivot.

3. Call quicksort recursively on the two sub-arrays.

What about an array of four elements?

Table summary: A set of four values: 33, 10, 15, and 7.

Suppose you choose 33 as the pivot again.

Image summary: A simple hand-drawn diagram of three adjacent rectangular cells containing the numbers 10, 15, and 7 from left to right. It is a basic numeric representation with no analytical result to report.

Image summary: A hand-drawn illustration showing the number 33 inside a diamond shape, followed by a pair of empty square brackets. It is a simple graphic with no data or analytical result to report.

The array on the left has three elements. You already know how to sort an array of three elements: call quicksort on it recursively.

Image summary: A hand-drawn grid of three cells containing the numbers 10, 15, and 7 from left to right. It is a simple numerical illustration with no analytical result to report.

Image summary: A hand-drawn sequence of three shapes containing numbers: a square with 7, a diamond with 10, and another square with 15. The image depicts a simple numerical progression across different geometric forms.

Image summary: A simple drawing showing the number 33 inside a diamond shape, followed by a pair of empty square brackets. It is a basic illustration with no data or analytical result to report.

So you can sort an array of four elements. And if you can sort an array of four elements, you can sort an array of five elements. Why is that? Suppose you have this array of five elements.

Table summary: A sequence of five numerical values: 3, 5, 2, 1, and 4.

Here are all the ways you can partition this array, depending on what pivot you choose.

Math summary: This expression demonstrates the partitioning process used in the quicksort algorithm. It shows an initial array of three, two, one, and four being split into sub-arrays of three, five, and four based on a chosen pivot value.

Image summary: A simple hand-drawn diagram of three adjacent rectangular boxes containing the numbers 3, 2, and 1 from left to right. It is a basic illustrative figure with no data or analytical result to report.

Math summary: This expression identifies a specific constant value. The resulting value is five.

Image summary: A simple diagram of four adjacent boxes containing the numbers 3, 2, 1, and 4 from left to right. It is a basic illustrative figure with no data or analytical result to report.

Image summary: A simple drawing containing a diamond shape with the number 5 inside it, followed by a pair of square brackets. This is a basic visual representation of a number and symbols with no analytical data to report.

Notice that all of these sub-arrays have somewhere between 0 and 4 elements. And you already know how to sort an array of 0 to 4 elements using quicksort! So no matter what pivot you pick, you can call quicksort recursively on the two sub-arrays.

For example, suppose you pick 3 as the pivot. You call quicksort on the sub-arrays.

Image summary: A diagram illustrating the quicksort algorithm process. It shows an initial state with two unsorted subarrays, [2, 1] and [5, 4], separated by a pivot value of 3. The process proceeds through a sorting step where the subarrays are rearranged to [1, 2] and [4, 5], and concludes with the final merged result of [1, 2, 3, 4, 5]. The point is to demonstrate how quicksort recursively partitions and sorts elements around a pivot to achieve a fully sorted list.

The sub-arrays get sorted, and then you combine the whole thing to get a sorted array. This works even if you choose 5 as the pivot.

Image summary: A diagram illustrating the quicksort algorithm process. It shows an initial state where a list containing 3, 2, 1, and 4 is sorted relative to a pivot value of 5, followed by a step where the list is ordered as 1, 2, 3, 4, and finally a combined state where the pivot is appended to the end. The diagram depicts how partitioning and recursion are used to organize elements around a pivot to achieve a fully sorted list.

This works with any element as the pivot. So you can sort an array of five elements. Using the same logic, you can sort an array of six elements, and so on.

Inductive proofs

You just got a sneak peak into inductive proofs! Inductive proofs are one way to prove that your algorithm works. Each inductive proof has two steps: the base case and the inductive case.

Sound familiar? For example, suppose I want to prove that I can climb to the top of a ladder. In the inductive case, if my legs are on a rung, I can put my legs on the next rung. So if I'm on rung 2, I can climb to rung 3. That's the inductive case. For the base case, I'll say that my legs are on rung 1. Therefore, I can climb the entire ladder, going up one rung at a time.

You use similar reasoning for quicksort. In the base case, I showed that the algorithm works for the base case: arrays of size 0 and 1. In the inductive case, I showed that if quicksort works for an array of size 1, it will work for an array of size 2. And if it works for arrays of size 2, it will work for arrays of size 3, and so on. Then I can say that quicksort will work for all arrays of any size. I won't go deeper into inductive proofs here, but they're fun and go hand-in-hand with D&C.

Image summary: A black and white sketch showing a person's legs and feet standing on a step or platform, viewed from a low angle. It is a simple illustration with no data or analytical result to report.

Here's the code for quicksort:

Code summary: quicksort implements a divide-and-conquer sorting algorithm that recursively partitions an array. It uses the first element as a pivot to split the remaining data into two sub-arrays—one containing elements less than or equal to the pivot and another containing elements greater than it. By recursively sorting these partitions and concatenating them around the pivot, the procedure produces a fully ordered version of the original array.

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

Big O notation revisited

Quicksort is unique because its speed depends on the pivot you choose. Before I talk about quicksort, let's look at the most common Big O run times again.

Image summary: A series of line charts and a corresponding table comparing the execution time of five algorithms—Binary Search, Simple Search, Quicksort, Selection Sort, and The Traveling Salesman—as array size increases, assuming a computer speed of 10 operations per second. The charts illustrate the growth rates of these algorithms, ranging from logarithmic to factorial time complexity. The table demonstrates that while algorithms with lower Big O complexity maintain manageable execution times as the input size grows, the Traveling Salesman algorithm in factorial time becomes computationally infeasible almost immediately. The takeaway is that algorithm efficiency significantly dictates performance as data scales.

The example times in this chart are estimates if you perform 10 operations per second. These graphs aren't precise—they're just there to give you a sense of how different these run times are. In reality, your computer can do way more than 10 operations per second.

Each run time also has an example algorithm attached. Check out selection sort, which you learned in chapter 2. It's O (n squared) . That's a pretty slow algorithm.

There's another sorting algorithm called merge sort, which is big O of n log n. Much faster! Quicksort is a tricky case. In the worst case, quicksort takes big O of n squared time.

It's as slow as selection sort! But that's the worst case. In the average case, quicksort takes O(n log n) time. So you might be wondering:

- What do worst case and average case mean here?

• If quicksort is O(n log n) on average, but merge sort is O(n log n) always, why not use merge sort? Isn't it faster?

Merge sort versus quicksort

Suppose you have this simple function to print every item in a list:

Code summary: print_items iterates through a provided list and prints each individual element to the console.

This function goes through every item in the list and prints it out. Because it loops over the whole list once, this function runs in O(n) time. Now, suppose you change this function so it sleeps for 1 second before it prints out an item:

Code summary: print_items2 iterates through a provided list and prints each element individually, introducing a one-second delay between prints to pace the output.

Before it prints out an item, it will pause for 1 second. Suppose you print a list of five items using both functions.

Table summary: A sequence of even numbers increasing from 2 to 10.

print items: 246810

: Code summary: print_items2 outputs a sequence of even numbers from 2 to 10, with each value separated by a sleep command to introduce a delay between prints.

Both functions loop through the list once, so they're both O(n) time. Which one do you think will be faster in practice? I think print items will be much faster because it doesn't pause for 1 second before printing an item. So even though both functions are the same speed in Big O notation, print items is faster in practice. When you write Big O notation like O(n) , it really means this.

C*n

some

fixed amount

of Time c is some fixed amount of time that your algorithm takes. It's called the constant. For example, it might be 10 milliseconds times n for print items versus 1 second times n for print items2.

You usually ignore that constant, because if two algorithms have different Big O times, the constant doesn't matter. Take binary search and simple search, for example. Suppose both algorithms had these constants.

Math summary: This expression compares the execution times of simple search and binary search. It calculates the simple search time as ten milliseconds multiplied by the number of elements and the binary search time as one second multiplied by the logarithm of the number of elements.

You might say, “Wow! Simple search has a constant of 10 milliseconds, but binary search has a constant of 1 second. Simple search is way faster!” Now suppose you're searching a list of 4 billion elements. Here are the times.

Simple Search

Binary Search

Math summary: This calculation compares the total time required for two different processes. It shows that ten milliseconds multiplied by four billion equals four hundred sixty three days, while one second multiplied by thirty two equals thirty two seconds.

As you can see, binary search is still way faster. That constant didn't make a difference at all.

But sometimes the constant can make a difference. Quicksort versus merge sort is one example. Quicksort has a smaller constant than merge sort. So if they're both O(n log n) time, quicksort is faster. And quicksort is faster in practice because it hits the average case way more often than the worst case.

So now you're wondering: what's the average case versus the worst case?

Average case versus worst case

The performance of quicksort heavily depends on the pivot you choose. Suppose you always choose the first element as the pivot. And you call quicksort with an array that is already sorted.

Quicksort doesn't check to see whether the input array is already sorted. So it will still try to sort it.

Image summary: A diagram illustrating the worst-case scenario of a quicksort algorithm on a sorted array of numbers 1 through 8. The sequence shows that when the first element is consistently picked as the pivot, the array is partitioned into one empty list and a remaining list that decreases by only one element per step. This results in a total call stack height of 8, demonstrating that picking the first element as a pivot for sorted data leads to maximum recursion depth.

Notice how you're not splitting the array into two halves. Instead, one of the sub-arrays is always empty. So the call stack is really long.

Now instead, suppose you always picked the middle element as the pivot. Look at the call stack now.

Image summary: A diagram illustrating a recursive divide-and-conquer process applied to a sequence of numbers from 1 to 8. The sequence is repeatedly split into smaller halves, with individual elements eventually isolated, while a bracket on the right indicates that the size of the call stack reaches 4. The figure demonstrates how a problem is broken down into smaller sub-problems through recursive splitting.

It's so short! Because you divide the array in half every time, you don't need to make as many recursive calls. You hit the base case sooner, and the call stack is much shorter.

The first example you saw is the worst-case scenario, and the second example is the best-case scenario. In the worst case, the stack size is O(n) . In the best case, the stack size is O(log n) .

Now look at the first level in the stack. You pick one element as the pivot, and the rest of the elements are divided into sub-arrays. You touch all eight elements in the array.

So this first operation takes O(n) time. You touched all eight elements on this level of the call stack. But actually, you touch O(n) elements on every level of the call stack.

Image summary: A diagram illustrating a process where elements from a list numbered 1 through 8 are moved one by one from a right-hand queue into a left-hand bracket. The sequence shows the elements 1 through 7 being shifted individually across a diamond-shaped transition point. The point is to demonstrate a linear time complexity, denoted as O(n), for processing these elements.

Even if you partition the array differently, you're still touching O(n) elements every time.

Image summary: A diagram illustrating a recursive partitioning process of a sequence of 8 elements. The sequence is split into two halves, and then further subdivided into smaller segments and individual elements across multiple levels. The annotations indicate that at each stage of the division, the total number of elements remains O(n), demonstrating that the space complexity is linear despite the recursive splitting.

So each level takes big O of n time to complete.

Image summary: A diagram illustrating a divide-and-conquer process, such as merge sort, where an initial array of 8 elements is repeatedly split into smaller subarrays across multiple levels. Each level of division is labeled as taking O(n) time, and the total number of levels is labeled as O(log n). The figure demonstrates that the overall time complexity is derived from the product of the work per level and the total number of levels.

In this example, there are big O of log n levels (the technical way to say that is, 01c The height of the call stack is big O of log n01d). And each level takes big O of n time. The entire algorithm will take big O of n times big O of log n equals big O of n log n time. This is the best-case scenario.

In the worst case, there are big O of n levels, so the algorithm will take big O of n times big O of n equals big O of n squared time.

Well, guess what? I'm here to tell you that the best case is also the average case. If you always choose a random element in the array as the pivot, quicksort will complete in O(n log n) time on average. Quicksort is one of the fastest sorting algorithms out there, and it's a very good example of D&C.

How long would each of these operations take in Big O notation?

4.5 Printing the value of each element in an array.

4.6 Doubling the value of each element in an array.

4.7 Doubling the value of just the first element in an array.

4.8 Creating a multiplication table with all the elements in the array. So if your array is [2, 3, 7, 8, 10], you first multiply every element by 2, then multiply every element by 3, then by 7, and so on.

Recap

- D&C works by breaking a problem down into smaller and smaller pieces. If you're using D&C on a list, the base case is probably an empty array or an array with one element.

• If you're implementing quicksort, choose a random element as the pivot. The average runtime of quicksort is O(n log n) !

- The constant in Big O notation can matter sometimes. That's why quicksort is faster than merge sort.

- The constant almost never matters for simple search versus binary search, because big O of log n is so much faster than big O of n when your list gets big.

In this chapter

- You learn about hash tables, one of the most useful basic data structures. Hash tables have many uses; this chapter covers the common use cases.

- You learn about the internals of hash tables: implementation, collisions, and hash functions. This will help you understand how to analyze a hash table's performance.

Suppose you work at a grocery store. When a customer buys produce, you have to look up the price in a book. If the book is unalphabetized, it can take you a long time to look through every single line for apple. You'd be doing simple search from chapter 1, where you have to look at every line.

Do you remember how long that would take? O(n) time. If the book is alphabetized, you could run binary search to find the price of an apple. That would only take O(log n) time.

Image summary: A handwritten list of grocery items and their prices, showing eggs at 2.49$, milk at 1.99$, and a pear at 79$. The image serves as a simple example of a list of items with associated costs.

Image summary: A line chart showing list size on the vertical axis and time on the horizontal axis. The curve rises steeply at first and then levels off, continuing to increase at a slower rate. The point is to illustrate a growth pattern with O(n) complexity.

Image summary: A hand-drawn list of three grocery items and their prices: a pear for 79 cents, eggs for 2.49 dollars, and milk for 1.99 dollars. The image serves as a simple example of a price list.

: Image summary: A line chart plotting list size against time, showing a straight line that rises linearly from the origin. The figure illustrates a linear time complexity of O(n).

As a reminder, there's a big difference between O(n) and O(log n) time! Suppose you could look through 10 lines of the book per second. Here's how long simple search and binary search would take you.

Table summary: A comparison of time complexity between linear search, O(n), and binary search, O(log n), for different book sizes. For 100 items, linear search takes 10 per second, while binary search takes 1 per second, requiring 7 lines. For a larger range of 10,000 to 100,000 items, linear search takes between 1.66 and 16.6 minutes, whereas binary search remains efficient, taking 0.5 seconds for 1,000 items with 10 lines, and 2 seconds for 10,000 items with 14 lines.

You already know that binary search is darn fast. But as a cashier, looking things up in a book is a pain, even if the book is sorted. You can feel the customer steaming up as you search for items in the book. What you really need is a buddy who has all the names and prices memorized. Then you don't need to look up anything: you ask her, and she tells you the answer instantly.

Your buddy Maggie can give you the price in O (1) time for any item, no matter how big the book is. She's even faster than binary search.

Table summary: MAGGIE provides the fastest search performance, remaining instant regardless of the number of items in the book. In contrast, SIMPLE SEARCH slows down significantly as the item count increases, rising from 10 seconds to 16.6 minutes. BINARY SEARCH remains efficient, staying between 10 and 20 seconds across the same range. The theoretical time complexities are listed as O(1) for MAGGIE, O(logn) for BINARY SEARCH, and O(n) for SIMPLE SEARCH.

What a wonderful person! How do you get a “Maggie”?

Let's put on our data structure hats. You know two data structures so far: arrays and lists (I won't talk about stacks because you can't really "search" for something in a stack). You could implement this book as an array.

Table summary: Prices for three grocery items, with EGGS at 2.49, MILK at 1.49, and PEAR at 0.79.

Each item in the array is really two items: one is the name of a kind of produce, and the other is the price. If you sort this array by name, you can run binary search on it to find the price of an item. So you can find items in O ( log n ) time. But you want to find items in O (1) time. That is, you want to make a “Maggie.” That's where hash functions come in.

Hash functions

A hash function is a function where you put in a string and you get back a number.

Math summary: This expression demonstrates a hash function that maps input strings to numeric outputs. It shows the words Namaste, Hola, and Hello being transformed through a hashing process to produce specific results, including the number four and the number two.

In technical terminology, we'd say that a hash function "maps strings to numbers." You might think there's no discernable pattern to what number you get out when you put a string in. But there are some requirements for a hash function:

- It needs to be consistent. For example, suppose you put in “apple” and get back “4”. Every time you put in “apple”, you should get “4” back. Without this, your hash table won't work.

- It should map different words to different numbers. For example, a hash function is no good if it always returns “1” for any word you put in. In the best case, every different word should map to a different number.

So a hash function maps strings to numbers. What is that good for? Well, you can use it to make your “Maggie”!

Start with an empty array:

Image summary: A diagram of a horizontal row of five adjacent boxes, labeled from left to right with the empty set symbol, then the numbers 1, 2, 3, and 4. The image depicts a simple ordered sequence of five indexed slots.

You'll store all of your prices in this array. Let's add the price of an apple. Feed "apple" into the hash function.

Image summary: A diagram showing a string, "APPLE", passing through a bow-tie shaped neural network structure to produce the output 3. This illustrates a process where a text input is mapped to a numerical value through a model.

The hash function outputs “3”. So let's store the price of an apple at index 3 in the array.

Table summary: The value for Apple is 0.67, with an additional row containing the values 1, 2, 3, and 4.

Let's add milk. Feed “milk” into the hash function. “Milk” goes to C 6 H 6 goes to C 6 H 6

The hash function says “0”. Let's store the price of milk at index 0.

Table summary: A comparison between MILK and APPLE, where MILK has a value of 1.49 and APPLE has a value of 0.67, with a reference to phi values 1, 2, 3, and 4.

Keep going, and eventually the whole array will be full of prices.

Table summary: A sequence of five numerical values: 1.49, 0.79, 2.49, 0.67, and 1.49.

Now you ask, “Hey, what's the price of an avocado?” You don't need to search for it in the array. Just feed “avocado” into the hash function.

Image summary: A diagram showing the word "AVOCADO" passing through a bow-tie shaped process and resulting in the number 4. This illustrates a process that transforms a text input into a numerical output.

It tells you that the price is stored at index 4. And sure enough, there it is.

Avocado = 1.41 , , , The hash function tells you exactly where the price is stored, so you don't have to search at all! This works because

Table summary: A sequence of five numerical values: 1.49, 0.79, 2.49, 0.67, and 1.49.

- The hash function consistently maps a name to the same index. Every time you put in “avocado”, you'll get the same number back. So you can use it the first time to find where to store the price of an avocado, and then you can use it to find where you stored that price.

- The hash function maps different strings to different indexes. “Avocado” maps to index 4. “Milk” maps to index 0. Everything maps to a different slot in the array where you can store its price.

- The hash function knows how big your array is and only returns valid indexes. So if your array is 5 items, the hash function doesn't return 100 ... that wouldn't be a valid index in the array.

You just built a “Maggie”! Put a hash function and an array together, and you get a data structure called a hash table. A hash table is the first data structure you'll learn that has some extra logic behind it. Arrays and lists map straight to memory, but hash tables are smarter. They use a hash function to intelligently figure out where to store elements.

Hash tables are probably the most useful complex data structure you'll learn. They're also known as hash maps, maps, dictionaries, and associative arrays. And hash tables are fast!

Remember our discussion of arrays and linked lists back in chapter 2? You can get an item from an array instantly. And hash tables use an array to store the data, so they're equally fast.

You'll probably never have to implement hash tables yourself. Any good language will have an implementation for hash tables. Python has hash tables; they're called dictionaries. You can make a new hash table using the dict function:

>>> book = dict()

book is a new hash table. Let's add some prices to book:

{'avocado': 1.49, 'apple': 0.67, 'milk': 1.49}

Image summary: A hand-drawn table listing three items and their prices: an apple for 0.67, milk for 1.49, and an avocado for 1.49. The image serves as a simple price list.

Pretty easy! Now let's ask for the price of an avocado:

Code summary: This snippet demonstrates how to access and print a specific value from a dictionary named book using the key avocado, resulting in the output of the item's price.

A hash table has keys and values. In the book hash, the names of produce are the keys, and their prices are the values. A hash table maps keys to values.

In the next section, you'll see some examples where hash tables are really useful.

Exercises

It's important for hash functions to consistently return the same output for the same input. If they don't, you won't be able to find your item after you put it in the hash table!

Which of these hash functions are consistent?

5.1 f of x equals 1 from Returns "1" for all input

5.2 f of x equals rand() arrow Returns a random number every time

5.3 f of x equals next empty slot() from Returns the index of the next empty slot in the hash table

5.4 f(x) = len(x) from Uses the length of the string as the index empty slot in the hash table

Use cases

Hash tables are used everywhere. This section will show you a few use cases.

Using hash tables for lookups

Your phone has a handy phonebook built in.

Each name has a phone number associated with it.

Bade Mama arrow 581 66 empty set 982 empty set

Alex Manning to 484 234 468 empty set

Jane Marin to 415 567 3579 Suppose you want to build a phone book like this. You're mapping people's names to phone numbers. Your phone book needs to have this functionality:

Image summary: A drawing of a smartphone displaying a contacts list under the heading "ALL CONTACTS". The list shows names starting with the letter M, including Bade Mama, Alex Manning, Jane Marin, Shefali Mausi, and Sabeen Minns. It is a simple illustration depicting a digital address book.

• Add a person's name and the phone number associated with that person.

- Enter a person's name, and get the phone number associated with that name.

This is a perfect use case for hash tables! Hash tables are great when you want to

- Create a mapping from one thing to another thing

• Look something up

Building a phone book is pretty easy. First, make a new hash table:

Code summary: This procedure initializes an empty dictionary named phone_book to serve as a data structure for storing and retrieving contact information.

By the way, Python has a shortcut for making a new hash table. You can use two curly braces:

Code summary: This snippet demonstrates that initializing an empty dictionary using curly braces is functionally equivalent to calling the dict constructor to create a phone book data structure.

Let's add the phone numbers of some people into this phone book:

Code summary: This snippet demonstrates how to populate a dictionary, acting as a phone book, by mapping specific string keys to their corresponding integer phone number values.

That's all there is to it! Now, suppose you want to find Jenny's phone number. Just pass the key in to the hash:

Code summary: This snippet demonstrates a basic dictionary lookup in Python, retrieving and printing the phone number associated with the key "jenny" from a phone book data structure.

Imagine if you had to do this using an array instead.

Image summary: A simple line drawing of a contact card or identification tag divided into four quadrants. The top row contains the name "JENNY" and the phone number "8675309", while the bottom row contains the label "EMERGENCY" and the number "911". The image serves as a humorous or illustrative depiction of emergency contact information.

How would you do it? Hash tables make it easy to model a relationship from one item to another.

Hash tables are used for lookups on a much larger scale. For example, suppose you go to a website like adit dot io. Your computer has to translate adit dot io to an I.P address.

Adit dot 10 to 173.255.248.55

For any website you go to, the address has to be translated to an I.P address.

google dot com arrow 74.125.239.133

facebook dot com goes to 173.252.120.6

scribd dot com goes to 23.235.47.175

Wow, mapping a web address to an I.P address? Sounds like a perfect use case for hash tables! This process is called D.N.S resolution. Hash tables are one way to provide this functionality.

Preventing duplicate entries

Suppose you're running a voting booth. Naturally, every person can vote just once. How do you make sure they haven't voted before?

When someone comes in to vote, you ask for their full name. Then you check it against the list of people who have voted.

Image summary: A simple drawing of a clipboard with a list titled VOTERS, containing the names Jim, Pam, and Mike. It is an illustrative image with no data or analytical result to report.

If their name is on the list, this person has already voted—kick them out! Otherwise, you add their name to the list and let them vote. Now suppose a lot of people have come in to vote, and the list of people who have voted is really long.

Image summary: A simple line drawing of a clipboard holding a list titled "VOTERS" with the names Jim, Pam, Mike, Mindy, and BJ written on it, resting atop a stack of several other papers. It is an illustration depicting a voter registration or check-in list.

Each time someone new comes in to vote, you have to scan this giant list to see if they've already voted. But there's a better way: use a hash! First, make a hash to keep track of the people who have voted:

: Code summary: This line initializes an empty dictionary named voted, which is typically used to track and store unique identifiers to prevent duplicate voting or to record the voting status of participants.

When someone new comes in to vote, check if they're already in the hash:

Code summary: This operation retrieves the voting value associated with the key "tom" from the voted dictionary, allowing the program to check if a specific individual has cast a vote.

The get function returns the value if “tom” is in the hash table. Otherwise, it returns None. You can use this to check if someone has already voted!

Image summary: A flowchart and accompanying Python code snippet illustrating a voting check process. The flowchart shows that when a person comes to vote, the system checks if they are in a hash; if yes, they are kicked out, and if no, they are allowed to vote and their name is added to the hash. The code implements this logic using a dictionary named voted and a function check_voter. The point is to demonstrate how a hash map can be used to prevent duplicate voting.

: Code summary: This procedure manages a voting registry to prevent duplicate entries. It uses a dictionary to track whether a person has already voted; if the name is found, it denies access, otherwise, it records the name and allows the vote to proceed.

Code summary: This procedure manages voter eligibility by tracking who has already participated. It allows a voter to proceed on their first attempt but denies access and triggers a removal action if the same voter attempts to vote a second time.

The first time Tom goes in, this will print, “let them vote!” Then Mike goes in, and it prints, “let them vote!” Then Mike tries to go a second time, and it prints, “kick them out!”

Remember, if you were storing these names in a list of people who have voted, this function would eventually become really slow, because it would have to run a simple search over the entire list. But you're storing their names in a hash table instead, and a hash table instantly tells you whether this person's name is in the hash table or not. Checking for duplicates is very fast with a hash table.

Using hash tables as a cache

One final use case: caching. If you work on a website, you may have heard of caching before as a good thing to do. Here's the idea. Suppose you visit facebook dot com:

1. You make a request to Facebook's server.

2. The server thinks for a second and comes up with the web page to send to you.

3. You get a web page.

Image summary: A hand-drawn diagram showing a sequence of events starting with a user, who sends a request to a server. The server then performs work, resulting in the delivery of a web page. The diagram illustrates the basic request-response mechanism of how a user accesses a web page via a server.

For example, on Facebook, the server may be collecting all of your friends' activity to show you. It takes a couple of seconds to collect all that activity and shows it to you. That couple of seconds can feel like a long time as a user. You might think, "Why is Facebook being so slow?" On the other hand, Facebook's servers have to serve millions of people, and that couple of seconds adds up for them. Facebook's servers are really working hard to serve all of those websites. Is there a way to make Facebook faster and have its servers do less work at the same time?

Suppose you have a niece who keeps asking you about planets. “How far is Mars from Earth?” “How far is the Moon?” “How far is Jupiter?” Each time, you have to do a Google search and give her an answer. It takes a couple of minutes. Now, suppose she always asked, “How far is the Moon?” Pretty soon, you'd memorize that the Moon is 238,900 miles away. You wouldn't have to look it up on Google … you'd just remember and answer. This is how caching works: websites remember the data instead of recalculating it.

If you're logged in to Facebook, all the content you see is tailored just for you. Each time you go to facebook dot com, its servers have to think about what content you're interested in. But if you're not logged in to Facebook, you see the login page. Everyone sees the same login page.

Facebook is asked the same thing over and over: "Give me the home page when I'm logged out." So it stops making the server do work to figure out what the home page looks like. Instead, it memorizes what the home page looks like and sends it to you.

Image summary: A diagram comparing two user experiences for accessing a web page. When not logged in, a user interacts with a computer to receive a saved web page. When logged in, the process includes an intermediate step where a server performs work before delivering the web page. The point is to illustrate that logging in triggers server-side processing to generate the page.

This is called caching. It has two advantages:

You get the web page a lot faster, just like when you memorized the distance from Earth to the Moon. The next time your niece asks you, you won't have to Google it. You can answer instantly.

• Facebook has to do less work.

Caching is a common way to make things faster. All big websites use caching. And that data is cached in a hash!

Facebook isn't just caching the home page. It's also caching the About page, the Contact page, the Terms and Conditions page, and a lot more. So it needs a mapping from page U.R.L to page data.

: Code summary: This mapping defines a routing system that associates specific URLs with their corresponding data sources, ensuring that requests for the about page and the home page return the correct respective datasets.

When you visit a page on Facebook, it first checks whether the page is stored in the hash.

Image summary: A flow chart depicting a caching process. It begins with a request for a URL from Facebook, followed by a decision step asking if the URL is in the hash. If yes, the system sends the data from the cache; if no, the server must perform work to retrieve the data. The diagram illustrates how a cache is used to avoid redundant server processing.

Here it is in code:

Code summary: This procedure implements a basic caching mechanism to reduce redundant network requests. It first checks if the requested URL exists in a local cache to provide an immediate response; if not, it fetches the data from a server and stores it in the cache for future use before returning the result.

Here, you make the server do work only if the U.R.L isn't in the cache. Before you return the data, though, you save it in the cache. The next time someone requests this U.R.L, you can send the data from the cache instead of making the server do the work.

To recap, hashes are good for

- Modeling relationships from one thing to another thing

• Filtering out duplicates

- Caching/memorizing data instead of making your server do work

Collisions

Like I said earlier, most languages have hash tables. You don't need to know how to write your own. So, I won't talk about the internals of hash tables too much.

But you still care about performance! To understand the performance of hash tables, you first need to understand what collisions are. The next two sections cover collisions and performance.

First, I've been telling you a white lie. I told you that a hash function always maps different keys to different slots in the array.

Image summary: A diagram showing three input strings, "MILK", "APPLE", and "AVOCADO", passing through a hash function and being mapped to different slots in a vertical array. This illustrates how a hash function transforms variable-length keys into specific indices for storage in a hash table.

In reality, it's almost impossible to write a hash function that does this. Let's take a simple example. Suppose your array contains 26 slots.

Image summary: A hand-drawn number line consisting of a horizontal line divided into equal segments by vertical tick marks, labeled with integers from 0 to 25. It is a basic mathematical diagram used to represent a sequence of whole numbers.

And your hash function is really simple: it assigns a spot in the array alphabetically.

Image summary: A hand-drawn diagram of a horizontal array of 26 numbered cells, from 0 to 25. Arrows point to the first few and last few cells, indicating that letters A through Z are mapped sequentially to these positions. The diagram illustrates the mapping of an alphabet to a zero-indexed numerical sequence.

0.67 ... Maybe you can already see the problem. You want to put the price of apples in your hash. You get assigned the first slot.

Then you want to put the price of bananas in the hash. You get assigned the second slot.

Image summary: A hand-drawn diagram showing a sequence of memory cells containing the values 0.67 and 0.39, with arrows labeling these cells as 'APPLES' and 'BANANAS' respectively. The diagram illustrates how specific data values are mapped to corresponding labels in a memory structure.

Everything is going so well! But now you want to put the price of avocados in your hash. You get assigned the first slot again.

Image summary: A hand-drawn diagram of a vector or array containing numerical values, with the first two elements labeled 0.67 and 0.39. Arrows point from the words APPLES? and AVOCADOS? toward the first element, and from BANANAS toward the second element. The diagram depicts the representation of words as numerical values in a vector space.

Oh no! Apples have that slot already! What to do? This is called a collision: two keys have been assigned the same slot. This is a problem. If you store the price of avocados at that slot, you'll overwrite the price of apples. Then the next time someone asks for the price of apples, they will get the price of avocados instead!

Collisions are bad, and you need to work around them. There are many different ways to deal with collisions. The simplest one is this: if multiple keys map to the same slot, start a linked list at that slot.

Image summary: A hand-drawn diagram of a linked list structure. A vertical list contains a value for the price of bananas, which points to a node for apples with a value of 0.67, which in turn points to a node for avocados with a value of 1.49. The diagram illustrates how data elements are connected sequentially via pointers in a linked list.

In this example, both “apple” and “avocado” map to the same slot. So you start a linked list at that slot. If you need to know the price of bananas, it's still quick.

If you need to know the price of apples, it's a little slower. You have to search through this linked list to find “apple”. If the linked list is small, no big deal—you have to search through three or four elements.

But suppose you work at a grocery store where you only sell produce that starts with the letter A.

Image summary: A diagram showing a vertical column of slots labeled A through E, where only slot A is linked to a horizontal sequence of items including apples, avocados, almonds, and advil. A bracket encompasses slots B through E with the text "ALL OF THESE SLOTS ARE WASTED," illustrating the inefficiency of utilizing only one available slot in a multi-slot system.

Hey, wait a minute! The entire hash table is totally empty except for one slot. And that slot has a giant linked list! Every single element in this hash table is in the linked list.

That's as bad as putting everything in a linked list to begin with. It's going to slow down your hash table.

There are two lessons here:

- Your hash function is really important. Your hash function mapped all the keys to a single slot. Ideally, your hash function would map keys evenly all over the hash.

- If those linked lists get long, it slows down your hash table a lot. But they won't get long if you use a good hash function!

Hash functions are important. A good hash function will give you very few collisions. So how do you pick a good hash function? That's coming up in the next section!

Performance

You started this chapter at the grocery store. You wanted to build something that would give you the prices for produce instantly. Well, hash tables are really fast.

In the average case, hash tables take O (1) for everything. O (1) is called constant time. You haven't seen constant time before. It doesn't mean instant. It means the time taken will stay the same, regardless of how big the hash table is. For example, you know that simple search takes linear time.

Table summary: Time complexities for SEARCH, INSERT, and DELETE operations. For the first configuration, all three operations are O(1), while for the second configuration, all three operations are O(n).

Image summary: A hand-drawn graph showing a straight line increasing diagonally from the origin. The image is labeled O(n), LINEAR TIME, and (SIMPLE SEARCH), illustrating that the time complexity of a simple search increases linearly with the size of the input.

Binary search is faster—it takes log time:

Image summary: A hand-drawn graph showing a curve that rises and then flattens, labeled with the Big O notation O(log n) and the text "LOG TIME (BINARY SEARCH)". The image illustrates the logarithmic time complexity characteristic of a binary search algorithm.

Looking something up in a hash table takes constant time.

Image summary: A simple line chart showing a nearly flat line along the x-axis, which is labeled O(1). This depicts a constant time or space complexity, indicating that the resource requirement remains the same regardless of the input size.

See how it's a flat line? That means it doesn't matter whether your hash table has 1 element or 1 billion elements—getting something out of a hash table will take the same amount of time. Actually, you've seen constant time before. Getting an item out of an array takes constant time. It doesn't matter how big your array is; it takes the same amount of time to get an element. In the average case, hash tables are really fast.

In the worst case, a hash table takes O(n) —linear time—for everything, which is really slow. Let's compare hash tables to arrays and lists.

Table summary: Support for SEARCH, INSERT, and DELETE operations across four configurations. SEARCH is supported as both 1 and n across all configurations. INSERT and DELETE share the same support patterns, where they are supported as 1 and n in the first two configurations, but switch to n and 1 in the final two.

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!

But in the worst case, hash tables are slow at all of those. So it's important that you don't hit worst-case performance with hash tables. And to do that, you need to avoid collisions. To avoid collisions, you need

• A low load factor

• A good hash function

Note

Before you start this next section, know that this isn't required reading. I'm going to talk about how to implement a hash table, but you'll never have to do that yourself. Whatever programming language you use will have an implementation of hash tables built in. You can use the built-in hash table and assume it will have good performance. The next section gives you a peek under the hood.

Load factor

The load factor of a hash table is easy to calculate.

Number of items

in Hash Table

Total Number

of Slots

Hash tables use an array for storage, so you count the number of occupied slots in an array. For example, this hash table has a load factor of 2 over 5 , or 0.4.

Image summary: A hand-drawn diagram of a memory array or buffer consisting of five cells. Two arrows point from the word "OCCUPIED" to the second cell, which contains the number 1, and the fourth cell, which contains a null symbol. The diagram illustrates how specific slots in a data structure are marked as occupied.

What's the load factor of this hash table?

Image summary: A hand-drawn diagram showing a rectangular container divided into three sections, with the middle section containing the text "2" and the text "LOAD FACTOR?" written below the container. The image is a conceptual sketch used to pose a question about calculating the load factor of a data structure.

If you said 1 over 3 , you're right. Load factor measures how many empty slots remain in your hash table.

Suppose you need to store the price of 100 produce items in your hash table, and your hash table has 100 slots. In the best case, each item will get its own slot.

Image summary: A hand-drawn diagram showing a sequence of boxes containing numbers, with the first box labeled as the price of milk and the second as the price of an apple. The sequence continues with an ellipsis, illustrating a way to represent a list of different prices in a structured format.

This hash table has a load factor of 1. What if your hash table has only 50 slots? Then it has a load factor of 2. There's no way each item will get its own slot, because there aren't enough slots! Having a load factor greater than 1 means you have more items than slots in your array. Once the load factor starts to grow, you need to add more slots to your hash table.

This is called resizing. For example, suppose you have this hash table that is getting pretty full.

Image summary: A hand-drawn diagram of a four-cell array or memory buffer containing the numbers 4, 3, and 1 in the first three cells, with the fourth cell left empty. A bracket spans the entire length of the array, indicating that these cells together form a single grouped entity.

You need to resize this hash table. First you create a new array that's bigger. The rule of thumb is to make an array that is twice the size.

Image summary: A hand-drawn diagram showing a long rectangle divided into eight smaller, roughly equal rectangular sections. It is a simple schematic with no data or labels, depicting a segmented bar or sequence.

Now you need to re-insert all of those items into this new hash table using the hash function:

Table summary: A set of numerical values including 4, 1, and 3.

This new table has a load factor of 3 over 8 . Much better! With a lower load factor, you'll have fewer collisions, and your table will perform better. A good rule of thumb is, resize when your load factor is greater than 0.7.

You might be thinking, “This resizing business takes a lot of time!” And you're right. Resizing is expensive, and you don't want to resize too often. But averaged out, hash tables take O (1) even with resizing.

A good hash function

A good hash function distributes values in the array evenly.

Table summary: A sequence of numerical values including 2, 6, 4, 10, and 12, with three empty entries interspersed.

A bad hash function groups values together and produces a lot of collisions.

Image summary: A diagram of a hash table showing a main array of buckets, where the first two buckets contain pointers to separate linked lists. The first list contains two nodes with values 2 and 4, while the second list contains three nodes with values 12, 10, and 6. This structure illustrates how a hash table handles collisions by using chaining to store multiple elements at the same index.

What is a good hash function? That's something you'll never have to worry about—old men (and women) with big beards sit in dark rooms and worry about that. If you're really curious, look up the S.H.A function (there's a short description of it in the last chapter). You could use that as your hash function.

It's important for hash functions to have a good distribution. They should map items as broadly as possible. The worst case is a hash function that maps all items to the same slot in the hash table.

Suppose you have these four hash functions that work with strings:

A. Return “1” for all input.

B. Use the length of the string as the index.

c. Use the first character of the string as the index. So, all strings starting with a are hashed together, and so on.

D. Map every letter to a prime number: a = 2, b = 3, c = 5, d = 7, e = 11, and so on. For a string, the hash function is the sum of all the characters modulo the size of the hash. For example, if your hash size is 10, and the string is “bag”, the index is 3 + 2 + 17% 10 = 22% 10 = 2.

For each of these examples, which hash functions would provide a good distribution? Assume a hash table size of 10 slots.

5.5 A phonebook where the keys are names and values are phone numbers. The names are as follows: Esther, Ben, Bob, and Dan.

5.6 A mapping from battery size to power. The sizes are A, A.A, A.A.A, and A.A.A.A.

5.7 A mapping from book titles to authors. The titles are Maus, Fun Home, and Watchmen.

Recap

You'll almost never have to implement a hash table yourself. The programming language you use should provide an implementation for you. You can use Python's hash tables and assume that you'll get the average case performance: constant time.

Hash tables are a powerful data structure because they're so fast and they let you model data in a different way. You might soon find that you're using them all the time:

- You can make a hash table by combining a hash function with an array.

- Collisions are bad. You need a hash function that minimizes collisions.

- Hash tables have really fast search, insert, and delete.

- Hash tables are good for modeling relationships from one item to another item.

- Once your load factor is greater than 0.07, it's time to resize your hash table.

- Hash tables are used for caching data (for example, with a web server).

- Hash tables are great for catching duplicates.

In this chapter

- You learn how to model a network using a new, abstract data structure: graphs.

- You learn breadth-first search, an algorithm you can run on graphs to answer questions like, "What's the shortest path to go to X?"

- You learn about directed versus undirected graphs.

- You learn topological sort, a different kind of sorting algorithm that exposes dependencies between nodes.

This chapter introduces graphs. First, I'll talk about what graphs are (they don't involve an X or Y axis). Then I'll show you your first graph algorithm. It's called breadth-first search B.F.S.

Breadth-first search allows you to find the shortest distance between two things. But shortest distance can mean a lot of things! You can use breadth-first search to

- Write a checkers A.I that calculates the fewest moves to victory

- Write a spell checker (fewest edits from your misspelling to a real word—for example, read -> Reader is one edit)

• Find the doctor closest to you in your network

Graph algorithms are some of the most useful algorithms I know. Make sure you read the next few chapters carefully—these are algorithms you'll be able to apply again and again.

Introduction to graphs

Suppose you're in San Francisco, and you want to go from Twin Peaks to the Golden Gate Bridge. You want to get there by bus, with the minimum number of transfers. Here are your options.

Image summary: A diagram of transit routes from Twin Peaks to the Golden Gate Bridge. Travelers can walk to different starting points and then take various bus combinations, including Bus #44, Bus #33, Bus #5L, or Bus #38L, eventually converging on Bus #28 to reach the destination. The diagram maps the available multimodal paths for commuting between these two locations.

What's your algorithm to find the path with the fewest steps?

Well, can you get there in one step? Here are all the places you can get to in one step.

Image summary: A diagram showing paths from a starting point, Twin Peaks, to a destination, Golden Gate Bridge. The paths diverge through two intermediate nodes and converge at a final node before reaching the destination, with one path including an additional middle step. The diagram illustrates the possible routes and connectivity between these locations.

The bridge isn't highlighted; you can't get there in one step. Can you get there in two steps?

Image summary: A hand-drawn directed graph showing paths from Twin Peaks to Golden Gate Bridge. The network consists of several intermediate nodes, some of which are marked with radiating lines, with multiple possible routes connecting the start and end points. The diagram illustrates a set of possible trajectories or transitions between these two locations.

Again, the bridge isn't there, so you can't get to the bridge in two steps. What about three steps?

Image summary: A diagram showing a directed graph with nodes and arrows connecting them. Paths lead from a starting node labeled Twin Peaks through intermediate nodes to a final destination node labeled Golden Gate Bridge. The structure illustrates multiple possible routes to reach the same destination from a single origin.

Aha! Now the Golden Gate Bridge shows up. So it takes three steps to get from Twin Peaks to the bridge using this route.

Image summary: A hand-drawn diagram showing a three-step journey from Twin Peaks to the Golden Gate Bridge. The route consists of walking in Step 1, taking Bus 44 in Step 2, and taking Bus 28 in Step 3. The diagram outlines the specific sequence of transportation modes needed to travel between these two locations.

There are other routes that will get you to the bridge too, but they're longer (four steps). The algorithm found that the shortest route to the bridge is three steps long. This type of problem is called a shortest-path problem.

You're always trying to find the shortest something. It could be the shortest route to your friend's house. It could be the smallest number of moves to checkmate in a game of chess. The algorithm to solve a shortest-path problem is called breadth-first search.

To figure out how to get from Twin Peaks to the Golden Gate Bridge, there are two steps:

1. Model the problem as a graph.

2. Solve the problem using breadth-first search.

Next I'll cover what graphs are. Then I'll go into breadth-first search in more detail.

What is a graph?

A graph models a set of connections. For example, suppose you and your friends are playing poker, and you want to model who owes whom money. Here's how you could say, "Alex owes Rama money."

Image summary: A simple diagram showing two circles containing the names ALEX and RAMA, with a right-pointing arrow connecting ALEX to RAMA. This depicts a directional relationship or transfer from Alex to Rama.

The full graph could look something like this.

Image summary: A directed graph showing relationships between four individuals. Arrows point from Alex to Rama, from Tom to Rama, and from both Rama and Tom to Adit. This structure depicts a flow of influence or connection where Adit is the final recipient of connections from all other parties.

Alex owes Rama money, Tom owes Adit money, and so on. Each graph is made up of nodes and edges.

Image summary: A simple diagram of a directed graph showing two circles labeled Alex and Rama, connected by a right-pointing arrow. Labels and arrows identify the circles as nodes and the connecting line as an edge, illustrating the basic components of a graph structure.

That's all there is to it! Graphs are made up of nodes and edges. A node can be directly connected to many other nodes. Those nodes are called its neighbors.

In this graph, Rama is Alex's neighbor. Adit isn't Alex's neighbor, because they aren't directly connected. But Adit is Rama's and Tom's neighbor.

Graphs are a way to model how different things are connected to one another. Now let's see breadth-first search in action.

Breadth-first search

We looked at a search algorithm in chapter 1: binary search. Breadth-first search is a different kind of search algorithm: one that runs on graphs. It can help answer two types of questions:

• Question type 1: Is there a path from node A to node B?

• Question type 2: What is the shortest path from node A to node B?

You already saw breadth-first search once, when you calculated the shortest route from Twin Peaks to the Golden Gate Bridge. That was a question of type 2: “What is the shortest path?” Now let's look at the algorithm in more detail. You'll ask a question of type 1: “Is there a path?”

Suppose you're the proud owner of a mango farm. You're looking for a mango seller who can sell your mangoes. Are you connected to a mango seller on Facebook? Well, you can search through your friends.

Image summary: A simple hand-drawn diagram showing a central figure labeled "YOU" with arrows pointing toward three other figures labeled "BOB", "CLAIRE", and "ALICE". The diagram depicts a network of relationships or communications originating from the central person.

This search is pretty straightforward. First, make a list of friends to search.

Image summary: A simple drawing of a clipboard holding a checklist with three names: Alice, Bob, and Claire, each with an empty checkbox next to it. The image is a basic illustration of a task or attendance list.

Now, go to each person in the list and check whether that person sells mangoes.

Image summary: A flowchart depicting a sequential search process through a list of names: Alice, Bob, and Claire. For each person, the process asks if they sell mangoes; if yes, the search is done, and if no, it moves to the next person. If none of the three sell mangoes, the final result is that no friends sell mangoes. The diagram illustrates a linear search algorithm for finding a specific attribute within a small set.

Suppose none of your friends are mango sellers. Now you have to search through your friends' friends.

Image summary: A diagram depicting a social network of animal characters, where nodes are labeled with names like You, Bob, Claire, Alice, Peggy, Anuj, Thom, and Jonny. Arrows indicate directed relationships, showing that You is connected to Bob, Claire, and Alice, while other characters have their own specific connections. The purpose of the diagram is to map out the directional links between individuals in a small network.

Each time you search for someone from the list, add all of their friends to the list.

Image summary: A flow diagram illustrating a search process. Starting with a list containing Alice, Bob, and Claire, the process asks if Alice sells mangoes; if the answer is yes, the process ends, but if no, all of Alice's friends are added to the search list. The final panel shows Peggy has been added to the list, demonstrating how the search space expands based on social connections.

This way, you not only search your friends, but you search their friends, too. Remember, the goal is to find one mango seller in your network. So if Alice isn't a mango seller, you add her friends to the list, too.

That means you'll eventually search her friends—and then their friends, and so on. With this algorithm, you'll search your entire network until you come across a mango seller. This algorithm is breadth-first search.

Finding the shortest path

As a recap, these are the two questions that breadth-first search can answer for you:

- Question type 1: Is there a path from node A to node B? (Is there a mango seller in your network?)

- Question type 2: What is the shortest path from node A to node B? (Who is the closest mango seller?)

You saw how to answer question 1; now let's try to answer question 2. Can you find the closest mango seller? For example, your friends are first-degree connections, and their friends are second-degree connections.

Image summary: A diagram illustrating a social network centered on the user, labeled You. First-degree connections are located within a central cloud and include Bob, Claire, and Alice; second-degree connections are located outside this cloud and include Anuj, Peggy, Thom, and Jonny. The diagram shows that second-degree connections are reached through first-degree intermediaries, demonstrating how social distance increases as one moves further from the center.

You'd prefer a first-degree connection to a second-degree connection, and a second-degree connection to a third-degree connection, and so on. So you shouldn't search any second-degree connections before you make sure you don't have a first-degree connection who is a mango seller. Well, breadth-first search already does this! The way breadth-first search works, the search radiates out from the starting point.

So you'll check first-degree connections before second-degree connections. Pop quiz: who will be checked first, Claire or Anuj? Answer: Claire is a first-degree connection, and Anuj is a second-degree connection. So Claire will be checked before Anuj.

Image summary: A hand-drawn diagram of a clipboard listing names grouped by degree of connection. Bob, Claire, and Alice are listed under 1st degree, while Anuj, Peggy, Thom, and Jonny are listed under 2nd degree. The image illustrates the concept of social network degrees of separation.

Another way to see this is, first-degree connections are added to the search list before second-degree connections.

You just go down the list and check people to see whether each one is a mango seller. The first-degree connections will be searched before the second-degree connections, so you'll find the mango seller closest to you. Breadth-first search not only finds a path from A to B, it also finds the shortest path.

Notice that this only works if you search people in the same order in which they're added. That is, if Claire was added to the list before Anuj, Claire needs to be searched before Anuj. What happens if you search Anuj before Claire, and they're both mango sellers? Well, Anuj is a second-degree contact, and Claire is a first-degree contact.

You end up with a mango seller who isn't the closest to you in your network. So you need to search people in the order that they're added. There's a data structure for this: it's called a queue.

Queues

A queue works exactly like it does in real life. Suppose you and your friend are queueing up at the bus stop. If you're before him in the queue, you get on the bus first.

A queue works the same way. Queues are similar to stacks. You can't access random elements in the queue. Instead, there are two only operations, enqueue and dequeue.

Image summary: A simple black and white drawing of three people standing in a line next to a sign that reads "BUS STOP". The group consists of a bearded man in a cap and jacket, a woman with a ponytail, and a man in a suit and glasses. It is an illustrative image depicting people waiting for transportation.

Image summary: A diagram illustrating the enqueue and dequeue operations of a queue data structure. Enqueue is shown as adding an item to the end of the line, while dequeue is shown as removing an item from the front. The point is to demonstrate the first-in, first-out nature of a queue.

If you enqueue two items to the list, the first item you added will be dequeued before the second item. You can use this for your search list! People who are added to the list first will be dequeued and searched first.

The queue is called a fifo data structure: First In, First Out. In contrast, a stack is a lifo data structure: Last In, First Out.

Image summary: A diagram comparing two data structures: FIFO (First In, First Out), depicted as a horizontal queue of numbered items, and LIFO (Last In, First Out), depicted as a vertical stack of numbered items. The illustration demonstrates the difference between sequential queue processing and stack-based processing.

Now that you know how a queue works, let's implement breadth-first search!

Exercises

Run the breadth-first search algorithm on each of these graphs to find the solution.

6.1 Find the length of the shortest path from start to finish.

6.2 Find the length of the shortest path from “cab” to “bat”.

Finish

Image summary: Two diagrams illustrating a path-finding problem. The top diagram shows a generic graph with a start node S and a finish node F. The bottom diagram applies this structure to a word ladder, where a path must be found from the start word CAB to the finish word BAT by changing one letter at a time through words like CAR, BAR, CAT, and MAT. The point is to demonstrate how a word puzzle can be modeled as a graph search problem.

Implementing the graph

First, you need to implement the graph in code. A graph consists of several nodes.

And each node is connected to neighboring nodes.

How do you express a relationship like “you -> bob”?

Luckily, you know a data structure that lets you express relationships: a hash table!

Remember, a hash table allows you to map a key to a value. In this case, you want to map a node to all of its neighbors.

Image summary: A hand-drawn illustration of a rectangular box or suitcase divided into two sections. The left section contains the word "YOU", and the right section lists the names "ALICE", "BOB", and "CLAIRE". It is a conceptual drawing used to represent a distinction between an individual and a group.

Here's how you'd write it in Python:

Image summary: A hand-drawn diagram showing a central dog labeled "YOU" with arrows pointing from it to a cat labeled "BOB" and a pig labeled "CLAIRE," and a line connecting it to another dog labeled "ALICE." The diagram depicts the relationships or connections between the central figure and three other animals.

Math summary: This expression defines a graph data structure. It maps the input key you to a list containing the three neighbors alice, bob, and claire.

Notice that “you” is mapped to an array. So graph["you"] will give you an array of all the neighbors of “you”.

A graph is just a bunch of nodes and edges, so this is all you need to have a graph in Python. What about a bigger graph, like this one?

Image summary: A hand-drawn diagram of a social or relational network where individuals, represented by animal faces and names, are connected by arrows. The central figure, labeled "YOU," has outgoing arrows to Bob, Claire, and Alice, who in turn connect to others: Bob leads to Anuj and Peggy, Claire leads to Thom and Jonny, and Alice leads to Peggy. The diagram maps out a chain of connections originating from the central user.

Here it is as Python code:

Code summary: This code defines a directed graph using a dictionary to represent a social network or set of relationships, where each key is a person and the associated list contains the people they are connected to.

Pop quiz: does it matter what order you add the key/value pairs in? Does it matter if you write

Code summary: This snippet demonstrates the use of a dictionary to represent a graph, where keys are nodes and values are lists of adjacent nodes. It illustrates that the order in which edges are defined for different nodes does not affect the resulting graph structure.

Think back to the previous chapter. Answer: It doesn't matter. Hash tables have no ordering, so it doesn't matter what order you add key/value pairs in.

Anuj, Peggy, Thom, and Jonny don't have any neighbors. They have arrows pointing to them, but no arrows from them to someone else. This is called a directed graph—the relationship is only one way.

So Anuj is Bob's neighbor, but Bob isn't Anuj's neighbor. An undirected graph doesn't have any arrows, and both nodes are each other's neighbors. For example, both of these graphs are equal.

Image summary: A diagram of a directed graph consisting of two nodes labeled Ross and Rachel, with one arrow pointing from Ross to Rachel and another pointing from Rachel back to Ross. This structure depicts a bidirectional relationship between the two entities.

Image summary: A simple diagram consisting of two circles containing the names ROSS and RACHEL, connected by a single straight line. The image depicts a relationship or connection between these two individuals.

Undirected

Graph

Implementing the algorithm

To recap, here's how the implementation will work.

Image summary: A flow diagram illustrating a breadth-first search process to find a mango seller. The process begins with a queue of people, pops the first person to check if they are a mango seller, and either ends if the person is a seller or adds that person's neighbors to the queue to continue the search. The loop repeats until a mango seller is found.

6. if the Queue is Empty,

There are no Mango Sellers

in Your Network Note

When updating queues, I use the terms enqueue and dequeue. You'll also encounter the terms push and pop. Push is almost always the same thing as enqueue, and pop is almost always the same thing as dequeue.

Make a queue to start. In Python, you use the double-ended queue (deque) function for this:

from collections import deque search queue equals deque open parenthesis close parenthesis arrow Creates a new queue search queue plus equals graph ["you"] from Adds all of your neighbors to the search queue

Remember, graph["you"] will give you a list of all your neighbors, like ["alice", "bob", "claire"]. Those all get added to the search queue.

Image summary: A drawing of a clipboard with a checklist containing three names: Alice, Bob, and Claire, each with an empty checkbox next to it. It is a simple illustration of a list of people to be checked off.

Let's see the rest:

Code summary: This breadth-first search algorithm identifies if a mango seller exists within a social network. It iteratively dequeues individuals from a search queue and checks if they are sellers; if not, it expands the search by adding the person's friends to the queue. The process continues until a seller is found, returning true, or the queue is exhausted, returning false.

One final thing: you still need a person_is seller function to tell you when someone is a mango seller. Here's one:

Code summary: person_is_seller determines if a person is a seller by checking if the last character of their name is the letter m.

This function checks whether the person's name ends with the letter m. If it does, they're a mango seller. Kind of a silly way to do it, but it'll do for this example. Now let's see the breadth-first search in action.

Code summary: BOB PEGGY

And so on. The algorithm will keep going until either

• A mango seller is found, or

- The queue becomes empty, in which case there is no mango seller.

Alice and Bob share a friend: Peggy. So Peggy will be added to the queue twice: once when you add Alice's friends, and again when you add Bob's friends. You'll end up with two Peggy's in the search queue.

Image summary: A hand-drawn sketch depicting three adjacent rectangular boxes labeled "CLAIRE", "PEGGY", and "PEGGY", with small leg-like lines extending downward from each box. A bracket is drawn underneath the two boxes labeled "PEGGY". The image is a simple diagram with no analytical data to report.

But you only need to check Peggy once to see whether she's a mango seller. If you check her twice, you're doing unnecessary, extra work. So once you search a person, you should mark that person as searched and not search them again.

If you don't do this, you could also end up in an infinite loop. Suppose the mango seller graph looked like this.

Image summary: A simple diagram showing two circles labeled "You" and "PEGGY" connected by two opposing curved arrows, creating a loop. This depicts a reciprocal or bidirectional relationship between the two entities.

To start, the search queue contains all of your neighbors.

Image summary: A simple hand-drawn sketch of a rectangular sign or nameplate resting on two small legs, with the word PEGGY written in capital letters in the center. It is a basic illustration with no data or analytical result to report.

Now you check Peggy. She isn't a mango seller, so you add all of her neighbors to the search queue.

Image summary: A simple hand-drawn illustration of a rectangular sign with the word "YOU" written on it, supported by two small legs. It is a conceptual drawing with no data or analytical result to report.

Next, you check yourself. You're not a mango seller, so you add all of your neighbors to the search queue.

Image summary: A simple hand-drawn sketch of a rectangular sign or placard on two legs with the word PEGGY written in capital letters in the center. It is a basic drawing with no data or analytical result to report.

And so on. This will be an infinite loop, because the search queue will keep going from you to Peggy.

Image summary: A simple hand-drawn sketch of a sign or piece of paper that reads "ALREADY CHECKED:" followed by a bullet point with the name "PEGGY". It is a basic illustration with no data or analytical result to report.

Image summary: A diagram showing a circular flow of arrows connecting four boxes. The boxes alternate between the names "PEGGY" and "YOU" in a clockwise loop. This structure depicts a repetitive, cyclical interaction or exchange between two parties.

Before checking a person, it's important to make sure they haven't been checked already. To do that, you'll keep a list of people you've already checked.

Here's the final code for breadth-first search, taking that into account:

Code summary: search implements a breadth-first search to find a mango seller within a social graph. It uses a queue to track people to visit and a list to record searched individuals to avoid infinite loops. The process iteratively explores connections until a seller is identified via the person_is_seller check or all reachable people have been exhausted, returning true if a seller is found and false otherwise.

Try running this code yourself. Maybe try changing the person_is seller function to something more meaningful, and see if it prints what you expect.

If you search your entire network for a mango seller, that means you'll follow each edge (remember, an edge is the arrow or connection from one person to another). So the running time is at least O(number of edges).

You also keep a queue of every person to search. Adding one person to the queue takes constant time: O (1). Doing this for every person will take O (number of people) total. Breadth-first search takes O (number of people + number of edges), and it's more commonly written as O (V+E) (V for number of vertices, E for number of edges).

Exercise

Here's a small graph of my morning routine.

Image summary: A flow diagram with three circles containing the activities "SHOWER", "BRUSH TEETH", and "EAT BREAKFAST", all with arrows pointing toward a central circle labeled "WAKE UP". The structure depicts a reversed sequence of events where multiple morning activities are shown leading back to the act of waking up.

It tells you that I can't eat breakfast until I've brushed my teeth. So "eat breakfast" depends on "brush teeth".

On the other hand, showering doesn't depend on brushing my teeth, because I can shower before I brush my teeth. From this graph, you can make a list of the order in which I need to do my morning routine:

1. Wake up.

2. Shower.

3. Brush teeth.

4. Eat breakfast.

Note that “shower” can be moved around, so this list is also valid:

1. Wake up.

2. Brush teeth.

3. Shower.

4. Eat breakfast.

6.3 For these three lists, mark whether each one is valid or invalid.

A.

1. Wake up

2. Shower

3. Eat Breakfast

4. Brush Teeth

B.

1. Wake up

2. Brush Teeth

3. Eat Breakfast

4. Shower

C.

1. Shower

2. Wake up

3. Brush Teeth

4. Eat Breakfast

6.4 Here's a larger graph. Make a valid list for this graph.

Image summary: A hand-drawn flow diagram showing a morning routine where multiple activities lead back to waking up. Arrows point from 'Get Dressed' to 'Shower', from 'Shower' to 'Exercise', and from 'Eat Breakfast' to 'Brush Teeth', with 'Exercise', 'Brush Teeth', and 'Pack Lunch' all pointing toward 'Wake Up'. The diagram depicts a reversed chronological sequence of a morning routine.

You could say that this list is sorted, in a way. If task A depends on task B, task A shows up later in the list. This is called a topological sort, and it's a way to make an ordered list out of a graph. Suppose you're planning a wedding and have a large graph full of tasks to do—and you're not sure where to start. You could topologically sort the graph and get a list of tasks to do, in order.

Suppose you have a family tree.

Image summary: A hand-drawn family tree diagram showing a person labeled "You" at the top, connected by lines to two "Parents," who are in turn connected to four "Grandparents" at the bottom. The diagram illustrates the ancestral lineage and the doubling of ancestors across three generations.

This is a graph, because you have nodes (the people) and edges. The edges point to the nodes' parents. But all the edges go down—it wouldn't make sense for a family tree to have an edge pointing back up! That would be meaningless—your dad can't be your grandfather's dad!

Image summary: A hand-drawn diagram showing a genealogical hierarchy with "YOU" at the top, "PARENTS" in the middle, and "GRANDPARENTS" at the bottom. Arrows point only downwards from the top level to the middle and from the middle to the bottom, with a note stating "THERE ARE NO ARROWS POINTING BACK UP." The diagram illustrates the one-way flow of descent from ancestors to descendants.

This is called a tree. A tree is a special type of graph, where no edges ever point back.

6.5 Which of the following graphs are also trees?

- Breadth-first search tells you if there's a path from A to B.

• If there's a path, breadth-first search will find the shortest path.

• If you have a problem like “find the shortest X,” try modeling your problem as a graph, and use breadth-first search to solve.

• A directed graph has arrows, and the relationship follows the direction of the arrow (rama -> adit means "rama owes adit money").

- Undirected graphs don't have arrows, and the relationship goes both ways (ross - rachel means “ross dated rachel and rachel dated ross”).

• Queues are fifo (First In, First Out).

• Stacks are lifo (Last In, First Out).

• You need to check people in the order they were added to the search list, so the search list needs to be a queue. Otherwise, you won't get the shortest path.

- Once you check someone, make sure you don't check them again. Otherwise, you might end up in an infinite loop.

Figure 6.5 summary: Three diagrams of directed graphs showing different connectivity patterns: a hierarchical tree structure on the left, a complex graph with cycles in the middle, and a linear chain on the right. These examples illustrate the variety of ways nodes can be linked in a directed network.

In this chapter

- We continue the discussion of graphs, and you learn about weighted graphs: a way to assign more or less weight to some edges.

- You learn Dijkstra's algorithm, which lets you answer "What's the shortest path to X?" for weighted graphs.

- You learn about cycles in graphs, where Dijkstra's algorithm doesn't work.

In the last chapter, you figured out a way to get from point A to point B.

Image summary: A directed graph diagram showing paths between Twin Peaks and Golden Gate Bridge. The shortest path consists of two thick arrows passing through a single intermediate node, while alternative paths involve more nodes and thinner arrows. The diagram illustrates that the most direct route from Twin Peaks to Golden Gate Bridge is the one highlighted by the thick lines.

It's not necessarily the fastest path. It's the shortest path, because it has the least number of segments (three segments). But suppose you add travel times to those segments. Now you see that there's a faster path.

Image summary: A network diagram showing travel times between Twin Peaks and the Golden Gate Bridge via different paths. The shortest route involves traveling from Twin Peaks to a bottom node in 10 minutes, then to a middle node in 5 minutes, and finally to a top node in 5 minutes, before reaching the bridge in 4 minutes. The takeaway is that the path through the middle and top nodes is faster than the direct top path or the bottom-most path.

You used breadth-first search in the last chapter. Breadth-first search will find you the path with the fewest segments (the first graph shown here). What if you want the fastest path instead (the second graph)? You can do that fastest with a different algorithm called Dijkstra's algorithm.

Working with Dijkstra's algorithm

Let's see how it works with this graph.

Image summary: A directed graph diagram showing paths from a START node to a FINISH node via nodes A and B. The edges are weighted: START to A is 6, START to B is 2, A to FINISH is 1, B to FINISH is 5, and B to A is labeled w. This structure represents a network where the total cost to reach the finish depends on the value of the weight w on the path from B to A.

Each segment has a travel time in minutes. You'll use Dijkstra's algorithm to go from start to finish in the shortest possible time.

If you ran breadth-first search on this graph, you'd get this shortest path.

Image summary: A diagram of a weighted graph showing paths from a START node to a FINISH node via intermediate nodes A and B. One path goes from START to A to FINISH with weights 6 and 1, totaling 7 minutes as indicated by the bracket at the top; another path goes from START to B to FINISH with weights 2 and 5, also totaling 7 minutes. The diagram illustrates two different routes that take the same total amount of time to reach the destination.

But that path takes 7 minutes. Let's see if you can find a path that takes less time! There are four steps to Dijkstra's algorithm:

1. Find the “cheapest” node. This is the node you can get to in the least amount of time.

2. Update the costs of the neighbors of this node. I'll explain what I mean by this shortly.

3. Repeat until you've done this for every node in the graph.

4. Calculate the final path.

Step 1: Find the cheapest node. You're standing at the start, wondering if you should go to node A or node B. How long does it take to get to each node?

Image summary: A diagram of a weighted directed graph with nodes labeled START, A, B, and FINISH. Edges connect START to A (weight 6) and B (weight 2), B to A (weight w), B to FINISH (weight 5), and A to FINISH (weight 1). Additionally, an external value of 6 points toward node A and a value of 2 points toward node B. The diagram represents a network for calculating paths or costs between a start and finish point.

It takes 6 minutes to get to node A and 2 minutes to get to node B. The rest of the nodes, you don't know yet.

Because you don't know how long it takes to get to the finish yet, you put down infinity (you'll see why soon). Node B is the closest node ... it's 2 minutes away.

: Table summary: Travel times to specific nodes, where node B is the fastest to reach at 2 units of time, node A takes 6 units, and the time to reach FINISH is listed as infinity.

Step 2: Calculate how long it takes to get to all of node B's neighbors by following an edge from B.

Table summary: The time associated with each node varies, with FINISH taking the longest at 7, followed by A at 5, and B at 2.

Image summary: A hand-drawn graph diagram showing three nodes, A, B, and a nameless starting node, connected by weighted edges. The starting node connects to A with a weight of 6 and to B with a weight of 2; node B connects to A with a weight of w and to the final node with a weight of 5; node A connects to the final node with a weight of 1. Text notes that it now takes only 5 minutes to get to node A, indicating that the path through node B is the shortest route.

Hey, you just found a shorter path to node A! It used to take 6 minutes to get to node A.

Image summary: A directed graph diagram showing a path from a START node to a FIN node. The START node connects to node A with a weight of 6 and to node B with a weight of 2; node B connects to node A with a weight of w and to the FIN node with a weight of 5; node A connects to the FIN node with a weight of 1. The diagram illustrates a network of weighted paths used to determine the shortest distance from start to finish.

But if you go through node B, there's a path that only takes 5 minutes!

Image summary: A diagram of a weighted directed graph with four nodes: START, A, B, and FINISH. Edges connect START to A (weight 6) and B (weight 2), B to A (weight w) and FINISH (weight 5), and A to FINISH (weight 1). The diagram illustrates a network of paths and costs between a starting point and a finishing point.

When you find a shorter path for a neighbor of B, update its cost. In this case, you found

• A shorter path to A (down from 6 minutes to 5 minutes)

- A shorter path to the finish (down from infinity to 7 minutes)

Step 3: Repeat!

Step 1 again: Find the node that takes the least amount of time to get to. You're done with node B, so node A has the next smallest time estimate.

Table summary: The time required for three different nodes, with FINISH taking the longest at 7, followed by A at 5, and B taking the shortest time at 2.

Step 2 again: Update the costs for node A's neighbors.

Image summary: A diagram of a weighted directed graph with a start node connected to nodes A and B, and both A and B connected to a finish node. The edges are labeled with weights: 6 from start to A, 2 from start to B, w from B to A, 1 from A to finish, and 5 from B to finish. The path from A to finish is highlighted with a thick arrow, illustrating a network path problem where the total cost depends on the value of w.

Woo, it takes 6 minutes to get to the finish now!

You've run Dijkstra's algorithm for every node (you don't need to run it for the finish node). At this point, you know

• It takes 2 minutes to get to node B.

• It takes 5 minutes to get to node A.

• It takes 6 minutes to get to the finish.

Table summary: The time values for three nodes are provided, with FINISH having the longest time at 6, followed by A at 5 and B at 2.

I'll save the last step, calculating the final path, for the next section. For now, I'll just show you what the final path is.

Image summary: A directed graph diagram showing paths from a START node to a FIN node via intermediate nodes A and B. Edges are labeled with weights: START to A is 6, START to B is 2, B to A is W, B to FIN is 5, and A to FIN is 1. The diagram depicts a network for calculating the shortest path from start to finish based on these edge weights.

Breadth-first search wouldn't have found this as the shortest path, because it has three segments. And there's a way to get from the start to the finish in two segments.

Image summary: A diagram of a directed graph with a start node connected to two intermediate nodes, A and B, which both lead to a finish node. The path from start to A has a weight of 6, start to B has a weight of 2, B to A has a weight of w, and the paths from A and B to finish have weights of 1 and 5 respectively. This structure represents a network problem where the total cost to reach the finish depends on the value of the variable weight w.

Shortest Path

with BREADTH-first Search In the last chapter, you used breadth-first search to find the shortest path between two points. Back then, “shortest path” meant the path with the fewest segments. But in Dijkstra's algorithm, you assign a number or weight to each segment. Then Dijkstra's algorithm finds the path with the smallest total weight.

Image summary: A weighted directed graph showing travel times between Twin Peaks and the Golden Gate Bridge through various intermediate nodes. The possible paths include a top route taking 25 minutes, a middle route taking 20 minutes, and a bottom route taking 20 minutes. The diagram serves as an exercise to find the shortest path using the Bellman-Ford algorithm.

Image summary: A diagram of a directed graph showing multiple paths between two locations, Twin Peaks and Golden Gate Bridge. The paths consist of nodes connected by arrows, with one path highlighted by a thicker line. The diagram illustrates the various routing options available to travel from the starting point to the destination.

To recap, Dijkstra's algorithm has four steps:

1. Find the cheapest node. This is the node you can get to in the least amount of time.

2. Check whether there's a cheaper path to the neighbors of this node. If so, update their costs.

3. Repeat until you've done this for every node in the graph.

4. Calculate the final path. (Coming up in the next section!)

Terminology

I want to show you some more examples of Dijkstra's algorithm in action. But first let me clarify some terminology.

When you work with Dijkstra's algorithm, each edge in the graph has a number associated with it. These are called weights.

Image summary: A hand-drawn graph diagram showing four nodes connected by directed edges with associated weights. Edges are labeled with values 6, 1, 2, 5, and a variable w. The diagram illustrates a weighted directed graph used to represent relationships or paths between nodes.

A graph with weights is called a weighted graph. A graph without weights is called an unweighted graph.

Image summary: Two diagrams comparing a weighted graph and an unweighted graph. The weighted graph assigns numerical values to the edges connecting nodes, whereas the unweighted graph shows the same connections without any values. The point is to illustrate the difference between graphs that quantify the cost or distance of edges and those that only represent the existence of a connection.

To calculate the shortest path in an unweighted graph, use breadth-first search. To calculate the shortest path in a weighted graph, use Dijkstra's algorithm. Graphs can also have cycles. A cycle looks like this.

Image summary: A hand-drawn diagram of a directed graph consisting of three nodes, A, B, and C, connected by arrows that form a closed loop from A to B, B to C, and C back to A. Accompanying text explains that this is a cycle where one can start at A and end up back at A, illustrating the fundamental concept of a cycle in graph theory.

It means you can start at a node, travel around, and end up at the same node. Suppose you're trying to find the shortest path in this graph that has a cycle.

: Image summary: A hand-drawn directed graph showing a path from a START node to a FINISH node via node B. There are bidirectional edges between nodes A and B, both labeled with the weight 4, which are explicitly marked as a "CYCLE!". The path from START to B has a weight of 2, and the path from B to FINISH has a weight of 3. The diagram illustrates a graph containing a cycle between two of its nodes.

Would it make sense to follow the cycle? Well, you can use the path that avoids the cycle.

Image summary: A hand-drawn diagram of a weighted directed graph with four nodes. Node A and Node B have bidirectional edges between them, both weighted 4. An unnamed node to the left has an edge to Node B weighted 2, and Node B has an edge to an unnamed node on the right weighted 3. The text indicates a total weight of 5, likely referring to the sum of the weights of the two edges entering and leaving Node B from the external nodes.

Or you can follow the cycle.

Image summary: A hand-drawn directed graph with three nodes and four weighted edges. Edges of weight 4 connect node A and node B in both directions, an edge of weight 2 leads from a third node to node B, and an edge of weight 3 leads from node B to a fourth node. The total weight of all edges is labeled as 13.

You end up at node A either way, but the cycle adds more weight. You could even follow the cycle twice if you wanted.

Image summary: A diagram of a weighted directed graph with three nodes. Two edges create a bidirectional loop between nodes A and B, each with a weight of 4, while a third node connects to node B with a weight of 2 and node B connects to a fourth node with a weight of 3. The total weight is labeled as 21, though the sum of the visible edge weights is 13.

But every time you follow the cycle, you're just adding 8 to the total weight. So following the cycle will never give you the shortest path.

Finally, remember our conversation about directed versus undirected graphs from chapter 6?

Image summary: A diagram of a directed graph consisting of two nodes labeled Ross and Rachel, with one arrow pointing from Ross to Rachel and another pointing from Rachel to Ross. This structure depicts a bidirectional relationship between the two entities.

Image summary: A diagram of an undirected graph consisting of two nodes labeled Ross and Rachel connected by a single line without arrows. This illustrates a basic undirected graph where a relationship exists between two entities without a specified direction.

An undirected graph means that both nodes point to each other. That's a cycle!

Image summary: A hand-drawn diagram comparing two graph structures. On the left, a single directed edge connects node A to node B. On the right, two directed edges create a loop between nodes A and B, with a label and arrow pointing to the loop asking "CYCLE!". The image illustrates the difference between a simple connection and a cyclic relationship between two entities.

With an undirected graph, each edge adds another cycle. Dijkstra's algorithm only works with directed acyclic graphs, called D.A.G's for short.

Trading for a piano

Enough terminology, let's look at another example! This is Rama. Rama is trying to trade a music book for a piano.

“I'll give you this poster for your book,” says Alex. “It's a poster of my favorite band, Destroyer. Or I'll give you this rare L.P of Rick Astley for your book and $5 more.” “Ooh, I've heard that L.P has a really great song,” says Amy. “I'll trade you my guitar or drum set for the poster or the L.P

“I've been meaning to get into guitar!” exclaims Beethoven. “Hey, I'll trade you my piano for either of Amy's things.”

Image summary: A simple line drawing of a closed book with a bookmark extending from the left side. The accompanying text, "WE HAVEN'T REACHED THESE NODES FROM THE START YET," suggests the image is used as a metaphor for unexplored information or unvisited states in a process.

Perfect! With a little bit of money, Rama can trade his way from a piano book to a real piano. Now he just needs to figure out how to spend the least amount of money to make those trades. Let's graph out what he's been offered.

Image summary: A hand-drawn directed graph showing paths between nodes associated with different objects: a book, a rare LP, a poster, a drum set, a bass guitar, and a piano. The edges are labeled with numerical values, representing weights or costs for moving between nodes. The diagram illustrates a network of connections and their associated costs between these various items.

In this graph, the nodes are all the items Rama can trade for. The weights on the edges are the amount of money he would have to pay to make the trade. So he can trade the poster for the guitar for $30, or trade the L.P for the guitar for $15. How is Rama going to figure out the path from the book to the piano where he spends the least dough?

Dijkstra's algorithm to the rescue! Remember, Dijkstra's algorithm has four steps. In this example, you'll do all four steps, so you'll calculate the final path at the end, too.

: Table summary: Current costs for reaching specific nodes from the start. The node LD has a cost of 5, while POSTER is marked with a null symbol. GUITAR, DRUMS, and PIANO all have a cost of infinity, indicating they have not yet been reached.

Before you start, you need some setup. Make a table of the cost for each node. The cost of a node is how expensive it is to get to.

You'll keep updating this table as the algorithm goes on. To calculate the final path, you also need a parent column on this table.

Table summary: A hierarchy of nodes and their parents. LP and POSTER both have BOOK as their parent, while GUITAR, DRUMS, and PIANO have no parent listed.

I'll show you how this column works soon. Let's start the algorithm.

Step 1: Find the cheapest node. In this case, the poster is the cheapest trade, at 0 dollars. Is there a cheaper way to trade for the poster? This is a really important point, so think about it. Can you see a series of trades that will get Rama the poster for less than 0 dollars? Read on when you're ready.

Answer: No. Because the poster is the cheapest node Rama can get to, there's no way to make it any cheaper. Here's a different way to look at it. Suppose you're traveling from home to work.

Image summary: A diagram showing travel times between four locations: Home, Park, School, and Work. Travel from Home takes 6 minutes to the Park and 2 minutes to School; from School, it takes 1 minute to the Park and 3 minutes to Work; from the Park, it takes 3 minutes to Work and 1 minute to School. The diagram maps the connectivity and time costs between these specific destinations.

If you take the path toward the school, that takes 2 minutes. If you take the path toward the park, that takes 6 minutes. Is there any way you can take the path toward the park, and end up at the school, in less than 2 minutes? It's impossible, because it takes longer than 2 minutes just to get to the park. On the other hand, can you find a faster path to the park? Yup.

Image summary: A diagram showing travel times between Home, Park, School, and Work. The shortest path from Home to Work is through School, taking a total of 5 minutes, whereas the path through the Park takes 9 minutes. The point is to illustrate that taking a detour through School is faster than going through the Park.

This is the key idea behind Dijkstra's algorithm: Look at the cheapest node on your graph. There is no cheaper way to get to this node! Back to the music example. The poster is the cheapest trade.

Step 2: Figure out how long it takes to get to its neighbors (the cost).

Image summary: A hand-drawn directed graph showing connections between five nodes: Book, LP, Poster, Bass Guitar, and Drums, with Piano as an additional node. Each edge is labeled with a numerical value, including some with a phi symbol. The diagram maps weighted relationships or costs between different musical and media items.

Table summary: Costs associated with connections between parent and node entities. The lowest cost is 3 for the connection from POSTER to GUITAR, while the highest finite cost is 35 for the connection from POSTER to DRUMS. Other connections include BOOK to LP at 5 and BOOK to POSTER at 6, while PIANO has no parent and an infinite cost.

You have prices for the bass guitar and the drum set in the table. Their value was set when you went through the poster, so the poster gets set as their parent. That means, to get to the bass guitar, you follow the edge from the poster, and the same for the drums.

Table summary: A list of parent-node relationships and their associated costs. The relationship from BOOK to LP has a cost of 5, while the path from POSTER to DRUMS costs 35. Other entries include a null cost for BOOK to POSTER, a cost of 3 null for POSTER to GUITAR, and an infinite cost for the standalone node PIANO.

Step 1 again: The L.P is the next cheapest node at $5.

Step 2 again: Update the values of all of its neighbors.

Image summary: A hand-drawn directed graph showing paths from a starting node labeled Book to several destination nodes: LP, Poster, Bass Guitar, Piano, and Drums. Edges are weighted with numerical values and symbols, such as 5, 15, 35, and various values containing a phi symbol. The diagram represents a network of weighted connections between different items.

: Table summary: The costs associated with moving between parent and child nodes. The lowest cost is 2 for the path from LP to GUITAR, while the path from LP to DRUMS is significantly higher at 25. Other entries include a cost of 5 for BOOK to LP, an undefined cost for BOOK to POSTER, and an infinite cost for the PIANO node, which has no listed parent.

Hey, you updated the price of both the drums and the guitar! That means it's cheaper to get to the drums and guitar by following the edge from the L.P. So you set the L.P as the new parent for both instruments.

The bass guitar is the next cheapest item. Update its neighbors.

: Image summary: A hand-drawn directed graph showing the flow of items between nodes labeled Book, LP, Poster, Bass Guitar, Drums, and Piano, with numerical values assigned to the edges. The flow starts at Book and splits toward LP and Poster, eventually converging at Piano. The point is to illustrate a network of connections and associated values between these different objects.

Table summary: A list of parent and node relationships with associated costs. The highest cost is 40 for the relationship between GUITAR and PIANO, while the lowest is 0 for BOOK and POSTER. Other costs include 25 for LP and DRUMS, 20 for LP and GUITAR, and 5 for BOOK and LP.

Ok, you finally have a price for the piano, by trading the guitar for the piano. So you set the guitar as the parent. Finally, the last node, the drum set.

Image summary: A hand-drawn directed graph showing weighted connections between nodes labeled Book, LP, Poster, Bass Guitar, Drums, and Piano. Arrows indicate paths between items with associated numerical values, such as 5 from Book to LP and 35 from Poster to Drums. The diagram represents a network of weighted relationships or costs between different objects.

Table summary: A cost breakdown for a hierarchy of items. The highest cost is 35 for the connection from DRUMS to PIANO, while the lowest cost is 0 for the connection from BOOK to POSTER. Other costs include 25 for LP to DRUMS, 20 for LP to GUITAR, and 5 for BOOK to LP.

Rama can get the piano even cheaper by trading the drum set for the piano instead. So the cheapest set of trades will cost Rama $35.

Now, as I promised, you need to figure out the path. So far, you know that the shortest path costs $35, but how do you figure out the path? To start with, look at the parent for piano.

Table summary: A hierarchical relationship between parent and node entities. BOOK is the parent of LP and POSTER, while LP is the parent of GUITAR and DRUMS, and DRUMS is the parent of PIANO.

The piano has drums as its parent. That means Rama trades the drums for the piano. So you follow this edge.

Let's see how you'd follow the edges. Piano has drums as its parent.

Image summary: A directed graph diagram showing paths between five nodes: Book, LP, Poster, Drums, and Piano. Edges are labeled with numerical values or null symbols, with paths flowing from Book toward Piano. The shortest path from Book to Piano is through LP and Drums, as opposed to paths through Poster or Bass Guitar. The diagram illustrates a weighted network used to find the minimum cost path between two points.

And drums has the L.P as its parent.

Image summary: A directed graph diagram connecting five nodes: Book, LP, Poster, Bass Guitar, and Drums, with a final connection to Piano. Each edge is labeled with a numerical value, and some edges are highlighted in bold. The diagram maps weighted paths between different items, likely representing costs or distances in a network.

So Rama will trade the L.P for the drums. And of course, he'll trade the book for the L.P. By following the parents backward, you now have the complete path.

Image summary: A hand-drawn network diagram showing paths between nodes labeled Book, LP, Poster, Bass Guitar, Drums, and Piano, with numerical weights assigned to the connecting edges. The thickest paths connect Book to LP, LP to Drums, and Drums to Piano, indicating the primary route through the network.

Here's the series of trades Rama needs to make.

Image summary: A diagram showing a cycle of transformations between three objects: a book transforms into an LP, an LP transforms into drums, and drums transform into a piano. The sequence illustrates a conceptual progression or conversion between different forms of media and instruments.

So far, I've been using the term shortest path pretty literally: calculating the shortest path between two locations or between two people. I hope this example showed you that the shortest path doesn't have to be about physical distance. It can be about minimizing something. In this case, Rama wanted to minimize the amount of money he spent. Thanks, Dijkstra!

Negative-weight edges

In the trading example, Alex offered to trade the book for two items.

Suppose Sarah offers to trade the L.P for the poster, and she'll give Rama an additional 7 dollars. It doesn't cost Rama anything to make this trade; instead, he gets 7 dollars back. How would you show this on the graph?

Image summary: A hand-drawn diagram showing three items—Book, LP, and Poster—connected by arrows. An arrow from Book to LP is labeled 5, and an arrow from Book to Poster is labeled with a null symbol. A text note states that Sarah will give Rama $7 if he trades his LP for her Poster. The diagram illustrates the value or exchange relationships between these three items.

Image summary: A diagram showing a node labeled Book with outgoing arrows to two other nodes, LP and POSTER. The arrow to LP is labeled $5 and the arrow to POSTER is labeled $0, illustrating the different costs associated with obtaining these two items from a book.

The edge from the L.P to the poster has a negative weight! Rama gets $7 back if he makes that trade. Now Rama has two ways to get to the poster.

Image summary: Two diagrams showing paths between nodes labeled Book, LP, and Poster. In the first diagram, the path goes directly from Book to Poster with a value of 0, and the text states Rama gets 0 dollars back. In the second diagram, the path goes from Book to LP and then from LP to Poster, and the text states Rama gets 2 dollars back. The figure illustrates how choosing a multi-step path can result in a higher payout than a direct path.

So it makes sense to do the second trade—Rama gets $2 back that way! Now, if you remember, Rama can trade the poster for the drums. There are two paths he could take.

Image summary: Two diagrams comparing different trade paths between items labeled Book, LP, Poster, and Drums. In the first scenario, the path goes from Book to Poster and then to Drums, resulting in a total cost of $35. In the second scenario, the path goes from Book to LP, then to Poster, and finally to Drums, resulting in a lower total cost of $33. The point is that the indirect trade route through LP reduces the overall cost.

The second path costs him $2 less, so he should take that path, right? Well, guess what? If you run Dijkstra's algorithm on this graph, Rama will take the wrong path.

He'll take the longer path. You can't use Dijkstra's algorithm if you have negative-weight edges. Negative-weight edges break the algorithm.

Let's see what happens when you run Dijkstra's algorithm on this. First, make the table of costs.

: Table summary: Costs for three items, where LP is 5, POSTER is empty, and DRUMS is infinite.

Next, find the lowest-cost node, and update the costs for its neighbors. In this case, the poster is the lowest-cost node. So, according to Dijkstra's algorithm, there is no cheaper way to get to the poster than paying $0 (you know that's wrong!). Anyway, let's update the costs for its neighbors.

Image summary: A diagram and a corresponding table illustrating costs associated with different items. The diagram shows weighted edges between Book, LP, Poster, and Drums, where the path from Book to LP is labeled 5, Book to Poster is labeled with a null symbol, and Poster to Drums is labeled 35. The table lists the cost for LP as 5, Poster as a null symbol, and Drums as 35. The overall purpose is to map the costs of these specific items.

Ok, the drums have a cost of $35 now.

Let's get the next-cheapest node that hasn't already been processed.

: Table summary: Final costs for three items. DRUMS has the highest cost at 35, followed by LP at 5, while no cost is listed for POSTER.

Update the costs for its neighbors.

Image summary: A diagram showing a directed graph on the left and a corresponding cost table on the right. In the graph, edges connect Book to LP with a weight of 5, Book to Poster with a weight of 0, LP to Poster with a weight of 1, and Poster to Drums with a weight of 35. The table maps these items to their costs: LP is 5, Poster is 2, and Drums is 35. The figure illustrates how paths in a network translate to specific costs for different items.

You already processed the poster node, but you're updating the cost for it. This is a big red flag. Once you process a node, it means there's no cheaper way to get to that node. But you just found a cheaper way to the poster!

Drums doesn't have any neighbors, so that's the end of the algorithm. Here are the final costs.

Table summary: Final costs for three items, with DRUMS having the highest cost at 35, followed by LP at 5, and POSTER showing a negative value of -2.

It costs 35 dollars to get to the drums. You know that there's a path that costs only 33 dollars, but Dijkstra's algorithm didn't find it. Dijkstra's algorithm assumed that because you were processing the poster node, there was no faster way to get to that node. That assumption only works if you have no negative-weight edges.

So you can't use negative-weight edges with Dijkstra's algorithm. If you want to find the shortest path in a graph that has negative-weight edges, there's an algorithm for that! It's called the Bellman–Ford algorithm. Bellman–Ford is out of the scope of this book, but you can find some great explanations online.

Implementation

Let's see how to implement Dijkstra's algorithm in code. Here's the graph I'll use for the example.

Image summary: A weighted directed graph showing paths from a START node to a FIN node. The paths include a route from START to A with weight 6, from START to B with weight 2, from B to A with weight w, from A to FIN with weight 1, and from B to FIN with weight 5. The diagram represents a network for calculating the shortest path between the start and finish points.

To code this example, you'll need three hash tables.

Image summary: A hand-drawn grid diagram resembling a table or a game board. The grid contains labels such as START, A, B, and FIN, paired with numbers like 6, 2, 1, 3, and 5 in adjacent cells. The layout organizes these labels and values into a structured sequence, likely representing a logic puzzle or a set of game rules.

: Image summary: A grid diagram representing costs, with labels A and B in the left column and values 6 and 2 in the right column. The bottom row contains the labels FIN and the infinity symbol. This structure maps specific categories or states to their corresponding costs, showing that state B has a lower cost than A, while the final state is associated with infinite cost.

Image summary: A simple hand-drawn grid depicting a cost table with three rows and two columns. The first two rows associate labels A and B with a START value, while the final row associates FIN with a dash. The figure serves as a basic representation of costs associated with starting and finishing processes.

You'll update the costs and parents hash tables as the algorithm progresses. First, you need to implement the graph. You'll use a hash table like you did in chapter 6:

Math summary: This expression initializes a variable named graph. It defines the graph as an empty set.

In the last chapter, you stored all the neighbors of a node in the hash table, like this:

Math summary: This expression defines a graph mapping for a specific node. It assigns a list containing the names alice, bob, and claire as the neighbors for the node labeled you.

But this time, you need to store the neighbors and the cost for getting to that neighbor. For example, Start has two neighbors, A and B.

Image summary: A diagram showing a start node with two directed edges leading to nodes A and B. The edge to node A has a cost of 6, while the edge to node B has a cost of 2. The takeaway is that reaching node B is less costly than reaching node A from the start.

How do you represent the weights of those edges? Why not just use another hash table?

Code summary: This snippet initializes a weighted directed graph by creating a start node and defining weighted edges to nodes a and b with values of 6 and 2, respectively.

Image summary: A simple drawing of a hash table with a label stating, "THIS HASH TABLE HAS MORE HASHTABLES INSIDE," and an arrow pointing to one of its entries. The image is a humorous illustration depicting the concept of recursive data structures.

So graph["start"] is a hash table. You can get all the neighbors for Start like this:

Code summary: This snippet demonstrates how to access the immediate neighbors of a starting node in a graph represented as a dictionary, printing the keys associated with the start node to identify all outgoing edges.

There's an edge from Start to A and an edge from Start to B. What if you want to find the weights of those edges?

Code summary: This snippet demonstrates how to access and retrieve edge weights from a graph represented as a nested dictionary, specifically printing the distances from a start node to nodes a and b.

Let's add the rest of the nodes and their neighbors to the graph:

Code summary: This procedure constructs a weighted directed graph using a dictionary of dictionaries, where keys represent nodes and nested keys represent edges to destination nodes with their associated weights. It defines a network consisting of nodes a, b, and fin, establishing paths from b to both a and fin, and from a to fin.

The finish node doesn't have any neighbors.

The full graph hash table looks like this.

Image summary: A hand-drawn diagram of a nested structure where entries labeled START, A, B, and FIN lead to smaller tables containing keys and values. Arrows point to these sub-structures with the text "THESE ARE ALL HASH TABLES." The diagram illustrates a recursive or hierarchical organization of data using hash tables.

Next you need a hash table to store the costs for each node.

Image summary: A hand-drawn diagram of a table labeled COSTS, containing three rows and two columns. The rows are labeled A, B, and FIN, and the corresponding values in the second column are 6, 2, and the infinity symbol. The diagram serves to list costs associated with different categories, showing that the cost for FIN is infinite.

The cost of a node is how long it takes to get to that node from the start. You know it takes 2 minutes from Start to node B. You know it takes 6 minutes to get to node A (although you may find a path that takes less time). You don't know how long it takes to get to the finish.

If you don't know the cost yet, you put down infinity. Can you represent infinity in Python? Turns out, you can:

Code summary: This statement initializes a variable named infinity to the floating-point representation of infinity, providing a standard upper bound for comparison operations in subsequent calculations.

Here's the code to make the costs table:

Code summary: This snippet initializes a costs dictionary to track the cumulative distance from a starting point to various nodes in a graph. It assigns specific numeric costs to nodes a and b, while setting the destination node fin to infinity to represent an initially unknown shortest path.

You also need another hash table for the parents:

Image summary: A hand-drawn diagram of a grid with three rows and two columns. The left column contains the labels A, B, and FIN, while the right column contains the labels START, START, and a dash. The diagram depicts a basic mapping or relationship between these sets of labels.

Here's the code to make the hash table for the parents:

Code summary: This procedure initializes a parent-child mapping using a dictionary to define a hierarchical or graph-based structure. It assigns a starting node to elements a and b, while designating the element fin as the terminal node by setting its parent to null.

Finally, you need an array to keep track of all the nodes you've already processed, because you don't need to process a node more than once:

Code summary: This snippet initializes an empty list named processed, which serves as a container to store elements after they have been handled by a subsequent operation.

That's all the setup. Now let's look at the algorithm.

Image summary: A flow diagram of a node-processing algorithm. The process begins with a loop that continues while nodes remain to be processed, sequentially grabbing the node closest to the start, updating the costs for its neighbors, updating parents if neighbor costs change, and finally marking the node as processed before looping back. The diagram illustrates the iterative mechanism for updating path costs across a network of nodes.

I'll show you the code first and then walk through it. Here's the code:

Code summary: This implementation of Dijkstra's algorithm finds the shortest path from a starting point to all other nodes in a graph. It iteratively selects the unprocessed node with the lowest current cost to explore its neighbors. For each neighbor, it calculates if traveling through the current node provides a cheaper path than previously known; if so, it updates the neighbor's minimum cost and records the current node as its parent. This process continues until all reachable nodes are processed, resulting in a map of minimum costs and a parent tracking system to reconstruct the shortest paths.

That's Dijkstra's algorithm in Python! I'll show you the code for the function later. First, let's see this find_lowest_cost node algorithm code in action.

Find the node with the lowest cost.

Image summary: A diagram illustrating a function call where the input is a table of costs for nodes A, B, and FIN, and the function find_lowest_cost_node(costs) identifies the node with the minimum value. Since node B has the lowest cost of 2, the result is that the node is B. The point is to demonstrate how the lowest cost node is selected from a list of options.

Get the cost and neighbors of that node.

Image summary: A diagram illustrating a graph representation using a hash table. It shows code snippets for retrieving a node's cost and its neighbors, with an example graph table where the start node connects to nodes A and B, node A connects to the finish node, and node B connects to both A and the finish node. The purpose is to demonstrate how a graph can be implemented as a map of nodes to their respective neighbors and associated weights.

Loop through the neighbors.

Image summary: A hand-drawn diagram explaining a programming loop. It shows a for-loop iterating over the keys of a neighbors object, where a table of keys and values contains the entries A:3 and FIN:5. The diagram illustrates that the loop iterates through a list of nodes containing A and FIN, with n representing the current node, such as A. The purpose is to visualize how a loop retrieves keys from a key-value data structure.

Each node has a cost. The cost is how long it takes to get to that node from the start. Here, you're calculating how long it would take to get to node A if you went Start greater than node B greater than node A, instead of Start greater than node A.

Math summary: This computation calculates a new cost for reaching node A by traveling through node B. It adds the cost of node B, which is two, to the distance from node B to node A, which is three, resulting in a total new cost of five.

Let's compare those costs.

Math summary: This expression performs a conditional comparison to determine if a current cost exceeds a new cost. It evaluates the cost at a specific index against a new cost value to trigger a specific action.

Image summary: A handwritten diagram illustrating a cost update step in a pathfinding algorithm, such as Dijkstra's. It shows a comparison where the existing cost to reach node A is 6, but a new path through node B offers a lower cost of 5. The accompanying code snippet and graphs demonstrate that if the new cost is lower than the old cost, the path to node A is updated. The point is to visualize the process of relaxing an edge to find a more efficient path to a node.

You found a shorter path to node A! Update the cost.

Image summary: A handwritten diagram illustrating a data update operation. On the left, the code snippet costs[n] = new_cost is annotated to show that n is "A" and new_cost is 5; on the right, a table with rows A, B, and FIN shows the value for row A being updated to 5. The image demonstrates how a specific value in a lookup table is assigned using an index and a new cost value.

Math summary: This operation updates the cost associated with node A in a costs list. It assigns the value of new-cost to the fifth position of the costs array.

The new path goes through node B, so set B as the new parent.

Image summary: A hand-drawn diagram and text illustrating a mapping process. On the right, a grid shows a transition where 'B' is highlighted and pointed to by an arrow, with 'START' and 'FIN' markers indicating a sequence. On the left, the text 'parents[n] = node' is annotated with arrows linking 'A' to the index and 'B' to the node. The figure depicts how a node B is associated with a parent A within a data structure.

Math summary: This operation updates the parent of node n. It assigns the value of node A as the new parent for that node.

Ok, you're back at the top of the loop. The next neighbor for is the Finish node.

Image summary: A handwritten snippet of Python code showing a loop iterating through the keys of a dictionary called neighbors. An arrow points from the variable n to a box containing the values A and FIN, with a note stating that n is "FIN". The image illustrates the process of iterating through dictionary keys to identify a specific neighbor.

How long does it take to get to the finish if you go through node B?

Math summary: This expression calculates the new cost to reach node B. It adds the existing cost of two to the distance from node B to the finish, which is five, resulting in a total of seven.

It takes 7 minutes. The previous cost was infinity minutes, and 7 minutes is less than that.

Image summary: A handwritten diagram illustrating a conditional logic statement for updating costs. It shows a code snippet, "if costs[n] > new_cost:", with an arrow pointing to a costs array containing values "FIN" and infinity, and another arrow pointing to the number 7. Accompanying text notes that there was no cost to the finish before this step. The diagram depicts the mechanism for updating a pathfinding cost when a cheaper route to a destination is discovered.

Set the new cost and the new parent for the Finish node.

Image summary: A hand-drawn diagram showing a mapping between a line of code and a table labeled COSTS. The code costs[n] = new.cost has arrows pointing from the index n to the table entry FIN and from the value new.cost to the table entry 7. The table contains three rows with entries A: 5, B: 2, and FIN: 7. The diagram illustrates the process of updating a specific cost value in a table.

Image summary: A hand-drawn diagram illustrating a parent-pointer representation for pathfinding. It shows a 3x2 grid of nodes containing labels A, B, START, and FIN, alongside a formula parents[n] = node where labels "FIN" and "B" are mapped to indices. The diagram demonstrates how a path from a start node to a finish node can be traced backward using a parents array.

Ok, you updated the costs for all the neighbors of node B. Mark it as processed.

Image summary: A handwritten diagram showing a line of code, "processed.append(node)", with an arrow pointing from the letter "B" toward the code. To the right, the text "PROCESSED NODES:" is followed by the letter "B" inside a box. The image illustrates the process of adding node B to a list of processed nodes.

Find the next node to process.

Image summary: A handwritten diagram illustrating a function call to find the lowest cost node. The function find_Lowest_cost_node(costs) is shown selecting node A from a table of costs, where A has a cost of 5, while node B is crossed out as already processed and node FIN has a higher cost of 7. The diagram demonstrates the process of identifying the cheapest unprocessed node in a cost table.

Get the cost and neighbors for node A.

Image summary: A handwritten diagram showing two lines of code and associated memory mappings. The first line assigns a value from a costs array to a cost variable, with an arrow pointing from the number 5 to the variable. The second line assigns a value from a graph array to a neighbors variable, with an arrow pointing from a memory block containing FIN and 1 to the variable. The figure illustrates how specific values from data structures are mapped to variables during program execution.

Math summary: This operation retrieves the cost associated with a specific node. It assigns the value stored in the costs list at the position of that node to the cost variable.

Node A only has one neighbor: the Finish node.

Image summary: A handwritten snippet of Python code reading "for n in neighbors.keys():" with annotations. An arrow points from the word "FIN" to the variable "n", and a bracket groups the expression "neighbors.keys()" with a label "FIN" below it. The image illustrates the concept of mapping specific code elements to a label.

Currently it takes 7 minutes to get to the Finish node. How long would it take to get there if you went through node A?

: Image summary: A handwritten diagram illustrating a pathfinding cost update. It shows a formula where a new cost is calculated by adding the cost to reach node A (5) and the distance from A to the finish (1), totaling 6. This new cost is compared to the existing cost to reach the finish (7), and because the new cost is lower, the path is updated. Two graphs visualize this, showing the path shifting from Start-B-Finish to Start-A-Finish. The point is to demonstrate how a shortest-path algorithm updates the cost of a node when a more efficient route is found.

Math summary: This expression calculates a new cost by adding the distance from node A to the finish to the current cost of getting to node A. It determines that the new cost is six and checks if this value is less than the previously recorded cost for that node.

A table with D equals 2, Fin equals 7, and Costs.

down arrow

Old Cost

to Get to

the Finish 7

down arrow

Cost if we

Go through A 6

It's faster to get to Finish from node A! Let's update the cost and parent.

Image summary: A hand-drawn diagram showing a table labeled COSTS with three rows containing pairs: A and 5, B and 2, and FIN and 6. To the left, an equation costs[n] = new_cost is shown, with arrows mapping "FIN" to the index n and 6 to new_cost. The diagram illustrates the process of updating a cost value for a specific key in a table.

Image summary: A hand-drawn diagram illustrating a pathfinding or state-tracking concept. It shows a 3x2 grid containing labels A, B, START, and FIN, alongside a formula defining a parents array where the node A is the parent of FIN. The image depicts the logic used to reconstruct a path from a finish point back to a start point in a grid-based environment.

Math summary: This operation updates a parents array to record the path to a specific node. It assigns node A as the parent of the finish node to indicate a faster route.

Table summary: A mapping of three items where A corresponds to B, B corresponds to START, and FIN corresponds to A'.

Once you've processed all the nodes, the algorithm is over. I hope the walkthrough helped you understand the algorithm a little better. Finding the lowest-cost node is pretty easy with the find_lowest_cost node function. Here it is in code:

Code summary: A, find_lowest_cost_node, identifies the node with the minimum associated cost from a collection of costs. It iterates through all available nodes to find the lowest value that has not yet been processed, returning the identifier of that node to determine the next priority for exploration.

Exercise

7.1 In each of these graphs, what is the weight of the shortest path from start to finish?

Figure 7.1 summary: Two diagrams of weighted directed graphs showing paths from a start node to a finish node. The top graph contains only positive edge weights, while the bottom graph includes a negative edge weight of -1. These examples illustrate how different edge weights affect the search for the shortest path from start to finish.

Image summary: A diagram of a directed graph with five nodes and four edges. The path starts at a node labeled START, moves to a second node with a weight of 1phi, then can either proceed to a third node with a weight of 2phi or move to a fourth node with a weight of 1. From the fourth node, an edge with weight 1 leads back to the third node, which then connects to the node labeled FINISH with a weight of 3phi. The diagram illustrates a weighted network of possible paths from a start point to a finish point.

Recap

- Breadth-first search is used to calculate the shortest path for an unweighted graph.

- Dijkstra's algorithm is used to calculate the shortest path for a weighted graph.

• Dijkstra's algorithm works when all the weights are positive.

• If you have negative weights, use the Bellman-Ford algorithm.

In this chapter

- You learn how to tackle the impossible: problems that have no fast algorithmic solution (N.P-complete problems).

- You learn how to identify such problems when you see them, so you don't waste time trying to find a fast algorithm for them.

- You learn about approximation algorithms, which you can use to find an approximate solution to an N.P-complete problem quickly.

- You learn about the greedy strategy, a very simple problem-solving strategy.

The classroom scheduling problem

Suppose you have a classroom and want to hold as many classes here as possible. You get a list of classes.

: Table summary: A class schedule with sessions running from 9 AM to 12 PM. ART starts at 9 AM and ends at 10 AM, followed by ENG from 9:30 AM to 10:30 AM, MATH from 10 AM to 11 AM, CS from 10:30 AM to 11:30 AM, and MUSIC from 11 AM to 12 PM.

You can't hold all of these classes in there, because some of them overlap.

: Image summary: A timeline from 9 to 12 showing the schedules of five subjects. Art runs from 9 to 10, English from 9:30 to 10:30, Math from 10 to 11, Computer Science from 10:30 to 11:30, and Music from 11 to 12. The point is that each subject's session overlaps with the one preceding and following it by 30 minutes.

You want to hold as many classes as possible in this classroom. How do you pick what set of classes to hold, so that you get the biggest set of classes possible?

Sounds like a hard problem, right? Actually, the algorithm is so easy, it might surprise you. Here's how it works:

1. Pick the class that ends the soonest. This is the first class you'll hold in this classroom.

2. Now, you have to pick a class that starts after the first class. Again, pick the class that ends the soonest. This is the second class you'll hold.

Keep doing this, and you'll end up with the answer! Let's try it out. Art ends the soonest, at 10 AM, so that's one of the classes you pick.

Table summary: A schedule of classes and their times. ART is listed with start and end times of q AM and 10 AM. ENG runs from 4:30AM to 10:30AM, MATH from 10AM to 11AM, CS from 10:30AM to 11:30AM, and MUSIC from 11AM to 12PM.

Now you need the next class that starts after 10 AM and ends the soonest.

Table summary: A schedule of classes and their times. ART is listed with start and end times of q AM and 10 AM. ENG runs from 4:30 AM to 10:30 AM, MATH from 10 AM to 11 AM, CS from 10:30 AM to 11:30 AM, and MUSIC from 11 AM to 12 PM.

English is out because it conflicts with Art, but Math works.

Finally, C.S conflicts with Math, but Music works.

Table summary: A schedule of classes with their start times, end times, and a status indicator. ART starts at q AM and ends at 10 AM with a checkmark. ENG runs from q:30 AM to 10:30 AM with an X. MATH is from 10 AM to 11 AM with a checkmark. CS is from 10:30 AM to 11:30 AM with an X. MUSIC runs from 11 AM to 12 PM with a checkmark.

So these are the three classes you'll hold in this classroom.

Table summary: The daily schedule allocates time blocks for three subjects. ART takes place from 9 to 10:30, MATH follows from 10:30 to 11:30, and MUSIC concludes the sequence from 11:30 to 12.

A lot of people tell me that this algorithm seems easy. It's too obvious, so it must be wrong. But that's the beauty of greedy algorithms: they're easy! A greedy algorithm is simple: at each step, pick the optimal move.

In this case, each time you pick a class, you pick the class that ends the soonest. In technical terms: at each step you pick the locally optimal solution, and in the end you're left with the globally optimal solution. Believe it or not, this simple algorithm finds the optimal solution to this scheduling problem!

Obviously, greedy algorithms don't always work. But they're simple to write! Let's look at another example.

The knapsack problem

Suppose you're a greedy thief. You're in a store with a knapsack, and there are all these items you can steal. But you can only take what you can fit in your knapsack. The knapsack can hold 35 pounds.

Image summary: A simple line drawing of a shopping bag with handles, labeled 35 lbs on the side. It is an illustration used to represent a specific weight.

You're trying to maximize the value of the items you put in your knapsack. What algorithm do you use?

Again, the greedy strategy is pretty simple:

1. Pick the most expensive thing that will fit in your knapsack.

2. Pick the next most expensive thing that will fit in your knapsack. And so on.

Except this time, it doesn't work! For example, suppose there are three items you can steal.

Your knapsack can hold 35 pounds of items. The stereo system is the most expensive, so you steal that. Now you don't have space for anything else.

Image summary: A hand-drawn diagram of a knapsack showing its total capacity of 35 lbs. The bag is partially filled with a stereo weighing 30 lbs, leaving 5 lbs of wasted capacity at the top. The illustration depicts a resource allocation problem where the item does not fully utilize the available capacity.

You got 3,000 dollars worth of goods. But wait! If you'd picked the laptop and the guitar instead, you could have had 3,500 dollars worth of loot!

Image summary: A hand-drawn diagram showing two stacked components labeled with their weights, where a guitar weighs 15 pounds and a laptop weighs 20 pounds. The figure illustrates the relative weight distribution of these two items.

Clearly, the greedy strategy doesn't give you the optimal solution here. But it gets you pretty close. In the next chapter, I'll explain how to calculate the correct solution.

But if you're a thief in a shopping center, you don't care about perfect. "Pretty good" is good enough.

Here's the takeaway from this second example: sometimes, perfect is the enemy of good. Sometimes all you need is an algorithm that solves the problem pretty well. And that's where greedy algorithms shine, because they're simple to write and usually get pretty close.

Exercises

8.1 You work for a furniture company, and you have to ship furniture all over the country. You need to pack your truck with boxes. All the boxes are of different sizes, and you're trying to maximize the space you use in each truck.

How would you pick boxes to maximize space? Come up with a greedy strategy. Will that give you the optimal solution?

8.2 You're going to Europe, and you have seven days to see everything you can. You assign a point value to each item (how much you want to see it) and estimate how long it takes. How can you maximize the point total (seeing all the things you really want to see) during your stay? Come up with a greedy strategy. Will that give you the optimal solution?

Let's look at one last example. This is an example where greedy algorithms are absolutely necessary.

The set-covering problem

Suppose you're starting a radio show. You want to reach listeners in all 50 states. You have to decide what stations to play on to reach all those listeners. It costs money to be on each station, so you're trying to minimize the number of stations you play on. You have a list of stations.

Table summary: The availability of five radio stations across various states. KONE is available in ID, NV, and UT; KTWO in WA, ID, and MT; KTHREE in OR, NV, and CA; KFOUR in NV and UT; and KFIVE in CA and AZ.

Image summary: A hand-drawn map of the United States where the interior is divided into various regions, each filled with a different pattern such as diagonal lines, dots, crosses, or swirls. This is a conceptual illustration, with no data or analytical result to report.

Each station covers a region, and there's overlap.

How do you figure out the smallest set of stations you can play on to cover all 50 states? Sounds easy, doesn't it? Turns out it's extremely hard. Here's how to do it:

1. List every possible subset of stations. This is called the power set. There are 2 to the n possible subsets.

Image summary: A diagram depicting three sets of words, labeled Set #1, Set #8, and Set #500. Each set contains words starting with the letter K followed by a number word, such as KONE and KTHREE in the first set, and KHUNDRED and KMIL in the last set. The diagram illustrates a sequence of sets containing modified number words.

Image summary: A diagram showing five overlapping regions labeled with US state abbreviations: WA, MT, ID, OR, NV, UT, CA, and AZ. Each region is numbered from 1 to 5. The diagram depicts the spatial relationships and overlaps between these geographic groupings.

2. From these, pick the set with the smallest number of stations that covers all 50 states.

The problem is, it takes a long time to calculate every possible subset of stations. It takes O 2 to the n) time, because there are 2 to the n stations. It's possible to do if you have a small set of 5 to 10 stations. But with all the examples here, think about what will happen if you have a lot of items. It takes much longer if you have more stations. Suppose you can calculate 10 subsets per second.

There's no algorithm that solves it fast enough! What can you do?

Table summary: Time taken increases drastically as the number of stations grows. For 5 stations, the time is 3.2 seconds, and for 32 stations, it jumps to 13.6 years. The table also includes two entries with phi symbols, showing a time of 2.4 seconds for one phi and 4 times 10 to the 21st power years for two phis.

Approximation algorithms

Greedy algorithms to the rescue! Here's a greedy algorithm that comes pretty close:

1. Pick the station that covers the most states that haven't been covered yet. It's okay if the station covers some states that have been covered already.

2. Repeat until all the states are covered.

This is called an approximation algorithm. When calculating the exact solution will take too much time, an approximation algorithm will work. Approximation algorithms are judged by

• How fast they are

- How close they are to the optimal solution

Greedy algorithms are a good choice because not only are they simple to come up with, but that simplicity means they usually run fast, too. In this case, the greedy algorithm runs in O (n squared) time, where n is the number of radio stations.

Let's see how this problem looks in code.

Code for setup

For this example, I'm going to use a subset of the states and the stations to keep things simple.

First, make a list of the states you want to cover:

Code summary: This procedure initializes a set of required state abbreviations by converting a list of specific US state codes into a set, ensuring unique identifiers for efficient membership lookups.

I used a set for this. A set is like a list, except that each item can show up only once in a set. Sets can't have duplicates. For example, suppose you had this list:

: Code summary: This code initializes a list named arr containing a sequence of integers with varying frequencies.

And you converted it to a set:

: Code summary: This operation converts a list or array into a set to remove all duplicate elements, returning a collection of unique values.

1, 2, and 3 all show up just once in a set.

Math summary: This expression performs a convert to set transformation on a list of numbers. It takes a list containing one one, two twos, and three threes and outputs a set containing only the unique values one, two, and three.

You also need the list of stations that you're choosing from. I chose to use a hash for this:

Code summary: This procedure initializes a dictionary named stations to map specific station identifiers to sets of associated state abbreviations, effectively creating a lookup table for the geographic coverage of each station.

The keys are station names, and the values are the states they cover. So in this example, the kone station covers Idaho, Nevada, and Utah. All the values are sets, too. Making everything a set will make your life easier, as you'll see soon.

Finally, you need something to hold the final set of stations you'll use:

Code summary: This operation initializes an empty set named final_stations, which serves as a unique collection to store and track the end-point stations of a journey or network.

Calculating the answer

Now you need to calculate what stations you'll use. Take a look at the image at right, and see if you can predict what stations you should use.

There can be more than one correct solution. You need to go through every station and pick the one that covers the most uncovered states. I'll call this best station:

Code summary: This procedure identifies the best station by iterating through a collection of stations and tracking which states are covered, aiming to find the station that optimizes coverage across the available states.

: Image summary: A hand-drawn Venn-style diagram featuring five overlapping regions labeled with US state abbreviations: WA and MT in region 2, OR in region 3, ID in region 1, NV and UT in region 4, and CA and AZ in region 5. The diagram illustrates the overlapping relationships or groupings between these specific Western states.

states covered is a set of all the states this station covers that haven't been covered yet. The for loop allows you to loop over every station to see which one is the best station. Let's look at the body of the for loop:

Code summary: This procedure identifies the best action by iterating through a set of available actions and evaluating which one maximizes a specific reward or value metric, returning the action that yields the highest result.

There's a funny-looking line here:

covered equals states needed and states for station

What's going on?

Sets

Suppose you have a set of fruits.

You also have a set of vegetables.

Image summary: A hand-drawn diagram showing an oval containing the words AVOCADO, TOMATO, and BANANA, with the label FRUITS written below the oval. The diagram serves to categorize these three items as fruits.

Image summary: A simple diagram showing an oval containing the words BEETS, CARROTS, and TOMATO, with the label VEGETABLES written below the oval. The diagram illustrates that beets, carrots, and tomatoes are categorized as vegetables.

When you have two sets, you can do some fun things with them.

Here are some things you can do with sets.

Image summary: A series of hand-drawn diagrams illustrating set operations using fruits and vegetables. The top left shows a union as a single circle containing all items; the top right shows an intersection as the overlap between two circles, containing only the tomato; and the bottom shows a difference as the subtraction of one group from another, leaving only the avocado and banana. The figure uses these examples to visually define the mathematical concepts of union, intersection, and difference.

- A set union means “combine both sets.”

- A set intersection means “find the items that show up in both sets” (in this case, just the tomato).

- A set difference means “subtract the items in one set from the items in the other set.”

For example:

Code summary: DIFFERENCE demonstrates basic set operations in Python, showing how to combine or filter collections of items. It uses the pipe operator for set union to merge all unique elements, the ampersand for intersection to find common elements, and the minus sign for set difference to identify elements present in one set but not the other.

To recap:

- Sets are like lists, except sets can't have duplicates.

• You can do some interesting operations on sets, like union, intersection, and difference.

Back to the code

Let's get back to the original example.

This is a set intersection:

Code summary: This operation identifies the intersection between the set of required states and the states available for stationing, resulting in a set of states that are both needed and available to be covered.

covered is a set of states that were in both states needed and states_for station. So covered is the set of uncovered states that this station covers! Next you check whether this station covers more states than the current best station:

: This logic implements a greedy selection step to maximize coverage. It compares the number of states covered by a current candidate station against the best result found so far, updating the best station and the set of covered states whenever a candidate provides superior coverage.

If so, this station is the new best station. Finally, after the for loop is over, you add best station to the final list of stations:

Code summary: This operation updates a collection of final stations by adding the best-performing or most optimal station identified during the selection process.

Image summary: A hand-drawn diagram consisting of five overlapping and nested regions, each containing state abbreviations (WA, MT, ID, OR, NV, UT, CA, AZ) and a circled number from 1 to 5. The layout uses interlocking boundaries to group different sets of states, illustrating a complex set of overlapping relationships or categories.

You also need to update states needed. Because this station covers some states, those states aren't needed anymore:

: Code summary: This operation updates the remaining number of states required by subtracting the number of states already covered, effectively tracking progress toward a total state coverage goal.

And you loop until states needed is empty. Here's the full code for the loop:

Code summary: This greedy set-cover algorithm iteratively selects the station that covers the largest number of remaining required states. In each iteration, it evaluates all available stations to find the one with the maximum overlap with the current needs, adds that station to the final selection, and removes the covered states from the requirement list. This process repeats until all needed states are accounted for, resulting in a minimal set of stations that provide full coverage.

Finally, you can print final stations, and you should see this:

Code summary: This snippet outputs a set containing the final stations reached, specifically ktwo, kthree, kone, and kfive.

Is that what you expected? Instead of stations 1, 2, 3, and 5, you could have chosen stations 2, 3, 4, and 5. Let's compare the run time of the greedy algorithm to the exact algorithm.

: The O(n^2) GREEDY ALGORITHM is significantly faster than the O(n!) EXACT ALGORITHM as the number of stations increases. For 5 stations, the GREEDY ALGORITHM takes 2.5 seconds compared to 3.2 seconds for the EXACT ALGORITHM. However, as the scale grows to 32 stations, the EXACT ALGORITHM requires 13.6 years, while the GREEDY ALGORITHM remains efficient at 1 phi 2.4 seconds. At the highest scale of 1 phi phi stations, the EXACT ALGORITHM takes 4 times 10 to the 24th power years, whereas the GREEDY ALGORITHM completes in 16.67 minutes.

Exercises

For each of these algorithms, say whether it's a greedy algorithm or not.

8.3 Quicksort

8.4 Breadth-first search

8.5 Dijkstra's algorithm

N.P-complete Problems

To solve the set-covering problem, you had to calculate every possible set.

Image summary: A diagram showing three sets of words labeled Set #1, Set #8, and Set #500. Each set contains words that begin with the letter K followed by a number word, such as KONE, KTHREE, and KFIVE in Set #1; KTEN, KTWENTY, and KFIFTY in Set #8; and KHUNDRED, KMIL, and KTHOU in Set #500. The diagram illustrates a pattern of adding a K prefix to numeric terms across a sequence of sets.

Maybe you were reminded of the traveling salesperson problem from chapter 1. In this problem, a salesperson has to visit five different cities.

Image summary: A hand-drawn map of the San Francisco Bay Area with pins marking the locations of Marin, Berkeley, San Francisco, Fremont, and Palo Alto. The image is a simple illustration used to show the relative geographic positions of these five cities around the bay.

And he's trying to figure out the shortest route that will take him to all five cities. To find the shortest route, you first have to calculate every possible route.

Image summary: A series of three hand-drawn diagrams showing different paths between the same set of points, each with a corresponding total distance in miles. The paths vary in sequence and direction, with distances of 120, 103, and 133 miles respectively. The figure illustrates how different routing sequences between the same locations result in different total travel distances.

How many routes do you have to calculate for five cities?

Traveling salesperson, step by step

Let's start small. Suppose you only have two cities. There are two routes to choose from.

Starting at Marin: Starting at San Fransisko

Image summary: A diagram consisting of two panels showing the direction of travel between two locations. Panel 1 shows a downward arrow from Marin to San Francisco, and panel 2 shows an upward arrow from San Francisco to Marin. The figure illustrates the opposite directions of travel between these two regions.

Same route or different?

You may think this should be the same route. After all, isn't S.F greater than Marin the same distance as Marin greater than S.F? Not necessarily. Some cities (like San Francisco) have a lot of one-way streets, so you can't go back the way you came. You might also have to go 1 or 2 miles out of the way to find an on-ramp to a highway. So these two routes aren't necessarily the same.

You may be wondering, “In the traveling salesperson problem, is there a specific city you need to start from?” For example, let's say I'm the traveling salesperson. I live in San Francisco, and I need to go to four other cities. San Francisco would be my start city.

But sometimes the start city isn't set. Suppose you're FedEx, trying to deliver a package to the Bay Area. The package is being flown in from Chicago to one of 50 FedEx locations in the Bay Area. Then that package will go on a truck that will travel to different locations delivering packages. Which location should it get flown to? Here the start location is unknown. It's up to you to compute the optimal path and start location for the traveling salesperson.

The running time for both versions is the same. But it's an easier example if there's no defined start city, so I'll go with that version.

Two cities = two possible routes.

3 cities

Now suppose you add one more city. How many possible routes are there?

If you start at Berkeley, you have two more cities to visit.

Starting at Berklee:

Image summary: Two diagrams showing directed relationships between Berkeley, Marin, and SF. In the first diagram, arrows flow from Berkeley to Marin and from Marin to SF. In the second diagram, arrows flow from Berkeley to SF and from SF to Marin. The figures illustrate two different directional flow patterns between the same three locations.

There are six total routes, two for each city you can start at.

Starting at Berklee:

Image summary: A series of six diagrams illustrating different directional paths between three locations: Berkeley, Marin, and San Francisco. The first four diagrams show paths starting at Berkeley or Marin, while the final two show paths starting at San Francisco. The diagrams visualize different permutations of travel sequences between these three cities.

So three cities = six possible routes.

4 cities

Let's add another city, Fremont. Now suppose you start at Fremont.

Starting at Fremont:

Image summary: A set of hand-drawn diagrams showing different sequences of cities (Marin, Berkeley, San Francisco, and Fremont) connected by arrows. The diagrams are organized into three conditional scenarios based on which city is the second in the sequence, illustrating how the order of visits changes the path between the cities. The point is to visualize different permutations of a travel route.

There are six possible routes starting from Fremont. And hey! They look a lot like the six routes you calculated earlier, when you had only three cities. Except now all the routes have an additional city, Fremont! There's a pattern here. Suppose you have four cities, and you pick a start city, Fremont. There are three cities left.

And you know that if there are three cities, there are six different routes for getting between those cities. If you start at Fremont, there are six possible routes. You could also start at one of the other cities.

Math summary: This expression identifies starting locations for travel routes. It lists the starting points as Atmarin and San Francisco.

Image summary: A text-based image showing three different starting locations: Marin, San Francisco, and Berkeley. For each location, it states there are 6 possible routes. The point is that the number of possible routes is the same regardless of the starting city.

=6 Possible Routes =

Four possible start cities, with six possible routes for each start city equals 4 times 6 equals 24 possible routes.

Do you see a pattern? Every time you add a new city, you're increasing the number of routes you have to calculate.

Image summary: A handwritten mathematical derivation showing the relationship between the number of cities and the total number of possible routes. As the number of cities increases from 1 to 5, the total routes grow factorially from 1 to 120, calculated by multiplying the number of start cities by the number of routes for the previous city count. The point is to demonstrate how the number of possible routes increases exponentially as more cities are added.

How many possible routes are there for six cities? If you guessed 720, you're right. 5,040 for 7 cities, 40,320 for 8 cities.

This is called the factorial function (remember reading about this in chapter 3?). So 5! = 120. Suppose you have 10 cities. How many possible routes are there? 10! = 3,628,800. You have to calculate over 3 million possible routes for 10 cities. As you can see, the number of possible routes becomes big very fast! This is why it's impossible to compute the "correct" solution for the traveling-salesperson problem if you have a large number of cities.

The traveling-salesperson problem and the set-covering problem both have something in common: you calculate every possible solution and pick the smallest/shortest one. Both of these problems are N.P-complete.

Approximating

What's a good approximation algorithm for the traveling salesperson? Something simple that finds a short path. See if you can come up with an answer before reading on.

Here's how I would do it: arbitrarily pick a start city. Then, each time the salesperson has to pick the next city to visit, they pick the closest unvisited city. Suppose they start in Marin.

Image summary: A diagram showing a path between five cities with distances labeled between them. The path goes from Marin to San Francisco (10 miles), then to Berkeley (14 miles), then to Fremont (31 miles), and finally to Palo Alto (16 miles). The total distance of this route is 71 miles.

Here's the short explanation of N.P-completeness: some problems are famously hard to solve. The traveling salesperson and the set-covering problem are two examples. A lot of smart people think that it's not possible to write an algorithm that will solve these problems quickly.

How Do You Tell If a Problem Is N.P-complete?

Jonah is picking players for his fantasy football team. He has a list of abilities he wants: good quarterback, good running back, good in rain, good under pressure, and so on. He has a list of players, where each player fulfills some abilities.

Table summary: A list of players and their abilities. Matt Forte is a RB, while Brendan Marshall and Aaron Rodgers are a WR and QB, respectively, both of whom are noted as being good under pressure.

Jonah needs a team that fulfills all his abilities, and the team size is limited. “Wait a second,” Jonah realizes. “This is a set-covering problem!”

Image summary: A hand-drawn Venn diagram showing three circles representing football positions: RB, QB, and WR. Matt is located exclusively in the RB circle, Brendan is in the WR circle, and Aaron is in the QB circle. Gup is positioned in the overlap between the QB and WR circles, indicating that Gup fulfills both roles.

Jonah can use the same approximation algorithm to create his team:

1. Find the player who fulfills the most abilities that haven't been fulfilled yet.

2. Repeat until the team fulfills all abilities (or you run out of space on the team).

N.P-complete problems show up everywhere! It's nice to know if the problem you're trying to solve is N.P-complete. At that point, you can stop trying to solve it perfectly, and solve it using an approximation algorithm instead. But it's hard to tell if a problem you're working on is N.P-complete. Usually there's a very small difference between a problem that's easy to solve and an N.P-complete problem. For example, in the previous chapters, I talked a lot about shortest paths. You know how to calculate the shortest way to get from point A to point B.

Image summary: A diagram of travel routes from Twin Peaks to the Golden Gate Bridge. From Twin Peaks, two paths begin with a walk; one leads to Bus #44, and the other leads to Bus #33. Bus #33 can either transfer to Bus #5L or continue to Bus #38L, both of which eventually merge with the Bus #44 route to take Bus #28 to the Golden Gate Bridge. The diagram illustrates the various transit combinations available to reach the destination.

But if you want to find the shortest path that connects several points, that's the traveling-salesperson problem, which is N.P-complete. The short answer: there's no easy way to tell if the problem you're working on is N.P-complete. Here are some giveaways:

- Your algorithm runs quickly with a handful of items but really slows down with more items.

• “All combinations of X” usually point to an N.P-complete problem.

- Do you have to calculate “every possible version” of X because you can't break it down into smaller sub-problems? Might be N.P-complete.

- If your problem involves a sequence (such as a sequence of cities, like traveling salesperson), and it's hard to solve, it might be N.P-complete.

- If your problem involves a set (like a set of radio stations) and it's hard to solve, it might be N.P-complete.

- Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely N.P-complete.

Exercises

8.6 A postman needs to deliver to 20 homes. He needs to find the shortest route that goes to all 20 homes. Is this an N.P-complete problem?

8.8 You're making a map of the U.S.A, and you need to color adjacent states with different colors. You have to find the minimum number of colors you need so that no two adjacent states are the same color. Is this an N.P-complete problem?

Recap

• Greedy algorithms optimize locally, hoping to end up with a global optimum.

• N.P-complete problems have no known fast solution.

• If you have an N.P-complete problem, your best bet is to use an approximation algorithm.

• Greedy algorithms are easy to write and fast to run, so they make good approximation algorithms.

In this chapter

- You learn dynamic programming, a technique to solve a hard problem by breaking it up into subproblems and solving those subproblems first.

- Using examples, you learn to how to come up with a dynamic programming solution to a new problem.

The knapsack problem

Let's revisit the knapsack problem from chapter 8. You're a thief with a knapsack that can carry 4 pounds of goods.

You have three items that you can put into the knapsack.

What items should you steal so that you steal the maximum money's worth of goods?

The simple solution

The simplest algorithm is this: you try every possible set of goods and find the set that gives you the most value.

Image summary: A hand-drawn diagram illustrating a knapsack problem with items of different values and sizes. Individual items include a guitar for 1500, a stereo for 3000, and a laptop for 2000. Various combinations are tested, but most are marked as not fitting; only the combination of a guitar and laptop fits, yielding a total of 3500. The point is that the guitar and laptop combination provides the maximum value that fits within the container's capacity.

This works, but it's really slow. For 3 items, you have to calculate 8 possible sets. For 4 items, you have to calculate 16 sets. With every item you add, the number of sets you have to calculate doubles! This algorithm takes O 2 to the n) time, which is very, very slow.

Image summary: A hand-drawn diagram showing grids of increasing size to illustrate the growth of possible sets based on the number of items. For 3 items, there are 8 possible sets; for 4 items, 16 sets; and for 5 items, 32 sets. A note at the bottom states that for 32 items, there are approximately 4 billion possible sets. The point is to demonstrate that the number of possible sets grows exponentially as more items are added.

That's impractical for any reasonable number of goods. In chapter 8, you saw how to calculate an approximate solution. That solution will be close to the optimal solution, but it may not be the optimal solution.

So how do you calculate the optimal solution?

Dynamic programming

Answer: With dynamic programming! Let's see how the dynamic-programming algorithm works here. Dynamic programming starts by solving subproblems and builds up to solving the big problem.

For the knapsack problem, you'll start by solving the problem for smaller knapsacks (or "sub-knapsacks") and then work up to solving the original problem.

Image summary: A hand-drawn diagram showing a small bag labeled 1 lb added to a larger bag labeled 3 lb, resulting in a single large bag containing both weights. The final total is labeled as 4 lb, illustrating a basic addition problem using bags of weights.

Dynamic programming is a hard concept, so don't worry if you don't get it right away. We're going to look at a lot of examples.

I'll start by showing you the algorithm in action first. After you've seen it in action once, you'll have a lot of questions! I'll do my best to address every question.

Every dynamic-programming algorithm starts with a grid. Here's a grid for the knapsack problem.

Image summary: A hand-drawn diagram of a table where columns represent knapsack sizes from 1 to 4 pounds and rows represent items to choose from, specifically a guitar, stereo, and laptop. This structure illustrates the setup for a dynamic programming approach to the knapsack problem, mapping item choices against available capacity.

The rows of the grid are the items, and the columns are knapsack weights from 1 pounds to 4 pounds. You need all of those columns because they will help you calculate the values of the sub-knapsacks.

The grid starts out empty. You're going to fill in each cell of the grid. Once the grid is filled in, you'll have your answer to this problem!

Please follow along. Make your own grid, and we'll fill it out together.

The guitar row

I'll show you the exact formula for calculating this grid later. Let's do a walkthrough first. Start with the first row.

Image summary: A hand-drawn grid with four numbered columns and three rows labeled Guitar, Stereo, and Laptop. The row for Guitar is outlined with a thicker border than the others. The image depicts a simple table structure for organizing or categorizing these three items across four numbered categories.

This is the guitar row, which means you're trying to fit the guitar into the knapsack. At each cell, there's a simple decision: do you steal the guitar or not? Remember, you're trying to find the set of items to steal that will give you the most value.

The first cell has a knapsack of capacity 1 pounds. The guitar is also 1 pounds, which means it fits into the knapsack! So the value of this cell is $1,500, and it contains a guitar.

Let's start filling in the grid.

Table summary: A list of items including GUITAR, STEREO, and LAPTOP, where the GUITAR is priced at $1500 G.

Like this, each cell in the grid will contain a list of all the items that fit into the knapsack at that point.

Let's look at the next cell. Here you have a knapsack of capacity 2 pounds. Well, the guitar will definitely fit in there!

Table summary: A GUITAR is priced at 1500 G across two categories, while no data is provided for the STEREO or LAPTOP.

The same for the rest of the cells in this row. Remember, this is the first row, so you have only the guitar to choose from. You're pretending that the other two items aren't available to steal right now.

Table summary: A GUITAR is priced at 1500 G across all four listed categories, while no pricing information is provided for the STEREO or LAPTOP.

At this point, you're probably confused. Why are you doing this for knapsacks with a capacity of 1 pounds, 2 pounds, and so on, when the problem talks about a 4 pounds knapsack? Remember how I told you that dynamic programming starts with a small problem and builds up to the big problem? You're solving subproblems here that will help you to solve the big problem. Read on, and things will become clearer.

At this point, your grid should look like this.

Table summary: A pricing list for musical and electronic equipment. The GUITAR is priced at $1500 G across three separate columns. The STEREO and LAPTOP entries are listed but do not have associated prices.

Remember, you're trying to maximize the value of the knapsack. This row represents the current best guess for this max. So right now, according to this row, if you had a knapsack of capacity 4 pounds, the max value you could put in there would be $1,500.

Table summary: A GUITAR is priced at 1500 G across three different categories or instances, while the STEREO and LAPTOP entries contain no listed values.

You know that's not the final solution. As we go through the algorithm, you'll refine your estimate.

The stereo row

Let's do the next row. This one is for the stereo. Now that you're on the second row, you can steal the stereo or the guitar.

At every row, you can steal the item at that row or the items in the rows above it. So you can't choose to steal the laptop right now, but you can steal the stereo and/or the guitar. Let's start with the first cell, a knapsack of capacity 1 pounds. The current max value you can fit into a knapsack of 1 pounds is $1,500.

Image summary: A hand-drawn table illustrating a dynamic programming approach to the knapsack problem. The table tracks the maximum value for knapsacks of increasing capacities (columns 1 through 4) as items like a guitar, stereo, and laptop are considered (rows). The first cell shows a value of $1500 for a 1lb knapsack containing a guitar, with labels indicating how current and new maximum values are calculated. The purpose is to demonstrate how the optimal value is iteratively updated as more items and capacities are evaluated.

Should you steal the stereo or not?

You have a knapsack of capacity 1 pounds. Will the stereo fit in there? Nope, it's too heavy! Because you can't fit the stereo, $1,500 remains the max guess for a 1 pounds knapsack.

Table summary: A set of values where the first row contains the numbers 1, 2, 3, and 4, and the second row contains $1500G across all four columns. The third row contains $1500G in the first column, while all other cells are empty.

Same thing for the next two cells. These knapsacks have a capacity of 2 pounds and 3 pounds. The old max value for both was $1,500.

: Table summary: For items 1, 2, 3, and 4, there are consistent values of 1500 G, with the first row for all four items indicating a downward trend.

The stereo still doesn't fit, so your guesses remain unchanged.

What if you have a knapsack of capacity 4 pounds? Aha: the stereo finally fits! The old max value was 1,500 dollars, but if you put the stereo in there instead, the value is 3,000 dollars! Let's take the stereo.

: Table summary: A grid of values where most entries are 1500 G, except for the final entry in the fourth column, which is 3000 G.

You just updated your estimate! If you have a 4 pounds knapsack, you can fit at least $3,000 worth of goods in it. You can see from the grid that you're incrementally updating your estimate.

Table summary: GUITAR and STEREO equipment specifications across four numbered categories. For GUITAR, all four categories are rated at 1500 G. For STEREO, the first three categories are rated at 1500 G with a downward arrow, while the fourth category is rated at 3000 G with a downward arrow. The LAPTOP category is listed but contains no data.

The laptop row

Let's do the same thing with the laptop! The laptop weighs 3 pounds, so it won't fit into a 1 pounds or a 2 pounds knapsack. The estimate for the first two cells stays at $1,500.

Table summary: Pricing and category data for three items. GUITAR is priced at $1500 and categorized as G across all three columns. STEREO is priced at $1500 and categorized as G in the first two columns, but increases to $3000 and is categorized as S in the third. LAPTOP is priced at $1500 and categorized as G in the first two columns, with no data provided for the third.

At 3 pounds, the old estimate was 1,500 dollars. But you can choose the laptop instead, and that's worth 2,000 dollars. So the new max estimate is 2,000 dollars!

: Table summary: Pricing and categorization for three items across three different scenarios. GUITAR and STEREO maintain a consistent price of $1500 and a category of G across all scenarios. LAPTOP is priced at $1500 with category G in the first two scenarios, but increases to $2000 and changes to category L in the third scenario.

At 4 pounds, things get really interesting. This is an important part. The current estimate is 3,000 dollars. You can put the laptop in the knapsack, but it's only worth 2,000 dollars.

$3000 vs $2000 Sterered Laptop

Hmm, that's not as good as the old estimate. But wait! The laptop weighs only 3 pounds, so you have 1 pounds free! You could put something in this 1 pounds.

Math summary: This expression calculates the value of free space available in a container. It determines this by multiplying three thousand by the value of a laptop and a ratio of three units of pressure over one pound of force.

What's the maximum value you can fit into 1 pounds of space? Well, you've been calculating it all along.

Image summary: A grid-based diagram illustrating a knapsack-style optimization problem for a maximum value of 1 lb. The columns represent capacity units, and rows represent items, with values and labels indicating the optimal selection path. The diagram shows that by selecting items marked G, S, and L, the total value is maximized, with the final cell highlighting a value of $2000 as the optimal outcome.

According to the last best estimate, you can fit the guitar into that 1 pounds space, and that's worth $1,500. So the real comparison is as follows.

Math summary: This expression compares the value of a single stereo against the combined value of a laptop and a guitar. It weighs three thousand dollars against the sum of two thousand dollars and one thousand five hundred dollars.

You might have been wondering why you were calculating max values for smaller knapsacks. I hope now it makes sense! When you have space left over, you can use the answers to those subproblems to figure out what will fit in that space. It's better to take the laptop + the guitar for $3,500.

The final grid looks like this.

Image summary: A grid-based diagram illustrating a calculation process across four columns and three rows labeled Guitar, Stereo, and Laptop. The values start at 1500 for all items in columns 1 and 2, with specific increases in columns 3 and 4 for Stereo and Laptop, culminating in a final value of 3500 in the bottom-right cell labeled as the answer. The diagram depicts a step-by-step accumulation of values based on item types.

There's the answer: the maximum value that will fit in the knapsack is $3,500, made up of a guitar and a laptop!

Maybe you think that I used a different formula to calculate the value of that last cell. That's because I skipped some unnecessary complexity when filling in the values of the earlier cells. Each cell's value gets calculated with the same formula. Here it is.

Image summary: A handwritten mathematical formula defining the value of a cell in a dynamic programming table, specifically for the knapsack problem. The value of cell [i][j] is the maximum of two options: the value of the previous cell [i-1][j], or the sum of the current item's value and the value of the remaining capacity found in cell [i-1][j minus item's weight]. This recurrence relation is used to determine the optimal value for a given capacity and set of items.

You can use this formula with every cell in this grid, and you should end up with the same grid I did. Remember how I talked about solving subproblems? You combined the solutions to two subproblems to solve the bigger problem.

Image summary: A hand-drawn illustration showing a simple addition problem with bags of items. A bag containing cables weighing 1 lb is added to a bag containing a tablet weighing 3 lb, resulting in a final bag containing both items weighing 4 lb. The image demonstrates the basic mathematical concept that the total weight is the sum of the individual parts.

Knapsack Problem F.A.Q

Maybe this still feels like magic. This section answers some common questions.

What happens if you add an item?

Suppose you realize there's a fourth item you can steal that you didn't notice before! You can also steal an iPhone.

Do you have to recalculate everything to account for this new item?

Nope. Remember, dynamic programming keeps progressively building on your estimate. So far, these are the max values.

Table summary: A distribution of monetary values across four categories, labeled 1 through 4. Categories 1, 2, and 3 primarily consist of 1500 G, though category 3 includes one instance of 2000 L. Category 4 shows a progression of increasing values, starting at 1500 G and rising to 3000 S and 3500 LG.

That means for a 4 pounds knapsack, you can steal $3,500 worth of goods. You thought that was the final max value. But let's add a row for the iPhone.

Table summary: A grid of values organized by columns 1 through 4. Most entries are 1500 G, but the values increase in the fourth column and the third row, reaching 3000 S in column 4, row 2, 2000 L in column 3, row 3, and peaking at 3500 LG in column 4, row 3.

iPhone 2000 116 Turns out you have a new max value! Try to fill in this new row before reading on.

Let's start with the first cell. The iPhone fits into the 1 pounds knapsack. The old max was 1,500 dollars, but the iPhone is worth 2,000 dollars. Let's take the iPhone instead.

Table summary: Pricing and categorization for four items. The GUITAR is consistently priced at $1500 G across three categories. The STEREO is $1500 G in the first two categories but increases to $3000 S in the third. The LAPTOP is $1500 G in the first two categories and $3500 LG in the third. Finally, the IPHONE is listed only in the first category at $2000 I.

In the next cell, you can fit the iPhone and the guitar.

Table summary: A pricing structure where most entries are 1500 G, with higher costs for larger or different categories. These include 3000 S, 2000 L, 3500 LG, 2000 I, and 3500 IG.

For cell 3, you can't do better than take the iPhone and the guitar again, so leave it as is.

For the last cell, things get interesting. The current max is $3,500. You can steal the iPhone instead, and you have 3 pounds of space left over.

$3500

Math summary: This expression calculates a total value based on a base amount of two thousand. It adds a fraction where an unknown value is divided by three pounds free to determine the final result.

Laptop + Guitar Those 3 pounds are worth 2,000 dollars! 2,000 dollars from the iPhone plus 2,000 dollars from the old subproblem: that's 4,000 dollars. A new max!

Here's the new final grid.

Table summary: Pricing and sizing options that increase across four tiers. The initial tier is uniform at 1500 G across all categories. As the tiers progress, prices and size labels increase, culminating in the final tier with values ranging from 3500 I to 4000 IL.

Question: Would the value of a column ever go down? Is this possible?

Table summary: Across four categories labeled 1 through 4, the second row shows a consistent value of 1500 dollars for all entries. In the third row, categories 1, 2, and 3 have no value, while category 4 has a value of 3000 dollars.

Think of an answer before reading on.

Answer: No. At every iteration, you're storing the current max estimate. The estimate can never get worse than it was before!

9.1 Suppose you can steal another item: an M.P.3 player. It weighs 1 pounds and is worth $1,000. Should you steal it?

What happens if you change the order of the rows?

Does the answer change? Suppose you fill the rows in this order: stereo, laptop, guitar. What does the grid look like? Fill out the grid for yourself before moving on.

Here's what the grid looks like.

Table summary: A grid of values across four columns and three rows. Most cells are empty, denoted by the null symbol. Notable entries include 3000 followed by a down arrow and S in the first row's fourth column; 2000 followed by a down arrow, L, a down arrow, and S in the second row's third column; and 1500 G in both the third row's first and second columns. The third row's third column contains a sequence starting with 2000, followed by a down arrow, L, a down arrow, S, a down arrow, and L G.

The answer doesn't change. The order of the rows doesn't matter.

Can you fill in the grid column-wise instead of row-wise?

Try it for yourself! For this problem, it doesn't make a difference. It could make a difference for other problems.

What happens if you add a smaller item?

Suppose you can steal a necklace. It weighs 0.5 pounds, and it's worth $1,000. So far, your grid assumes that all weights are integers. Now you decide to steal the necklace. You have 3.5 pounds left over.

What's the max value you can fit in 3.5 pounds? You don't know! You only calculated values for 1 pounds, 2 pounds, 3 pounds, and 4 pounds knapsacks. You need to know the value of a 3.5 pounds knapsack.

Because of the necklace, you have to account for finer granularity, so the grid has to change.

Table summary: A grid for recording data across eight numeric intervals from 0.5 to 4, with rows for GUITAR, STEREO, LAPTOP, and JEWELRY. All data cells for these four categories are currently empty.

Can you steal fractions of an item?

Suppose you're a thief in a grocery store. You can steal bags of lentils and rice. If a whole bag doesn't fit, you can open it and take as much as you can carry. So now it's not all or nothing—you can take a fraction of an item. How do you handle this using dynamic programming?

Answer: You can't. With the dynamic-programming solution, you either take the item or not. There's no way for it to figure out that you should take half an item.

But this case is also easily solved using a greedy algorithm! First, take as much as you can of the most valuable item. When that runs out, take as much as you can of the next most valuable item, and so on.

For example, suppose you have these items to choose from.

Image summary: A simple line drawing of a bowl filled with grains, with the text "QUINOA" and "$6/lb" written below it. This is a basic illustration of a product and its price.

Image summary: A simple line drawing of a bowl filled with food, labeled DAL with a price of $3/lb. It is a basic illustrative image depicting a food item and its cost.

Image summary: A simple line drawing of a bowl of rice with the text "RICE" and "$2/lb" written below it. It is an illustrative image depicting the price of rice per pound.

Quinoa is more expensive per pound than anything else. So, take all the quinoa you can carry! If that fills your knapsack, that's the best you can do.

If the quinoa runs out and you still have space in your knapsack, take the next most valuable item, and so on.

Optimizing your travel itinerary

Suppose you're going to London for a nice vacation. You have two days there and a lot of things you want to do. You can't do everything, so you make a list.

Table summary: The National Gallery and British Museum are the highest rated attractions, both receiving a rating of 9, though the British Museum requires 2 days to visit compared to 1 day for the National Gallery. St. Paul's Cathedral follows with a rating of 8, while Westminster Abbey and Globe Theater are rated 7 and 6 respectively, both taking half a day.

For each thing you want to see, you write down how long it will take and rate how much you want to see it. Can you figure out what you should see, based on this list?

It's the knapsack problem again! Instead of a knapsack, you have a limited amount of time. And instead of stereos and laptops, you have a list of places you want to go. Draw the dynamic-programming grid for this list before moving on.

Here's what the grid looks like.

Image summary: A hand-drawn grid with five rows labeled as London landmarks—Westminster, Globe Theatre, National Gallery, British Museum, and St. Paul's—and four columns labeled with the numbers 1/2, 1, 1 1/2, and 2. The grid is currently empty, serving as a blank table for data collection or scoring.

Did you get it right? Fill in the grid. What places should you end up seeing? Here's the answer.

Globe Theater

National Gallery

British Museum

Saint Paul's

Table summary: A sequence of values across four columns that transition from simple numerical fractions and integers to complex symbolic notations involving omega and prime markers. The first row contains the values 1/2, 1, 1 1/2, and 2. The second row is constant across all columns with 7 omega. Subsequent rows introduce downward arrows and varying subscripts and prime markers, such as 13 prime omega G, 16 prime omega N, and 22 prime omega G N. The final row concludes with values including 8 1/5, 15 prime omega S, 21 prime omega S, and 24 prime omega N S.

Final Answer: Westminster Aboy, National Gallery, Saint. Paul's Cathedral

Handling items that depend on each other

Suppose you want to go to Paris, so you add a couple of items on the list.

Table summary: Recommended visit durations and ratings for three Paris landmarks. The Louvre has the highest rating at 9, followed by the Eiffel Tower at 8 and Notre Dame at 7. Each of these locations is allocated a visit time of one half day.

These places take a lot of time, because first you have to travel from London to Paris. That takes half a day. If you want to do all three items, it will take four and a half days.

Wait, that's not right. You don't have to travel to Paris for each item. Once you're in Paris, each item should only take a day. So it should be one day per item + half a day of travel = 3.5 days, not 4.5 days.

If you put the Eiffel Tower in your knapsack, then the Louvre becomes “cheaper”—it will only cost you a day instead of 1.5 days. How do you model this in dynamic programming?

You can't. Dynamic programming is powerful because it can solve subproblems and use those answers to solve the big problem. Dynamic programming only works when each subproblem is discrete—when it doesn't depend on other subproblems. That means there's no way to account for Paris using the dynamic-programming algorithm.

Is it possible that the solution will require more than two sub-knapsacks?

It's possible that the best solution involves stealing more than two items. The way the algorithm is set up, you're combining two knapsacks at most—you'll never have more than two sub-knapsacks. But it's possible for those sub-knapsacks to have their own sub-knapsacks.

Is it possible that the best solution doesn't fill the knapsack completely?

Yes. Suppose you could also steal a diamond.

This is a big diamond: it weighs 3.5 pounds. It's worth a million dollars, way more than anything else. You should definitely steal it! But there's half a pound of space left, and nothing will fit in that space.

Exercise

Diamond

1 million dollars Dollars

3.51bs

9.2 Suppose you're going camping. You have a knapsack that will hold 6 pounds, and you can take the following items. Each has a value, and the higher the value, the more important the item is:

• Water, 3 pounds, 10

• Book, 1 pounds, 3

• Food, 2 pounds, 9

• Jacket, 2 pounds, 5

• Camera, 1 pounds, 6

What's the optimal set of items to take on your camping trip?

Longest common substring

You've seen one dynamic programming problem so far. What are the takeaways?

- Dynamic programming is useful when you're trying to optimize something given a constraint. In the knapsack problem, you had to maximize the value of the goods you stole, constrained by the size of the knapsack.

• You can use dynamic programming when the problem can be broken into discrete subproblems, and they don't depend on each other.

It can be hard to come up with a dynamic-programming solution. That's what we'll focus on in this section. Some general tips follow:

• Every dynamic-programming solution involves a grid.

- The values in the cells are usually what you're trying to optimize. For the knapsack problem, the values were the value of the goods.

- Each cell is a subproblem, so think about how you can divide your problem into subproblems. That will help you figure out what the axes are.

Let's look at another example. Suppose you run dictionary dot com. Someone types in a word, and you give them the definition.

But if someone misspells a word, you want to be able to guess what word they meant. Alex is searching for fish, but he accidentally put in hish. That's not a word in your dictionary, but you have a list of words that are similar.

Similar to Hish:

Fish

- · Vista

Image summary: A line drawing showing a person from behind looking at a computer monitor, which displays a search bar containing the word FISH. It is a simple illustration depicting a user performing a web search.

(This is a toy example, so you'll limit your list to two words. In reality, this list would probably be thousands of words.)

Alex typed hish. Which word did Alex mean to type: fish or vista?

Making the grid

What does the grid for this problem look like? You need to answer these questions:

• What are the values of the cells?

• How do you divide this problem into subproblems?

- What are the axes of the grid?

In dynamic programming, you're trying to maximize something. In this case, you're trying to find the longest substring that two words have in common. What substring do hish and fish have in common? How about hish and vista? That's what you want to calculate.

Remember, the values for the cells are usually what you're trying to optimize. In this case, the values will probably be a number: the length of the longest substring that the two strings have in common.

How do you divide this problem into subproblems? You could compare substrings. Instead of comparing his and fish, you could compare his and his first.

Each cell will contain the length of the longest substring that two substrings have in common. This also gives you a clue that the axes will probably be the two words. So the grid probably looks like this.

Table summary: The table consists of a single row containing the letters H, I, S, and H, followed by five empty rows.

If this seems like black magic to you, don't worry. This is hard stuff—that's why I'm teaching it so late in the book! Later, I'll give you an exercise so you can practice dynamic programming yourself.

Filling in the grid

Now you have a good idea of what the grid should look like. What's the formula for filling in each cell of the grid? You can cheat a little, because you already know what the solution should be—hish and fish have a substring of length 3 in common: ish.

But that still doesn't tell you the formula to use. Computer scientists sometimes joke about using the Feynman algorithm. The Feynman algorithm is named after the famous physicist Richard Feynman, and it works like this:

1. Write down the problem.

2. Think real hard.

3. Write down the solution.

Computer scientists are a fun bunch!

The truth is, there's no easy way to calculate the formula here. You have to experiment and try to find something that works. Sometimes algorithms aren't an exact recipe. They're a framework that you build your idea on top of.

Try to come up with a solution to this problem yourself. I'll give you a hint—part of the grid looks like this.

Table summary: A grid containing letters and numbers organized across five rows and four columns. The first row contains H, I, S, H. The second row contains O, O in the first two columns. The fourth row contains the number 2 in the third column and O in the fourth. The fifth row contains the number 3 in the fourth column.

What are the other values? Remember that each cell is the value of a subproblem. Why does cell (3, 3) have a value of 2? Why does cell (3, 4) have a value of 0?

Read on after you've tried to come up with a formula yourself. Even if you don't get it right, my explanation will make a lot more sense.

The solution

Here's the final grid.

Table summary: A grid of single-letter characters arranged in five rows and four columns. The letters consist primarily of H, I, S, F, O, and Z, with O being the most frequent character, appearing in every row and column.

Here's my formula for filling in each cell.

Image summary: A hand-drawn diagram of a 4x4 grid with the letters F, I, S, H listed along both the top and left axes. The grid contains numerical values, where cells with matching row and column letters contain non-zero numbers, while cells with non-matching letters contain zeros. This illustrates the rule that the value is zero if the letters do not match.

Here's how the formula looks in pseudocode:

if word a i equals word b j: less than The letters match.

cell [i][j] = cell [i-1][j-1] + 1 else: less than The letters don't match.

cell[i][j] = 0 Here's the grid for hish versus vista.

Image summary: A hand-drawn grid with the word VISTA across the top and HISH down the side. The grid contains circles and numbers, with an arrow pointing to the number 2 in the S column and S row as the final answer, and another arrow pointing to the A column as not the final answer. The image depicts a manual process for identifying a specific character or coordinate in a word grid.

One thing to note: for this problem, the final solution may not be in the last cell! For the knapsack problem, this last cell always had the final solution. But for the longest common substring, the solution is the largest number in the grid—and it may not be the last cell.

Let's go back to the original question: which string has more in common with his? his and fish have a substring of three letters in common. his and vista have a substring of two letters in common.

Alex probably meant to type fish.

Longest common subsequence

Suppose Alex accidentally searched for fosh. Which word did he mean: fish or fort?

Let's compare them using the longest-common-substring formula.

Table summary: A grid of characters where the first column spells FORT vertically and the first row spells FOSH horizontally. The remaining cells contain the character O, except for the second row first column which is 1 and the third row second column which is 2.

Table summary: A matrix of interactions between F, O, S, and H. The primary activity is concentrated on the diagonal, with F having a value of 1 at the intersection of F, S having a value of 1 at the intersection of S, and H having a value of 2 at the intersection of H. All other intersections, including those involving O, are 0.

They're both the same: two letters! But fosh is closer to fish.

Math summary: This process calculates the longest common subsequence between two words. It identifies that fosh and fish share three letters in common, while fosh and fort share two letters.

You're comparing the longest common substring, but you really need to compare the longest common subsequence: the number of letters in a sequence that the two words have in common. How do you calculate the longest common subsequence?

Here's the partial grid for fish and fosh.

: Table summary: A distribution of values across four categories labeled F, O, S, and H. The category F has the most entries with two instances of 1, while category O has two instances of 1. Categories S and H each contain a single entry of 2.

Can you figure out the formula for this grid? The longest common subsequence is very similar to the longest common substring, and the formulas are pretty similar, too. Try to solve it yourself—I give the answer next.

Longest common subsequence—solution

Here's the final grid.

Image summary: A hand-drawn grid with rows labeled F, O, R, T and columns labeled F, O, S, H. Numbers and arrows fill the cells, with 1s in the first column and first row, and 2s filling the remaining cells. Arrows indicate a flow from top-to-bottom and left-to-right, culminating in a bolded box containing the number 2 at the bottom right. The diagram illustrates a step-by-step progression or calculation across the grid.

: Table summary: A transition matrix for the characters F, O, S, and H. The row for F shows a sequence of 1 to 1 to 1 to 1. The row for I shows a sequence of 1 to 1 to 1 to 1. The row for S shows a sequence of 1 to 1 to 2 to 2. The row for H shows a sequence of 1 to 1 to 2 to 3.

Here's my formula for filling in each cell.

Image summary: A handwritten diagram illustrating a dynamic programming algorithm for string matching. The process uses a grid where values are determined by comparing characters from two strings: if characters don't match, the cell takes the larger value of its top or left neighbor; if they do match, the cell value is the top-left neighbor's value plus one. The diagram explains how to populate the grid to find a common sequence, noting that the mismatch rule differs from the standard longest common substring algorithm.

And here it is in pseudocode:

Code summary: This algorithm computes the Longest Common Subsequence between two words using dynamic programming. It populates a grid where each cell represents the length of the longest shared sequence of characters up to those positions. If characters match, the sequence length increases based on the previous diagonal cell; otherwise, it inherits the maximum value from the adjacent top or left cells to maintain the best sequence found so far.

Whew—you did it! This is definitely one of the toughest chapters in the book. So is dynamic programming ever really used? Yes:

- Biologists use the longest common subsequence to find similarities in D.N.A strands. They can use this to tell how similar two animals or two diseases are. The longest common subsequence is being used to find a cure for multiple sclerosis.

• Have you ever used diff (like git diff)? Diff tells you the differences between two files, and it uses dynamic programming to do so.

- We talked about string similarity. Levenshtein distance measures how similar two strings are, and it uses dynamic programming. Levenshtein distance is used for everything from spell-check to figuring out whether a user is uploading copyrighted data.

- Have you ever used an app that does word wrap, like Microsoft Word? How does it figure out where to wrap so that the line length stays consistent? Dynamic programming!

Exercise

9.3 Draw and fill in the grid to calculate the longest common substring between blue and clues.

Recap

- Dynamic programming is useful when you're trying to optimize something given a constraint.

- You can use dynamic programming when the problem can be broken into discrete subproblems.

• Every dynamic-programming solution involves a grid.

• The values in the cells are usually what you're trying to optimize.

- Each cell is a subproblem, so think about how you can divide your problem into subproblems.

- There's no single formula for calculating a dynamic-programming solution.

In this chapter

- You learn to build a classification system using the k-nearest neighbors algorithm.

- You learn about feature extraction.

- You learn about regression: predicting a number, like the value of a stock tomorrow, or how much a user will enjoy a movie.

- You learn about the use cases and limitations of k-nearest neighbors.

Classifying oranges versus grapefruit

Look at this fruit. Is it an orange or a grapefruit? Well, I know that grapefruits are generally bigger and redder.

Image summary: A simple line drawing of a round fruit or vegetable resting on a flat surface. It is a basic illustration with no data or analytical result to report.

My thought process is something like this: I have a graph in my mind.

Image summary: A scatter plot with size on the x-axis and color on the y-axis. Small items are represented by open circles and are categorized as orange, while big items are represented by the letter G and are categorized as red. The figure illustrates a correlation where larger size is associated with the color red and smaller size with orange.

O = Orange

G = Grapefruit

Generally speaking, the bigger, redder fruit are grapefruits. This fruit is big and red, so it's probably a grapefruit. But what if you get a fruit like this?

Image summary: A hand-drawn scatter plot with size on the x-axis and color on the y-axis, ranging from orange to red. Small, orange fruits are represented by circles, while big, red fruits are represented by the letter G. An arrow labeled "MYSTERIOUS FRUIT" points to a single dot located between these two clusters. The figure illustrates the process of classifying an unknown object based on its size and color relative to known groups.

How would you classify this fruit? One way is to look at the neighbors of this spot. Take a look at the three closest neighbors of this spot.

Image summary: A scatter plot with size on the x-axis and color on the y-axis. Small circles of an orange-like color are clustered at the bottom left, while larger circles of a red-like color are clustered at the top right. A central point with arrows pointing toward different clusters suggests a classification or grouping process. The point is that the data points are clustered by both size and color.

More neighbors are oranges than grapefruit. So this fruit is probably an orange. Congratulations: You just used the k-nearest neighbors (K.N.N) algorithm for classification! The whole algorithm is pretty simple.

: Image summary: A three-panel diagram illustrating the k-nearest neighbors classification process. In the first panel, a new data point is introduced among existing clusters of circles and letters. In the second panel, the three closest neighbors to the new point are identified. In the third panel, because the majority of those neighbors are circles (labeled as oranges), the new point is classified as an orange. The diagram demonstrates how a local majority vote determines the class of a new data point.

The K.N.N algorithm is simple but useful! If you're trying to classify something, you might want to try K.N.N first. Let's look at a more real-world example.

Building a recommendations system

Suppose you're Netflix, and you want to build a movie recommendations system for your users. On a high level, this is similar to the grapefruit problem!

You can plot every user on a graph.

Image summary: A hand-drawn sketch featuring various animal faces, including dogs, pigs, and rabbits, scattered within a coordinate system defined by x and y axes. The image is an illustration with no data or analytical result to report.

These users are plotted by similarity, so users with similar taste are plotted closer together. Suppose you want to recommend movies for Priyanka. Find the five users closest to her.

Image summary: A diagram showing several hand-drawn animal faces arranged in a coordinate system with x and y axes. Arrows point from a central rabbit face toward a pig, another rabbit, and a cat face, while an arrow points from a bear face toward the central rabbit. This layout depicts a network of relationships or transitions between different animal categories.

Justin, J.C, Joey, Lance, and Chris all have similar taste in movies. So whatever movies they like, Priyanka will probably like too!

Once you have this graph, building a recommendations system is easy. If Justin likes a movie, recommend it to Priyanka.

Image summary: A three-panel diagram illustrating a recommendation process. First, Justin watches a movie; second, he gives the movie a five-star rating and labels it "PITCH PERFECT"; third, the movie is recommended to Priyanka under the heading "YOU MIGHT LIKE". The diagram depicts a basic user-based recommendation mechanism where one person's positive rating triggers a suggestion for another person.

But there's still a big piece missing. You graphed the users by similarity. How do you figure out how similar two users are?

Feature extraction

In the grapefruit example, you compared fruit based on how big they are and how red they are. Size and color are the features you're comparing. Now suppose you have three fruit. You can extract the features.

Image summary: A diagram showing three fruits labeled A, B, and C with corresponding values for size and redness. Fruit A has size 2 and redness 2, fruit B has size 2 and redness 1, and fruit C has the highest values with size 4 and redness 5. The figure illustrates that fruit C is both larger and redder than fruits A and B.

Then you can graph the three fruit.

Image summary: A scatter plot with 'SIZE' on the x-axis and 'REDNESS' on the y-axis, showing three points labeled A, B, and C. Point C has the highest size and redness, while A and B have similar size, with A being redder than B. The plot illustrates the relative differences in size and redness among the three points.

From the graph, you can tell visually that fruits A and B are similar. Let's measure how close they are. To find the distance between two points, you use the Pythagorean formula.

Math summary: This expression calculates the distance between two points using the Pythagorean formula. It computes the square root of the sum of the squared differences between the first and second horizontal coordinates and the first and second vertical coordinates.

Here's the distance between A and B, for example.

Math summary: This computation calculates the distance between point A and point B. It finds the square root of the sum of the squared differences between the input coordinates, resulting in a final value of one.

The distance between A and B is 1. You can find the rest of the distances, too.

Image summary: A geometric diagram on a coordinate plane showing three points, A, B, and C. Point A is located above point B at a distance of 1, while a line segment connects B to C with a length of 25 and a line segment connects A to C with a length of 13. The diagram illustrates the relationship between the distances of these three points.

The distance formula confirms what you saw visually: fruits A and B are similar.

Suppose you're comparing Netflix users, instead. You need some way to graph the users. So, you need to convert each user to a set of coordinates, just as you did for fruit.

Image summary: A simple diagram showing a hand-drawn circle containing several dots, with an arrow pointing to the coordinates (2,2). The image depicts a mapping or transformation from a visual object to a specific numerical coordinate.

Image summary: A simple line drawing of a rabbit's head wearing glasses, with an arrow pointing to a pair of coordinates represented by question marks in parentheses. This is a conceptual illustration depicting the process of mapping a visual image to a set of numerical coordinates.

Once you can graph users, you can measure the distance between them.

Here's how you can convert users into a set of numbers. When users sign up for Netflix, have them rate some categories of movies based on how much they like those categories. For each user, you now have a set of ratings!

Table summary: Movie genre ratings for PRIYANKA, JUSTIN, and MORPHEUS. JUSTIN gave the highest ratings for DRAMA and ROMANCE, both scoring 5, while MORPHEUS gave the highest rating to ACTION with a 5. PRIYANKA provided consistent ratings of 4 for ACTION, DRAMA, and ROMANCE, and a 3 for COMEDY. The lowest ratings across the group were 1, given by PRIYANKA and JUSTIN for HORROR, and by MORPHEUS for DRAMA and ROMANCE.

Priyanka and Justin like Romance and hate Horror. Morpheus likes Action but hates Romance (he hates when a good action movie gets ruined by a cheesy romantic scene). Remember how in oranges versus grapefruit, each fruit was represented by a set of two numbers? Here, each user is represented by a set of five numbers.

Math summary: This expression maps a circle symbol to the coordinates two, two. This result implies that the variable x dot transforms into the five dimensional sequence three, four, four, one, four.

A mathematician would say, instead of calculating the distance in two dimensions, you're now calculating the distance in five dimensions. But the distance formula remains the same.

: Math summary: This expression calculates the distance between two sets of five numbers. It computes the square root of the sum of the squared differences between each corresponding pair of input values.

It just involves a set of five numbers instead of a set of two numbers.

The distance formula is flexible: you could have a set of a million numbers and still use the same old distance formula to find the distance. Maybe you're wondering, “What does distance mean when you have five numbers?” The distance tells you how similar those sets of numbers are.

Math summary: This expression calculates the distance between Priyanka and Justin. It computes the square root of the sum of the squared differences between five pairs of input values, resulting in a final value of two.

Here's the distance between Priyanka and Justin.

Priyanka and Justin are pretty similar. What's the difference between Priyanka and Morpheus? Calculate the distance before moving on.

Did you get it right? Priyanka and Morpheus are 24 apart. The distance tells you that Priyanka's tastes are more like Justin's than Morpheus's.

Great! Now recommending movies to Priyanka is easy: if Justin likes a movie, recommend it to Priyanka, and vice versa. You just built a movie recommendations system!

If you're a Netflix user, Netflix will keep telling you, "Please rate more movies. The more movies you rate, the better your recommendations will be." Now you know why. The more movies you rate, the more accurately Netflix can see what other users you're similar to.

10.1 In the Netflix example, you calculated the distance between two different users using the distance formula. But not all users rate movies the same way. Suppose you have two users, Yogi and Pinky, who have the same taste in movies. But Yogi rates any movie he likes as a 5, whereas Pinky is choosier and reserves the 5s for only the best.

10.2 Suppose Netflix nominates a group of “influencers.” For example, Quentin Tarantino and Wess Anderson are influencers on Netflix, so their ratings count for more than a normal user's. How would you change the recommendations system so it's biased toward the ratings of influencers?

Regression

Suppose you want to do more than just recommend a movie: you want to guess how Priyanka will rate this movie. Take the five people closest to her.

By the way, I keep talking about the closest five people. There's nothing special about the number 5: you could do the closest 2, or 10, or 10,000. That's why the algorithm is called k-nearest neighbors and not five-nearest neighbors!

Image summary: A hand-drawn diagram showing a central rabbit head surrounded by other animal heads, with arrows pointing from the rabbit to a pig, a dog, and another rabbit. The image is a conceptual illustration with no data or analytical result to report.

Suppose you're trying to guess a rating for Pitch Perfect. Well, how did Justin, J.C, Joey, Lance, and Chris rate it?

Code summary: This data block records a set of scores or counts associated with five individuals: Justin, JC, Joey, Lance, and Chris.

You could take the average of their ratings and get 4.2 stars. That's called regression. These are the two basic things you'll do with K.N.N—classification and regression:

• Classification = categorization into a group

• Regression = predicting a response (like a number)

Regression is very useful. Suppose you run a small bakery in Berkeley, and you make fresh bread every day. You're trying to predict how many loaves to make for today. You have a set of features:

• Weather on a scale of 1 to 5 (1 = bad, 5 = great).

• Weekend or holiday? (1 if it's a weekend or a holiday, 0 otherwise.)

• Is there a game on? (1 if yes, 0 if no.)

And you know how many loaves of bread you've sold in the past for different sets of features.

Math summary: This expression maps sets of input features to the quantity of loaves or lones sold. It defines specific outputs such as seventy five loaves for the first set of features and fifteen lones for the fourth set of features.

Today is a weekend day with good weather. Based on the data you just saw, how many loaves will you sell? Let's use K.N.N, where K = 4. First, figure out the four nearest neighbors for this point.

: Math summary: This expression identifies the target point for a K nearest neighbors search. It uses the input values four, one, and phi to determine the four nearest neighbors for predicting loaf sales.

Here are the distances. A, B, D, and E are the closest.

A. 1 left arrow B. 2 left arrow C. 9 D. 2 left arrow E. 1 left arrow F. 5

Take an average of the loaves sold on those days, and you get 218.75. That's how many loaves you should make for today!

Cosine similarity

So far, you've been using the distance formula to compare the distance between two users. Is this the best formula to use? A common one used in practice is cosine similarity. Suppose two users are similar, but one of them is more conservative in their ratings. They both loved Manmohan Desai's Amar Akbar Anthony. Paul rated it 5 stars, but Rowan rated it 4 stars. If you keep using the distance formula, these two users might not be each other's neighbors, even though they have similar taste.

Cosine similarity doesn't measure the distance between two vectors. Instead, it compares the angles of the two vectors. It's better at dealing with cases like this. Cosine similarity is out of the scope of this book, but look it up if you use K.N.N!

Picking good features

To figure out recommendations, you had users rate categories of movies. What if you had them rate pictures of cats instead? Then you'd find users who rated those pictures similarly. This would probably be a worse recommendations engine, because the “features” don't have a lot to do with taste in movies!

Or suppose you ask users to rate movies so you can give them recommendations—but you only ask them to rate Toy Story, Toy Story 2, and Toy Story 3. This won't tell you a lot about the users' movie tastes!

When you're working with K.N.N, it's really important to pick the right features to compare against. Picking the right features means

- Features that directly correlate to the movies you're trying to recommend

- Features that don't have a bias (for example, if you ask the users to only rate comedy movies, that doesn't tell you whether they like action movies)

Do you think ratings are a good way to recommend movies? Maybe I rated The Wire more highly than House Hunters, but I actually spend more time watching House Hunters. How would you improve this Netflix recommendations system?

Going back to the bakery: can you think of two good and two bad features you could have picked for the bakery? Maybe you need to make more loaves after you advertise in the paper. Or maybe you need to make more loaves on Mondays.

There's no one right answer when it comes to picking good features. You have to think about all the different things you need to consider.

Introduction to machine learning

K.N.N is a really useful algorithm, and it's your introduction to the magical world of machine learning! Machine learning is all about making your computer more intelligent. You already saw one example of machine learning: building a recommendations system. Let's look at some other examples.

O.C.R

O.C.R stands for optical character recognition. It means you can take a photo of a page of text, and your computer will automatically read the text for you. Google uses O.C.R to digitize books. How does O.C.R work? For example, consider this number.

Image summary: A black ink drawing of a single character or symbol on a white background, consisting of a horizontal top stroke, a vertical descending stroke, and a short horizontal cross-stroke. It is a character image with no data or analytical result to report.

How would you automatically figure out what number this is? You can use K.N.N for this:

1. Go through a lot of images of numbers, and extract features of those numbers.

2. When you get a new image, extract the features of that image, and see what its nearest neighbors are!

It's the same problem as oranges versus grapefruit. Generally speaking, O.C.R algorithms measure lines, points, and curves.

Image summary: Two hand-drawn figures illustrating the components of digits. The digit 3 is decomposed into a top curve, a middle point, and a bottom curve, while the digit 7 is decomposed into a top line, a corner point, a descending line, and a point on that line. The point is to demonstrate how digits can be represented as a sequence of basic geometric primitives.

Then, when you get a new character, you can extract the same features from it.

Feature extraction is a lot more complicated in O.C.R than the fruit example. But it's important to understand that even complex technologies build on simple ideas, like K.N.N. You could use the same ideas for speech recognition or face recognition. When you upload a photo to Facebook, sometimes it's smart enough to tag people in the photo automatically. That's machine learning in action!

The first step of O.C.R, where you go through images of numbers and extract features, is called training. Most machine-learning algorithms have a training step: before your computer can do the task, it must be trained. The next example involves spam filters, and it has a training step.

Building a spam filter

Spam filters use another simple algorithm called the Naive Bayes classifier. First, you train your Naive Bayes classifier on some data.

Table summary: A classification of email subjects as either spam or not spam. Most of the examples are labeled as SPAM, including messages about winning 1 million dollars, requests for passwords, and a Nigerian prince sending 10 million dollars. Messages such as "RESET YOUR PASSWORD" and "HAPPY BIRTHDAY" are labeled as NOT SPAM.

Suppose you get an email with the subject “collect your million dollars now!” Is it spam? You can break this sentence into words. Then, for each word, see what the probability is for that word to show up in a spam email. For example, in this very simple model, the word million only appears in spam emails. Naive Bayes figures out the probability that something is likely to be spam. It has applications similar to K.N.N.

For example, you could use Naive Bayes to categorize fruit: you have a fruit that's big and red. What's the probability that it's a grapefruit? It's another simple algorithm that's fairly effective. We love those algorithms!

Predicting the stock market

Here's something that's hard to do with machine learning: really predicting whether the stock market will go up or down. How do you pick good features in a stock market? Suppose you say that if the stock went up yesterday, it will go up today. Is that a good feature? Or suppose you say that the stock will always go down in May. Will that work?

There's no guaranteed way to use past numbers to predict future performance. Predicting the future is hard, and it's almost impossible when there are so many variables involved.

Recap

I hope this gives you an idea of all the different things you can do with K.N.N and with machine learning! Machine learning is an interesting field that you can go pretty deep into if you decide to:

- K.N.N is used for classification and regression and involves looking at the k-nearest neighbors.

• Classification = categorization into a group.

• Regression = predicting a response (like a number).

- Feature extraction means converting an item (like a fruit or a user) into a list of numbers that can be compared.

• Picking good features is an important part of a successful K.N.N algorithm.

In this chapter

- You get a brief overview of 10 algorithms that weren't covered in this book, and why they're useful.

- You get pointers on what to read next, depending on what your interests are.

Trees

Let's go back to the binary search example. When a user logs in to Facebook, Facebook has to look through a big array to see if the username exists. We said the fastest way to search through this array is to run binary search.

But there's a problem: every time a new user signs up, you insert their username into the array. Then you have to re-sort the array, because binary search only works with sorted arrays. Wouldn't it be nice if you could insert the username into the right slot in the array right away, so you don't have to sort the array afterward? That's the idea behind the binary search tree data structure.

Image summary: A diagram of a family tree showing three generations of people. A single individual at the top branches down to two children, who in turn each have two children of their own. The structure illustrates a lineage of descent across three levels.

A binary search tree looks like this.

Image summary: A hand-drawn diagram showing a hierarchical structure of names in circles connected by arrows. David is at the top, with arrows pointing to Adit and Manning; Manning then has arrows pointing to Maggie and Mike. The diagram depicts a tree-like relationship or flow starting from David.

For every node, the nodes to its left are smaller in value, and the nodes to the right are larger in value.

Image summary: A diagram of a binary search tree containing names. The root node is David, with Adit as the left child because it comes before David alphabetically, and Manning as the right child because it comes after. Manning further branches into Maggie and Mike. An arrow points to Maggie with a note stating she comes after David and before Manning. The diagram illustrates how alphabetical ordering determines the placement of nodes in a binary search tree.

Suppose you're searching for Maggie. You start at the root node.

Image summary: A hand-drawn tree diagram showing a hierarchy of names. David is at the top, branching down to Adit and Manning, with Manning further branching down to Maggie and Mike. The diagram depicts a organizational or familial structure with David as the root node.

Maggie comes after David, so go toward the right.

Image summary: A hand-drawn diagram showing a hierarchical relationship between people. David is at the top, with arrows pointing down to Adit and Manning; Manning further has arrows pointing down to Maggie and Mike. The structure depicts a chain of command or a family tree with David as the primary head.

Maggie comes before Manning, so go to the left.

Image summary: A hand-drawn diagram of a hierarchical tree structure showing David at the top, with arrows pointing down to Adit and Manning. Manning further branches down to Maggie and Mike, with an additional arrow pointing toward Maggie. The diagram depicts a chain of command or organizational relationship where David is the primary head.

You found Maggie! It's almost like running a binary search! Searching for an element in a binary search tree takes O( log n ) time on average and O(n) time in the worst case. Searching a sorted array takes O( log n ) time in the worst case, so you might think a sorted array is better. But a binary search tree is a lot faster for insertions and deletions on average.

Table summary: BINARY search trees outperform ARRAY structures in time complexity for insertion and deletion. While both have a search complexity of O(log n), BINARY structures maintain O(log n) for INSERT and DELETE operations, whereas ARRAY structures require O(n) for both.

Binary search trees have some downsides too: for one thing, you don't get random access. You can't say, "Give me the fifth element of this tree." Those performance times are also on average and rely on the tree being balanced. Suppose you have an imbalanced tree like the one shown next.

Image summary: A diagram of a directed graph where nodes are labeled with numbers and connected by arrows. Node 2 points to nodes 1 and 4; node 4 points to nodes 3 and 7; node 7 points to node 20; and node 20 points to node 50. The structure depicts a hierarchical flow of connections starting from node 2 and branching down to node 50.

See how it's leaning to the right? This tree doesn't have very good performance, because it isn't balanced. There are special binary search trees that balance themselves. One example is the red-black tree.

So when are binary search trees used? B-trees, a special type of binary tree, are commonly used to store data in databases.

If you're interested in databases or more-advanced data structures, check these out:

• B-trees

• Red-black trees

• Heaps

• Splay trees

Inverted indexes

Here's a very simplified version of how a search engine works. Suppose you have three web pages with this simple content.

Image summary: A simple line drawing of a scroll with the words "HI ADIT" written on it. It is an illustration with no data or analytical result to report.

Let's build a hash table from this content.

The keys of the hash table are the words, and the values tell you what pages each word appears on. Now suppose a user searches for hi. Let's see what pages hi shows up on.

Image summary: A simple hand-drawn sketch of a rectangular object with a curved top and a small handle-like shape on top. The object is divided into sections containing the handwritten labels "S", "H1", and "A, B". It is a conceptual diagram, with no data or analytical result to report.

Image summary: A hand-drawn sketch of a clipboard containing a table with two columns. The left column lists words "HI", "THERE", "ADIT", "WE", and "GO", while the right column lists corresponding letters "A, B", "A, C", "B", "C", and "C". It is a simple illustration of a data table.

Aha: It appears on pages A and B. Let's show the user those pages as the result. Or suppose the user searches for there. Well, you know that it shows up on pages A and C. Pretty easy, huh?

This is a useful data structure: a hash that maps words to places where they appear. This data structure is called an inverted index, and it's commonly used to build search engines. If you're interested in search, this is a good place to start.

The Fourier transform

The Fourier transform is one of those rare algorithms: brilliant, elegant, and with a million use cases. The best analogy for the Fourier transform comes from Better Explained (a great website that explains math simply): given a smoothie, the Fourier transform will tell you the ingredients in the smoothie. Or, to put it another way, given a song, the transform can separate it into individual frequencies.

It turns out that this simple idea has a lot of use cases. For example, if you can separate a song into frequencies, you can boost the ones you care about. You could boost the bass and hide the treble.

The Fourier transform is great for processing signals. You can also use it to compress music. First you break an audio file down into its ingredient notes.

The Fourier transform tells you exactly how much each note contributes to the overall song. So you can just get rid of the notes that aren't important. That's how the M.P.3 format works!

Music isn't the only type of digital signal. The J.P.G format is another compressed format, and it works the same way. People use the Fourier transform to try to predict upcoming earthquakes and analyze D.N.A.

You can use it to build an app like Shazam, which guesses what song is playing. The Fourier transform has a lot of uses. Chances are high that you'll run into it!

Parallel algorithms

The next three topics are about scalability and working with a lot of data. Back in the day, computers kept getting faster and faster. If you wanted to make your algorithm faster, you could wait a few months, and the computers themselves would become faster. But we're near the end of that period.

Instead, laptops and computers ship with multiple cores. To make your algorithms faster, you need to change them to run in parallel across all the cores at once!

Here's a simple example. The best you can do with a sorting algorithm is roughly O(n log n) . It's well known that you can't sort an array in O(n) time—unless you use a parallel algorithm! There's a parallel version of quicksort that will sort an array in O(n) time.

Parallel algorithms are hard to design. And it's also hard to make sure they work correctly and to figure out what type of speed boost you'll see. One thing is for sure—the time gains aren't linear. So if you have two cores in your laptop instead of one, that almost never means your algorithm will magically run twice as fast. There are a couple of reasons for this:

- Overhead of managing the parallelism—Suppose you have to sort an array of 1,000 items. How do you divide this task among the two cores? Do you give each core 500 items to sort and then merge the two sorted arrays into one big sorted array? Merging the two arrays takes time.

• Load balancing—Suppose you have 10 tasks to do, so you give each core 5 tasks. But core A gets all the easy tasks, so it's done in 10 seconds, whereas core B gets all the hard tasks, so it takes a minute. That means core A was sitting idle for 50 seconds while core B was doing all the work! How do you distribute the work evenly so both cores are working equally hard?

If you're interested in the theoretical side of performance and scalability, parallel algorithms might be for you!

MapReduce

There's a special type of parallel algorithm that is becoming increasingly popular: the distributed algorithm. It's fine to run a parallel algorithm on your laptop if you need two to four cores, but what if you need hundreds of cores? Then you can write your algorithm to run across multiple machines. The MapReduce algorithm is a popular distributed algorithm. You can use it through the popular open source tool Apache Hadoop.

Why are distributed algorithms useful?

Suppose you have a table with billions or trillions of rows, and you want to run a complicated S.Q.L query on it. You can't run it on my sql, because it struggles after a few billion rows. Use MapReduce through Hadoop!

Or suppose you have to process a long list of jobs. Each job takes 10 seconds to process, and you need to process 1 million jobs like this. If you do this on one machine, it will take you months! If you could run it across 100 machines, you might be done in a few days.

Distributed algorithms are great when you have a lot of work to do and want to speed up the time required to do it. MapReduce in particular is built up from two simple ideas: the map function and the reduce function.

The map function

The map function is simple: it takes an array and applies the same function to each item in the array. For example, here we're doubling every item in the array: arr 2 now contains [2, 4, 6, 8, 10] —every element in arr 1 was doubled! Doubling an element is pretty fast. But suppose you apply a function that takes more time to process. Look at this pseudocode:

Code summary: This snippet demonstrates how to double every element in a list by applying a lambda function to each item using the map function, resulting in a new sequence of transformed values.

Table summary: A numerical progression where each value in the first row is multiplied by two to produce the corresponding value in the second row. For instance, the sequence 1, 2, 3, 4, 5 maps to 2, 4, 6, 8, 10 respectively.

Code summary: This snippet demonstrates how to apply a download function to a collection of URLs using the map function, which transforms the list of addresses into a series of page download operations.

Here you have a list of U.R.L's, and you want to download each page and store the contents in arr2. This could take a couple of seconds for each U.R.L. If you had 1,000 U.R.L's, this might take a couple of hours!

Wouldn't it be great if you had 100 machines, and map could automatically spread out the work across all of them? Then you would be downloading 100 pages at a time, and the work would go a lot faster! This is the idea behind the “map” in MapReduce.

The reduce function

The reduce function confuses people sometimes. The idea is that you “reduce” a whole list of items down to one item. With map, you go from one array to another.

Table summary: A numerical grid where values increase by two across each row and column. The first row contains 1, 2, 3, 4, and 5. The second row consists of downward arrows, and the third row contains 2, 4, 6, 8, and 10.

With reduce, you transform an array to a single item.

Here's an example:

Table summary: A sequence of numbers from 1 to 5.

Code summary: This snippet demonstrates the use of the reduce function to perform a cumulative operation on a list. It applies a lambda function that adds two elements together repeatedly across the array, effectively condensing the entire sequence into a single sum.

In this case, you sum up all the elements in the array: 1 + 2 + 3 + 4 + 5 = 15 ! I won't explain reduce in more detail here, because there are plenty of tutorials online.

MapReduce uses these two simple concepts to run queries about data across multiple machines. When you have a large dataset (billions of rows), MapReduce can give you an answer in minutes where a traditional database might take hours.

Bloom filters and HyperLogLog

Suppose you're running Reddit. When someone posts a link, you want to see if it's been posted before. Stories that haven't been posted before are considered more valuable. So you need to figure out whether this link has been posted before.

Or suppose you're Google, and you're crawling web pages. You only want to crawl a web page if you haven't crawled it already. So you need to figure out whether this page has been crawled before.

Or suppose you're running bit.ly, which is a U.R.L shortener. You don't want to redirect users to malicious websites. You have a set of U.R.L's that are considered malicious. Now you need to figure out whether you're redirecting the user to a U.R.L in that set.

All of these examples have the same problem. You have a very large set.

Image summary: A hand-drawn illustration of a cloud-like shape containing several website URLs, including scribd.com, adit.io, xkcd.com, facebook.com, itch.io, and instagram.com. It is a simple conceptual drawing with no data or analytical result to report.

Now you have a new item, and you want to see whether it belongs in that set. You could do this quickly with a hash. For example, suppose Google has a big hash in which the keys are all the pages it has crawled.

Image summary: A hand-drawn illustration of a screen or list showing two entries: facebook.com and adit.io, both marked with YES. The image is a simple sketch and does not present a data-driven analytical result.

You want to see whether you've already crawled adit dot io. Look it up in the hash.

Math summary: This expression performs a lookup for the input value adit dot i o. The process returns the result yes to indicate that the value exists within the hash.

adit dot io is a key in the hash, so you've already crawled it. The average lookup time for hash tables is O (1). adit dot io is in the hash, so you've already crawled it. You found that out in constant time. Pretty good!

Except that this hash needs to be huge. Google indexes trillions of web pages. If this hash has all the U.R.L's that Google has indexed, it will take up a lot of space. Reddit and bit.ly have the same space problem. When you have so much data, you need to get creative!

Bloom filters

Bloom filters offer a solution. Bloom filters are probabilistic data structures. They give you an answer that could be wrong but is probably correct. Instead of a hash, you can ask your bloom filter if you've crawled this U.R.L before. A hash table would give you an accurate answer. A bloom filter will give you an answer that's probably correct:

- False positives are possible. Google might say, “You've already crawled this site,” even though you haven't.

- False negatives aren't possible. If the bloom filter says, "You haven't crawled this site," then you definitely haven't crawled this site.

Bloom filters are great because they take up very little space. A hash table would have to store every U.R.L crawled by Google, but a bloom filter doesn't have to do that. They're great when you don't need an exact answer, as in all of these examples. It's okay for bit.ly to say, "We think this site might be malicious, so be extra careful."

HyperLogLog

Along the same lines is another algorithm called HyperLogLog. Suppose Google wants to count the number of unique searches performed by its users. Or suppose Amazon wants to count the number of unique items that users looked at today. Answering these questions takes a lot of space! With Google, you'd have to keep a log of all the unique searches. When a user searches for something, you have to see whether it's already in the log.

If not, you have to add it to the log. Even for a single day, this log would be massive!

HyperLogLog approximates the number of unique elements in a set. Just like bloom filters, it won't give you an exact answer, but it comes very close and uses only a fraction of the memory a task like this would otherwise take.

If you have a lot of data and are satisfied with approximate answers, check out probabilistic algorithms!

The S.H.A algorithms

Do you remember hashing from chapter 5? Just to recap, suppose you have a key, and you want to put the associated value in an array.

Image summary: A hand-drawn number line consisting of a horizontal bar divided into equal segments, labeled with integers from 0 to 25. It is a basic diagram used to represent a linear scale of numbers.

You use a hash function to tell you what slot to put the value in.

Image summary: A hand-drawn diagram of a horizontal array of 26 numbered slots from 0 to 25. Arrows point to the first few slots for As, Bs, and Cs, and to the final slots for Ys and Zs. The diagram illustrates a mapping of the alphabet to a zero-indexed numerical sequence.

And you put the value in that slot.

Image summary: A hand-drawn diagram showing a box containing the number 0.67, with the word APPLES and an upward arrow pointing toward the box. This depicts a value of 0.67 associated with apples.

This allows you to do constant-time lookups. When you want to know the value for a key, you can use the hash function again, and it will tell you in O (1) time what slot to check.

In this case, you want the hash function to give you a good distribution. So a hash function takes a string and gives you back the slot number for that string.

Comparing files

Another hash function is a secure hash algorithm S.H.A function. Given a string, S.H.A gives you a hash for that string.

Math summary: This expression demonstrates a secure hash algorithm function. It transforms the input string hello into the output hash string two c f twenty four d b.

The terminology can be a little confusing here. S.H.A is a hash function. It generates a hash, which is just a short string. The hash function for hash tables went from string to array index, whereas S.H.A goes from string to string.

S.H.A generates a different hash for every string.

Math summary: This expression demonstrates how the SHA algorithm transforms specific input strings into unique hash values. It shows the words hello, algorithm, and password being converted into distinct sequences of hexadecimal characters.

Note

S.H.A hashes are long. They've been truncated here.

You can use S.H.A to tell whether two files are the same. This is useful when you have very large files. Suppose you have a 4 G.B file. You want to check whether your friend has the same large file.

You don't have to try to email them your large file. Instead, you can both calculate the S.H.A hash and compare it.

Image summary: A diagram illustrating the concept of file hashing. Two separate files, labeled "YOUR FILE" and "THEIR FILE," are both processed through a hashing function, "e2pakt...", resulting in "YOUR HASH" and "THEIR HASH." Because both processes yield the same hash, the diagram concludes that it is the same file. The point is that identical files produce identical hashes, allowing for efficient verification of file equality.

Checking passwords

S.H.A is also useful when you want to compare strings without revealing what the original string was. For example, suppose Gmail gets hacked, and the attacker steals all the passwords! Is your password out in the open?

No, it isn't. Google doesn't store the original password, only the S.H.A hash of the password! When you type in your password, Google hashes it and checks it against the hash in its database.

Image summary: A diagram illustrating the password verification process. A user's password is converted into a hash, which is then compared against a stored hash in a database table containing user and password columns. A checkmark indicates that when the hashes match, the password is correct. The purpose is to show how systems verify passwords securely by storing and comparing hashes rather than plain text.

So it's only comparing hashes—it doesn't have to store your password! S.H.A is used very commonly to hash passwords like this. It's a one-way hash. You can get the hash of a string.

abc123 to 6ca13d

But you can't get the original string from the hash.

Math summary: This expression performs an assignment operation. It assigns the hexadecimal hash value six c a one three d to a specific variable.

That means if an attacker gets the S.H.A hashes from Gmail, they can't convert those hashes back to the original passwords! You can convert a password to a hash, but not vice versa.

S.H.A is actually a family of algorithms: S.H.A 0, S.H.A 1, S.H.A 2, and S.H.A 3. As of this writing, S.H.A 0 and S.H.A 1 have some weaknesses. If you're using an S.H.A algorithm for password hashing, use S.H.A 2 or S.H.A 3. The gold standard for password-hashing functions is currently bcrypt (though nothing is foolproof).

Locality-sensitive hashing

S.H.A has another important feature: it's locality insensitive. Suppose you have a string, and you generate a hash for it.

Math summary: This expression shows a transformation of the word dog into a hash value. The process maps the input string to the specific output sequence c d six three five seven.

If you change just one character of the string and regenerate the hash, it's totally different!

Math summary: This expression shows a transformation of a specific input string. The input string dot is converted into the output hash value e three nine two d a.

This is good because an attacker can't compare hashes to see whether they're close to cracking a password.

Sometimes, you want the opposite: you want a locality-sensitive hash function. That's where Simhash comes in. If you make a small change to a string, Simhash generates a hash that's only a little different. This allows you to compare hashes and see how similar two strings are, which is pretty useful!

- Google uses Simhash to detect duplicates while crawling the web.

- A teacher could use Simhash to see whether a student was copying an essay from the web.

- Scribd allows users to upload documents or books to share with others. But Scribd doesn't want users uploading copyrighted content! The site could use Simhash to check whether an upload is similar to a Harry Potter book and, if so, reject it automatically.

Simhash is useful when you want to check for similar items.

Diffie-Hellman key exchange

The Diffie-Hellman algorithm deserves a mention here, because it solves an age-old problem in an elegant way. How do you encrypt a message so it can only be read by the person you sent the message to?

The easiest way is to come up with a cipher, like a = 1, b = 2, and so on. Then if I send you the message “4,15,7”, you can translate it to “d,o,g”. But for this to work, we both have to agree on the cipher. We can't agree over email, because someone might hack into your email, figure out the cipher, and decode our messages. Heck, even if we meet in person, someone might guess the cipher—it's not complicated.

So we should change it every day. But then we have to meet in person to change it every day!

Even if we did manage to change it every day, a simple cipher like this is easy to crack with a brute-force attack. Suppose I see the message “9,6,13,13,16 24,16,19,13,5”. I'll guess that this uses a = 1, b = 2, and so on.

Math summary: This process performs a decryption transformation on a sequence of numbers. It maps the input values nine, six, thirteen, thirteen, sixteen, twenty four, sixteen, nineteen, thirteen, and five to the letters i, f, m, m, p, x, p, s, m, and e.

That's gibberish. Let's try a = 2, b = 3, and so on.

Math summary: This expression performs a mapping of numerical values to specific letters of the alphabet. The numbers nine, six, thirteen, thirteen, sixteen, twenty four, sixteen, nineteen, thirteen, and five are transformed into the words hello world.

That worked! A simple cipher like this is easy to break. The Germans used a much more complicated cipher in W.W.2, but it was still cracked. Diffie-Hellman solves both problems:

- Both parties don't need to know the cipher. So we don't have to meet and agree to what the cipher should be.

- The encrypted messages are extremely hard to decode.

Diffie-Hellman has two keys: a public key and a private key. The public key is exactly that: public. You can post it on your website, email it to friends, or do anything you want with it. You don't have to hide it. When someone wants to send you a message, they encrypt it using the public key.

An encrypted message can only be decrypted using the private key. As long as you're the only person with the private key, only you will be able to decrypt this message!

The Diffie-Hellman algorithm is still used in practice, along with its successor, R.S.A. If you're interested in cryptography, Diffie-Hellman is a good place to start: it's elegant and not too hard to follow.

Linear programming

I saved the best for last. Linear programming is one of the coolest things I know.

Linear programming is used to maximize something given some constraints. For example, suppose your company makes two products, shirts and totes. Shirts need 1 meter of fabric and 5 buttons. Totes need 2 meters of fabric and 2 buttons. You have 11 meters of fabric and 20 buttons. You make $2 per shirt and $3 per tote. How many shirts and totes should you make to maximize your profit?

Here you're trying to maximize profit, and you're constrained by the amount of materials you have.

Another example: you're a politician, and you want to maximize the number of votes you get. Your research has shown that it takes an average of an hour of work (marketing, research, and so on) for each vote from a San Franciscan or 1.5 hours/vote from a Chicagoan. You need at least 500 San Franciscans and at least 300 Chicagoans. You have 50 days. It also costs you 2 dollars per San Franciscan versus 1 dollar per Chicagoan. Your total budget is 1,500 dollars. What's the maximum number of total votes you can get (San Francisco plus Chicago)?

Here you're trying to maximize votes, and you're constrained by time and money.

You might be thinking, “You've talked about a lot of optimization topics in this book. How are they related to linear programming?” All the graph algorithms can be done through linear programming instead. Linear programming is a much more general framework, and graph problems are a subset of that. I hope your mind is blown!

Linear programming uses the Simplex algorithm. It's a complex algorithm, which is why I didn't include it in this book. If you're interested in optimization, look up linear programming!

Epilogue

I hope this quick tour of 10 algorithms showed you how much more is left to discover. I think the best way to learn is to find something you're interested in and dive in. This book gave you a solid foundation to do just that.

Chapter 1

1.1 Suppose you have a sorted list of 128 names, and you're searching through it using binary search. What's the maximum number of steps it would take?

Answer: 7.

1.2 Suppose you double the size of the list. What's the maximum number of steps now?

Answer: 8.

1.3 You have a name, and you want to find the person's phone number in the phone book.

Answer: big O of log n.

1.4 You have a phone number, and you want to find the person's name in the phone book. (Hint: You'll have to search through the whole book!)

Answer: O(n).

1.5 You want to read the numbers of every person in the phone book. Answer: O(n).

1.6 You want to read the numbers of just the As.

Answer: O(n). You may think, “I'm only doing this for 1 out of 26 characters, so the run time should be O n over 26 A simple rule to remember is, ignore numbers that are added, subtracted, multiplied, or divided. None of these are correct Big O run times:

O(n + 26), O(n - 26), O(n ★ 26), O(n / 26). They're all the same as O(n)! Why? If you're curious, flip to "Big O notation revisited," in chapter 4, and read up on constants in Big O notation (a constant is just a number; 26 was the constant in this question).

Chapter 2

2.1 Suppose you're building an app to keep track of your finances.

1. Groceries

2. Movie

3. S.F.B.C Membership

Every day, you write down everything you spent money on. At the end of the month, you review your expenses and sum up how much you spent. So, you have lots of inserts and a few reads. Should you use an array or a list?

Answer: In this case, you're adding expenses to the list every day and reading all the expenses once a month. Arrays have fast reads and slow inserts. Linked lists have slow reads and fast inserts. Because you'll be inserting more often than reading, it makes sense to use a linked list.

Also, linked lists have slow reads only if you're accessing random elements in the list. Because you're reading every element in the list, linked lists will do well on reads too. So a linked list is a good solution to this problem.

2.2 Suppose you're building an app for restaurants to take customer orders. Your app needs to store a list of orders. Servers keep adding orders to this list, and chefs take orders off the list and make them. It's an order queue: servers add orders to the back of the queue, and the chef takes the first order off the queue and cooks it.

Image summary: A diagram illustrating a queue system using a restaurant analogy, where a server adds order slips to the back of an order queue and a chef pulls them off from the front. This depicts a first-in, first-out mechanism for processing tasks.

Would you use an array or a linked list to implement this queue?

(Hint: linked lists are good for inserts/deletes, and arrays are good for random access. Which one are you going to be doing here?)

Answer: A linked list. Lots of inserts are happening (servers adding orders), which linked lists excel at. You don't need search or random access (what arrays excel at), because the chefs always take the first order off the queue.

2.3 Let's run a thought experiment. Suppose Facebook keeps a list of usernames. When someone tries to log in to Facebook, a search is done for their username. If their name is in the list of usernames, they can log in. People log in to Facebook pretty often, so there are a lot of searches through this list of usernames. Suppose Facebook uses binary search to search the list.

Binary search needs random access—you need to be able to get to the middle of the list of usernames instantly. Knowing this, would you implement the list as an array or a linked list?

Answer: A sorted array. Arrays give you random access—you can get an element from the middle of the array instantly. You can't do that with linked lists. To get to the middle element in a linked list, you'd have to start at the first element and follow all the links down to the middle element.

2.4 People sign up for Facebook pretty often, too. Suppose you decided to use an array to store the list of users. What are the downsides of an array for inserts? In particular, suppose you're using binary search to search for logins. What happens when you add new users to an array?

Answer: Inserting into arrays is slow. Also, if you're using binary search to search for usernames, the array needs to be sorted. Suppose someone named Adit B signs up for Facebook. Their name will be inserted at the end of the array. So you need to sort the array every time a name is inserted!

2.5 In reality, Facebook uses neither an array nor a linked list to store user information. Let's consider a hybrid data structure: an array of linked lists. You have an array with 26 slots. Each slot points to a linked list. For example, the first slot in the array points to a linked list containing all the usernames starting with a. The second slot points to a linked list containing all the usernames starting with b, and so on.

Image summary: A diagram of a hash table consisting of an array that points to three separate linked lists. Each list stores usernames starting with a specific letter: the first list contains "A" usernames, the second contains "B" usernames, and the third contains "C" usernames. This structure demonstrates how a hash table uses chaining to handle multiple entries that map to the same array index.

Suppose Adit B signs up for Facebook, and you want to add them to the list. You go to slot 1 in the array, go to the linked list for slot 1, and add Adit B at the end. Now, suppose you want to search for Zakhir H. You go to slot 26, which points to a linked list of all the Z names. Then you search through that list to find Zakhir H.

Compare this hybrid data structure to arrays and linked lists. Is it slower or faster than each for searching and inserting? You don't have to give Big O run times, just whether the new data structure would be faster or slower.

Answer: Searching—slower than arrays, faster than linked lists.

Inserting—faster than arrays, same amount of time as linked lists.

So it's slower for searching than an array, but faster or the same as linked lists for everything. We'll talk about another hybrid data structure called a hash table later in the book. This should give you an idea of how you can build up more complex data structures from simple ones.

So what does Facebook really use? It probably uses a dozen different databases, with different data structures behind them: hash tables, B-trees, and others. Arrays and linked lists are the building blocks for these more complex data structures.

Chapter 3

3.1 Suppose I show you a call stack like this.

Image summary: A hand-drawn diagram of a memory stack containing two frames. The top frame is labeled GREET2 and contains a variable NAME assigned to MAGGIE; the bottom frame is labeled GREET and contains a variable NAME also assigned to MAGGIE. The diagram illustrates how recursive or nested function calls create separate stack frames with their own local variables, even when those variables share the same name and value.

What information can you give me, just based on this call stack?

Answer: Here are some things you could tell me:

• The greet function is called first, with name = maggie.

• Then the greet function calls the greet2 function, with name = maggie.

- At this point, the greet function is in an incomplete, suspended state.

• The current function call is the greet2 function.

• After this function call completes, the greet function will resume.

Answer: The stack grows forever. Each program has a limited amount of space on the call stack. When your program runs out of space (which it eventually will), it will exit with a stack-overflow error.

Chapter 4

Code summary: This block provides two recursive utility functions for list processing. The first, count, determines the total number of items by recursively stripping the first element and adding one until the list is empty. The second, max, identifies the largest value in a list by recursively comparing the first element against the maximum value of the remaining sub-list, using a base case for lists of length 2.

4.4 Remember binary search from chapter 1? It's a divide-and-conquer algorithm, too. Can you come up with the base case and recursive case for binary search?

Answer: The base case for binary search is an array with one item. If the item you're looking for matches the item in the array, you found it! Otherwise, it isn't in the array.

In the recursive case for binary search, you split the array in half, throw away one half, and call binary search on the other half.

How long would each of these operations take in Big O notation?

4.5 Printing the value of each element in an array. Answer: O(n)

4.6 Doubling the value of each element in an array. Answer: O(n)

4.7 Doubling the value of just the first element in an array. Answer: O (1)

4.8 Creating a multiplication table with all the elements in the array. So if your array is [2, 3, 7, 8, 10], you first multiply every element by 2, then multiply every element by 3, then by 7, and so on. Answer: O (n squared)

: Algorithm 4.1 summary: This sum function calculates the total of a list using a recursive approach. It establishes a base case to return zero when the list is empty, and otherwise solves the problem by adding the first element to the result of a recursive call on the remainder of the list.

Chapter 5

Which of these hash functions are consistent?

5.1 f(x) = 1 less than Returns "1" for all input

Answer: Consistent

5.2 f of x equals rand open parenthesis close parenthesis arrow Returns a random number every time Answer: Not consistent

5.3 f of x equals next empty slot open parenthesis close parenthesis Returns the index of the next empty slot in the hash table

Answer: Not consistent

5.4 f(x) = len(x) ☑ Uses the length of the string as the index

Answer: Consistent

Suppose you have these four hash functions that work with strings:

A. Return “1” for all input.

B. Use the length of the string as the index.

C. Use the first character of the string as the index. So, all strings starting with a are hashed together, and so on.

D. Map every letter to a prime number: a = 2, b = 3, c = 5, d = 7, e = 11, and so on. For a string, the hash function is the sum of all the characters modulo the size of the hash. For example, if your hash size is 10, and the string is “bag”, the index is 3 + 2 + 17% 10 = 22% 10 = 2.

For each of the following examples, which hash functions would provide a good distribution? Assume a hash table size of 10 slots.

5.5 A phonebook where the keys are names and values are phone numbers. The names are as follows: Esther, Ben, Bob, and Dan.

Answer: Hash functions C and D would give a good distribution.

5.6 A mapping from battery size to power. The sizes are A, A.A, A.A.A, and A.A.A.A.

Answer: Hash functions B and D would give a good distribution.

5.7 A mapping from book titles to authors. The titles are Maus, Fun Home, and Watchmen.

Answer: Hash functions B, C, and D would give a good distribution.

Chapter 6

Run the breadth-first search algorithm on each of these graphs to find the solution.

6.1 Find the length of the shortest path from start to finish.

Answer: The shortest path has a length of 2.

6.2 Find the length of the shortest path from “cab” to “bat”.

Image summary: A directed graph diagram showing paths between words that differ by one letter. Starting at CAB, paths lead through CAR and CAT to reach the finish word, BAT, with an additional loop through MAT. The diagram illustrates a word ladder puzzle where the goal is to transform the start word into the finish word through single-letter changes.

Answer: The shortest path has a length of 2.

6.3 Here's a small graph of my morning routine.

For these three lists, mark whether each one is valid or invalid.

Figure 6.1 summary: A directed graph diagram showing paths from a start node S to a finish node F. The graph consists of five nodes connected by arrows, illustrating multiple possible routes from start to finish through intermediate nodes. The purpose is to represent a network of paths for a traversal or search problem.

Figure 6.3 summary: A diagram showing three activities in bubbles—Shower, Brush Teeth, and Eat Breakfast—with arrows pointing toward Wake Up and Brush Teeth. Specifically, Shower points to Wake Up, and Eat Breakfast points to Brush Teeth, which in turn points to Wake Up. This structure represents a set of prerequisites or dependencies where these activities must occur before waking up.

A.

1. Wake up

2. Shower

3. Eat Breakfast

4. Brush Teeth B.

1. Wake up

2. Brush Teeth

3. Eat Breakfast

4. Shower

Answers: A—Invalid; B—Valid; C—Invalid.

C.

1. Shower

2. Wake up

3. Brush Teeth

4. Eat Breakfast

6.4 Here's a larger graph. Make a valid list for this graph.

6.5 Which of the following graphs are also trees?

A. B. C.

Image summary: Three diagrams of directed graphs with different structures. The first is a tree with a root node branching down to children; the second is a cyclic graph with multiple interconnected nodes and a return edge to the root; the third is a simple linear chain of nodes. The point is to illustrate different types of graph topologies, ranging from hierarchical to cyclic and sequential.

Answers: A—Tree; B—Not a tree; C—Tree. The last example is just a sideways tree. Trees are a subset of graphs. So a tree is always a graph, but a graph may or may not be a tree.

Figure 6.4 summary: A flow diagram depicting a morning routine where several activities lead back to the starting point of waking up. The sequences show exercise leading to shower and then getting dressed, as well as eating breakfast leading to brushing teeth. Additionally, packing lunch is listed as a separate activity. The diagram illustrates the various components and order of a daily morning sequence.

Chapter 7

7.1 In each of these graphs, what is the weight of the shortest path from start to finish?

Figure 7.1 summary: A diagram of a weighted directed graph consisting of nodes and edges connecting a START node to a FINISH node. The edges are labeled with numerical weights, showing multiple possible paths from start to finish with varying costs. The purpose of the figure is to illustrate a network for pathfinding or optimization problems.

Image summary: A directed graph diagram showing a network of five nodes connecting a START node to a FINISH node. Edges are labeled with weights, where most paths have a weight of 2, except for one backward edge with a weight of -1. The diagram illustrates a weighted graph, likely used to demonstrate pathfinding or the impact of negative edge weights.

Answers: A: A 8; B 60; C—Trick question. No shortest path is possible (negative-weight cycle).

Figure B summary: A diagram of a directed graph consisting of five nodes and five edges. The path begins at a START node and leads to a FINISH node, with edges labeled with costs or weights including 1, 2, 3, and 1. The structure depicts a network of possible paths from a starting point to a destination.

Chapter 8

8.1 You work for a furniture company, and you have to ship furniture all over the country. You need to pack your truck with boxes. All the boxes are of different sizes, and you're trying to maximize the space you use in each truck.

How would you pick boxes to maximize space? Come up with a greedy strategy. Will that give you the optimal solution?

Answer: A greedy strategy would be to pick the largest box that will fit in the remaining space, and repeat until you can't pack any more boxes. No, this won't give you the optimal solution.

8.2 You're going to Europe, and you have seven days to see everything you can. You assign a point value to each item (how much you want to see it) and estimate how long it takes. How can you maximize the point total (seeing all the things you really want to see) during your stay? Come up with a greedy strategy. Will that give you the optimal solution?

Answer: Keep picking the activity with the highest point value that you can still do in the time you have left. Stop when you can't do anything else. No, this won't give you the optimal solution.

For each of these algorithms, say whether it's a greedy algorithm or not.

8.3 Quicksort Answer: No.

8.4 Breadth-first search Answer: Yes.

8.5 Dijkstra's algorithm

Answer: Yes.

8.6 A postman needs to deliver to 20 homes. He needs to find the shortest route that goes to all 20 homes. Is this an N.P-complete problem?

Answer: Yes.

Answer: Yes.

8.8 You're making a map of the U.S.A, and you need to color adjacent states with different colors. You have to find the minimum number of colors you need so that no two adjacent states are the same color. Is this an N.P-complete problem?

Answer: Yes.

Chapter 9

9.1 Suppose you can steal another item: an M.P.3 player. It weighs 1 pounds and is worth $1,000. Should you steal it?

Answer: Yes. Then you could steal the M.P.3 player, the iPhone, and the guitar, worth a total of $4,500.

9.2 Suppose you're going camping. You have a knapsack that holds 6 pounds, and you can take the following items. They each have a value, and the higher the value, the more important the item is:

• Water, 3 pounds, 10

• Book, 1 pounds, 3

• Food, 2 pounds, 9

• Jacket, 2 pounds, 5

• Camera, 1 pounds, 6

What's the optimal set of items to take on your camping trip? Answer: You should take water, food, and a camera.

9.3 Draw and fill in the grid to calculate the longest common substring between blue and clues.

Answer:

: Table summary: A grid of characters where the top row contains the letters C, L, U, E, and S. The subsequent rows consist primarily of the letter O, with three exceptions: an I in the second row under U, a 2 in the third row under E, and a 3 in the fourth row under S.

Chapter 10

10.1 In the Netflix example, you calculated distance between two different users using the distance formula. But not all users rate movies the same way. Suppose you have two users, Yogi and Pinky, who have the same taste in movies. But Yogi rates any movie he likes as a 5, whereas Pinky is choosier and reserves the 5s for only the best.

Answer: You could use something called normalization. You look at the average rating for each person and use it to scale their ratings. For example, you might notice that Pinky's average rating is 3, whereas Yogi's average rating is 3.5. So you bump up Pinky's ratings a little, until her average rating is 3.5 as well. Then you can compare their ratings on the same scale.

10.2 Suppose Netflix nominates a group of “influencers.” For example, Quentin Tarantino and Wess Anderson are influencers on Netflix, so their ratings count for more than a normal user's. How would you change the recommendations system so it's biased toward the ratings of influencers?

Answer: You could give more weight to the ratings of the influencers when using K.N.N. Suppose you have three neighbors: Joe, Dave, and Wess Anderson (an influencer). They rated Caddyshack a 3, a 4, and a 5, respectively. Instead of just taking the average of their ratings (3 plus 4 plus 5 divided by 3 equals 4 stars), you could give Wess Anderson's rating more weight: 3 plus 4 plus 5 plus 5 plus 5 divided by 5 equals 4.4 stars.

Answer: It's too low. If you look at fewer neighbors, there's a bigger chance that the results will be skewed. A good rule of thumb is, if you have N users, you should look at sqrt(N) neighbors.

Index

A

adit dot io 212 algorithms approximation algorithms

147 to 150 calculating answer 149 code for setup 147 to 148 sets 149 to 150

Bellman-Ford 130

Big O notation and 10 to 19 common run times 15 to 16 drawing squares example

13 to 14 exercises 17 growth of run times at different rates 11 to 13 overview 10 traveling salesperson problem 17 to 19 worst-case run time 15 binary search 3 to 10 better way to search 5 to 7 exercises 6 to 9 overview 3 to 4 running time 10 breadth-first search 107 to 113 exercise 111 to 113 running time 111

Dijkstra's algorithm 115 to 139 exercise 139 implementation 131 to 139 negative-weight edges

128 to 130 overview 115 to 119 terminology related to

120 to 122 trading for piano example

122 to 128 distributed, usefulness of 209

Euclid's 54

Feynman 180 greedy algorithms 141 to 159 classroom scheduling problem 142 to 144 exercises 145 to 146 knapsack problem 144 to 145

N.P-complete problems 152 to 158 overview 141 set-covering problem 146 to 151

HyperLogLog algorithm 213 k-nearest neighbors algorithm building recommendations system 189 to 194 classifying oranges versus grapefruit 187 to 189 exercises 195 to 199 machine learning 199 to 201

MapReduce algorithm 209 to 211 map function 209 to 210 reduce function 210 to 211 parallel 208

S.H.A algorithms 213 to 216 checking passwords 215 to 216 comparing files 214 overview 213 approximation algorithms 147 to 150 calculating answer 149 code for setup 147 to 148 sets 149 to 150 arrays deletions and 30 exercises 30 to 31 insertions and 28 to 29 overview 28 terminology used with 27 to 28 uses of 26 to 27

B

base case 40 to 41, 41, 53

Bellman-Ford algorithm 130 best station 151

Better Explained website 207

Big O notation 10 to 19 common run times 15 to 16 drawing squares example 13 to 14 exercises 17 growth of run times at different rates 11 to 13 overview 10 quicksort and 66 to 71 average case versus worst case 68 to 71 exercises 72 merge sort versus quicksort

67 to 68 overview 66 traveling salesperson problem

17 to 19 worst-case run time 15 binary search 3 to 10 better way to search 5 to 7 exercises 6 to 9 overview 3 to 4 running time 10 binary search trees 204 to 205 bloom filters 211 to 212 breadth-first search 95 to 113 graphs and 99 to 104 exercises 104 finding shortest path

102 to 103 overview 107 to 110 queues 103 to 104 implementing 105 to 106 implementing algorithm

107 to 113 exercise 111 to 113 overview 107 to 110 running time 111 overview 95 to 98 built-in hash table 90 bye function 44

C

cache, using hash tables as 83 to 85

Caldwell, Leigh 40 call stack overview 42 to 45 with recursion 45 to 50 cheapest node 117, 125 classification 189 classroom scheduling problem 142 to 144 common substring 184 constants 35 constant time 88 to 89 covered set 151

Ctrl-C shortcut 41 cycles, graph 121

D

A.G's (directed acyclic graphs)

122

D&C (divide and conquer) 52 to 60 def countdown(i) function 41 deletions 30 deque function 107 dict function 78

Diffie-Hellman key exchange 217

Dijkstra's algorithm 115 to 139 exercise 139 implementation 131 to 139 negative-weight edges 128 to 130 overview 115 to 119 terminology related to 120 to 122 trading for piano example 122 to 128 directed graph 106 distance formula 194 distributed algorithms 209

D.N.S resolution 81 double-ended queue 107 duplicate entries, preventing 81 to 83 dynamic programming 161 to 185 exercises 173 to 178, 186 knapsack problem 161 to 171 changing order of rows 174

F.A.Q 171 to 173 filling in grid column-wise 174 guitar row 164 to 167 if solution doesn't fill knapsack completely 178 if solution requires more than two sub-knapsacks 177 laptop row 168 to 170 optimizing travel itinerary 175 to 177 overview 161 simple solution 162 to 163 stealing fractions of an item 175 stereo row 166 to 168 longest common substring 178 to 185 filling in grid 180 to 182 longest common subsequence 183 to 186 making grid 179 to 180 overview 179 to 180 solution 182 to 183

E

edges 99, 113 empty array 57, 58 encrypted messages 218 enqueue operation 104

Euclid's algorithm 54

F

acebook, user login and signups example 31 fact function 45, 47 factorial function 45 factorial time 19 false negatives 212 false positives 212

Feynman algorithm 180

fifo (First In, First Out) data structure 104 find_lowest_cost node function 134, 139 first-degree connection 103 for loop 149 for node 136

Fourier transform 207 to 208

G

git diff 185 graphs breadth-first search and 99 to 104 exercises 104 finding shortest path

102 to 104 overview 99 to 101 queues 103 to 104 overview 96 to 98 graph["start"] hash table 132 greedy algorithms 141 to 159 classroom scheduling problem

142 to 144 exercises 145 to 146 knapsack problem 144 to 145

N.P-complete problems 152 to 158 set-covering problem 146 to 151 approximation algorithms

147 to 150 back to code 151 to 152 exercise 152 overview 146 greet2 function 44 greet function 43 to 45

H

hash tables 73 to 88 collisions 86 to 88 hash functions 76 to 78 performance 88 to 91 exercises 93 good hash function 90 to 91 load factor 90 to 91 use cases 79 to 86 preventing duplicate entries 81 to 83 using hash tables as cache 83 to 85 using hash tables for lookups 79 to 81

Haskell 59

HyperLogLog algorithm 213

，

inductive proofs 65 infinity, representing in Python

133 insertions 28 to 29 inverted indexes 206 to 207

I.P address, mapping web address to 81

J.P.G format 207

K

han Academy 7, 54 knapsack problem changing order of rows 174 F.A.Q 171 to 173 filling in grid column-wise 174 guitar row 164 to 167 if solution doesn't fill knapsack completely 178 if solution requires more than two sub-knapsacks 177 laptop row 168 to 170 optimizing travel itinerary 175 to 177 overview 144 to 145, 161 simple solution 162 to 163 stealing fractions of an item 175 stereo row 166 to 168 k-nearest neighbors algorithm building recommendations system 189 to 194 classifying oranges versus grapefruit 187 to 189 exercises 195 to 198 machine learning 199 to 201

L

evenshtein distance 185

lifo (Last In, Last Out) data structure 104 linear programming 218 to 219 linear time 10, 15, 89 linked lists 25 to 26 deletions and 30 exercises 28, 30 to 31 insertions and 28 to 29 overview 25 to 26 terminology used with 27 to 28 load balancing 208 locality-sensitive hashing 216 logarithmic time. See log time logarithms 7 log time 7, 10, 15 lookups, using hash tables for 79 to 81

M

machine learning 199 to 201

MapReduce algorithm map function 209 to 210 reduce function 210 to 211 memory 22 to 23 merge sort versus quicksort 67 to 68

M.P.3 format 207

N

aive Bayes classifier 200 name variable 43 neighbors 99 n! (n factorial) operations 19 nodes 99, 105 n operations 12

N.P-complete problems 152 to 158

O

C.R (optical character recognition) 199 to 201 parallel algorithms 208 partitioning 61 person_is seller function 108, 111 pivot element 60 pop (remove and read) action 42

Print function 43 print items function 67 private key, Diffie-Hellman 218 probabilistic data structure 212 pseudocode 38, 40, 182 public key, Diffie-Hellman 218 push (insert) action 42

Pythagorean formula 191

Q

queues 30 to 31 quicksort, Big O notation and

66 to 71 average case versus worst case

68 to 71 exercises 72 merge sort versus quicksort 67 to 68

R

random access 30 recommendations system, building

189 to 194 recursion 37 to 49 base case and recursive case

40 to 41 call stack with 45 to 50 overview 37 to 39 regression 196 resizing 91 run time common run times 15 to 16 growth of at different rates

11 to 13 overview 10

S

searches binary search 3 to 10 as better way to search 5 to 7 exercises 6 to 9 overview 3 to 4 running time 10 breadth-first search graphs and 99 to 104 implementing 105 to 106 implementing algorithm

107 to 113 selection sort 32 to 33 sequential access 30 set-covering problem 146 to 151 approximation algorithms calculating answer 149 code for setup 147 to 148 sets 149 to 150 exercise 152 overview 146 set difference 150 set intersection 150 sets 148 set union 150

S.H.A algorithms 213 to 216 checking passwords 215 to 216 comparing files 214 overview 213

S.H.A (Secure Hash Algorithm)

function 92, 214 shortest path 98, 128 signals, processing 207

Simhash 216, 217 simple search 5, 11, 200

S.Q.L query 209 stacks 42 to 49 call stack 43 to 45 call stack with recursion 45 to 50 exercise 45, 49 to 50 overview 42 states covered set 149 states_for station 151 states needed 151 stock market, predicting 201 strings, mapping to numbers 76 sum function 57, 59

T

third-degree connection 103 topological sort 112 training 200 trees 203 to 206 undirected graph 122 unique searches 213 unweighted graph 120 weighted graph 120

grokking algorithms

An illustrated guide for programmers and other curious people

Aditya Y. Bhargava

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

Grokking Algorithms is a friendly take on this core computer science topic. In it, you'll learn how to apply common algorithms to the practical programming problems you face every day. You'll start with tasks like sorting and searching.

As you build up your skills, you'll tackle more complex problems like dynamic programming and recommender systems. Each carefully presented example includes helpful diagrams and fully annotated code samples in Python. By the end of this book, you will have mastered widely applicable algorithms as well as how and when to use them.

What's Inside

• Covers search, sort, and graph algorithms

Over 400 pictures with detailed walkthroughs

• Performance trade-offs between algorithms

• Python-based code samples

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

To download their free eBook in P.D.F, ePub, and Kindle formats, owners of this book should visit manning dot com U.R.L

“This book does the impossible: it makes math fun and easy!”

—Sander Rossel C.O.A's Software Systems

“Do you want to treat yourself to learning algorithms in the same way that you would read your favorite novel? If so, this is the book you need!”

—Sankar Ramanathan I.B.M Analytics

“In today's world, there is no aspect of our lives that isn't optimized by some algorithm. Let this be the first book you pick up if you want a well-explained introduction to the topic.”

—Amit Lamba Tech Overture, L.L.C

“Algorithms are not boring! This book was fun and insightful for both my students and me.”

—Christopher Haupt Mobirobo, Inc

I.S.B.N-13: 978-1-61729-223-1

I.S.B.N-10: 1-61729-223-0

You have reached the end of the document.