Grokking Algorithms: An illustrated guide for programmers and other curious people

Copyright

For online information and ordering of this and other Manning books, please visit www.manning.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, PO Box 761

      Shelter Island, NY 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.

Development editor: Jennifer Stout

Technical development editor: Damien White

Project manager: Tiffany Taylor

Copyeditor: Tiffany Taylor

Technical proofreader: Jean-François Morin

Typesetter: Leslie Haimes

Cover and interior design: Leslie Haimes

Illustrations by the author

ISBN: 9781617292231

Printed in the United States of America

1 2 3 4 5 6 7 8 9 10 – EBM – 21 20 19 18 17 16

For my parents, Sangeeta and Yogesh

Brief Table of Contents

Copyright

Brief Table of Contents

Table of Contents

Preface

Acknowledgments

About this Book

Chapter 1. Introduction to Algorithms

Chapter 2. Selection Sort

Chapter 3. Recursion

Chapter 4. Quicksort

Chapter 5. Hash Tables

Chapter 6. Breadth-first Search

Chapter 7. Dijkstra’s algorithm

Chapter 8. Greedy algorithms

Chapter 9. Dynamic programming

Chapter 10. K-nearest neighbors

Chapter 11. Where to go next

 Answers to Exercises

Index

Table of Contents

Copyright

Brief Table of Contents

Table of Contents

Preface

Acknowledgments

About this Book

Chapter 1. Introduction to Algorithms

Introduction

What you’ll learn about performance

What you’ll learn about solving problems

Binary search

A better way to search

Exercises

Running time

Big O notation

Algorithm running times grow at different rates

Visualizing different Big O run times

Big O establishes a worst-case run time

Some common Big O run times

Exercises

The traveling salesperson

Recap

Chapter 2. Selection Sort

How memory works

Arrays and linked lists

Linked lists

Arrays

Terminology

Exercise

Inserting into the middle of a list

Deletions

Exercises

Selection sort

Example Code Listing

Recap

Chapter 3. Recursion

Recursion

Base case and recursive case

The stack

The call stack

Exercise

The call stack with recursion

Exercise

Recap

Chapter 4. Quicksort

Divide & conquer

Exercises

Quicksort

Big O notation revisited

Merge sort vs. quicksort

Average case vs. worst case

Exercises

Recap

Chapter 5. Hash Tables

Hash functions

Exercises

Use cases

Using hash tables for lookups

Preventing duplicate entries

Using hash tables as a cache

Recap

Collisions

Performance

Load factor

A good hash function

Exercises

Recap

Chapter 6. Breadth-first Search

Introduction to graphs

What is a graph?

Breadth-first search

Finding the shortest path

Queues

Exercises

Implementing the graph

Implementing the algorithm

Running time

Exercise

Recap

Chapter 7. Dijkstra’s algorithm

Working with Dijkstra’s algorithm

Terminology

Trading for a piano

Negative-weight edges

Implementation

Exercise

Recap

Chapter 8. Greedy algorithms

The classroom scheduling problem

The knapsack problem

Exercises

The set-covering problem

Approximation algorithms

Exercises

NP-complete problems

Traveling salesperson, step by step

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

Exercises

Recap

Chapter 9. Dynamic programming

The knapsack problem

The simple solution

Dynamic programming

Knapsack problem FAQ

What happens if you add an item?

Exercise

What happens if you change the order of the rows?

Can you fill in the grid column-wise instead of row-wise?

What happens if you add a smaller item?

Can you steal fractions of an item?

Optimizing your travel itinerary

Handling items that depend on each other

Is it possible that the solution will require more than two sub-knapsacks?

Is it possible that the best solution doesn’t fill the knapsack completely?

Exercise

Longest common substring

Making the grid

Filling in the grid

The solution

Longest common subsequence

Longest common subsequence—solution

Exercise

Recap

Chapter 10. K-nearest neighbors

Classifying oranges vs. grapefruit

Building a recommendations system

Feature extraction

Exercises

Regression

Picking good features

Exercise

Introduction to machine learning

OCR

Building a spam filter

Predicting the stock market

Recap

Chapter 11. Where to go next

Trees

Inverted indexes

The Fourier transform

Parallel algorithms

MapReduce

Why are distributed algorithms useful?

The map function

The reduce function

Bloom filters and HyperLogLog

Bloom filters

HyperLogLog

The SHA algorithms

Comparing files

Checking passwords

Locality-sensitive hashing

Diffie-Hellman key exchange

Linear programming

Epilogue

 Answers to Exercises

Chapter 1

Chapter 2

Chapter 3

Chapter 4

Chapter 5

Chapter 6

Chapter 7

Chapter 8

Chapter 9

Chapter 10

Index

Preface

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

A few years ago, I wrote my first illustrated blog post. I’m a visual learner, and I really liked the illustrated style. Since then, I’ve written a few illustrated posts on functional programming, Git, machine learning, and concurrency. By the way: I was a mediocre writer when I started out. Explaining technical concepts is hard. Coming up with good examples takes time, and explaining a difficult concept takes time. So it’s easiest to gloss over the hard stuff. I thought I was doing a pretty good job, until after one of my posts got popular, a coworker came up to me and said, I read your post and I still don’t understand this. I still had a lot to learn about writing.

Somewhere in the middle of writing these blog posts, Manning reached out to me and asked if I wanted to write an illustrated 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.

Acknowledgments

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: Karen Bensdon, Rob Green, Michael Hamrah, Ozren Harlovic, Colin Hastie, Christopher Haupt, Chuck Henderson, Pawel Kozlowski, Amit Lamba, Jean-François 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 CLRS, 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 (KNN)— Covered in chapter 10. This is a simple machine-learning algorithm. You can use KNN to build a recommendations system, an OCR engine, a system to predict stock values—anything that involves predicting a value (We think Adit will rate this movie 4 stars) or classifying an object (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 www.manning.com/books/grokking-algorithms or https://github.com/egonschiele/grokking_algorithms), and execute them. You’ll retain a lot more if you do.

I also recommend doing the exercises in this 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