In a slightly simplified explanation, hash tables are just arrays that with the keys mapped to the indexes. A key is transformed in an index through a hash function.A good hash function must be:<ul><li>consistent: it should always produce the same output for the same key</li><li>collision-free: it should minimize the number of keys that are mapped to the same number</li></ul>In case the hash function still causes collisions (e.g. for memory reasons), it could be changed so that an entry in the array no longer contains a single value, but a new data structure (such as a linked list or even a new hash table).

Hash Tables Under The Hood

Breadth-first search is used to find the shortest path in an unweighted graph.Dijkstra’s Algorithm is used to find the shortest path in a directed, acyclic graph (DAG).The topological sort of a directed graph is the set of nodes ordered such that if u->v is an edge, then u comes before v in the sorting.

On Graph Algorithms

There’s no easy way to tell if a problem is NP-complete. Here are some giveaways: <ul><li>Your algorithm runs quickly with a handful of items but really slows down with more items. </li><li>“All combinations of X” usually point to an NP-complete problem. </li><li>Do you have to calculate “every possible version” of X because you can’t break it down into smaller sub-problems? Might be NP-complete.</li><li>Can you restate your problem as the set-covering problem or the traveling-salesperson problem? Then your problem is definitely NP-complete.</li></ul>

NP-completeness

The book covers algorithms at a basic level. I knew most of the stuff, so here are only so brief notes I took.

"This book does the impossible: it makes math fun and easy!" - Sander Rossel, COAS Software Systems Grokking Algorithms is a fully illustrated, friendly guide that teaches you how to apply common algorithms to the practical problems you face every day as a programmer. You'll start with sorting and searching and, as you build up your skills in thinking algorithmically, you'll tackle more complex concerns such as data compression and artificial intelligence. Each carefully presented example includes helpful diagrams and fully annotated code samples in Python. Learning about algorithms doesn't have to be boring! Get a sneak peek at the fun, illustrated, and friendly examples you'll find in Grokking Algorithms on Manning Publications' YouTube channel. Continue your journey into the world of algorithms with Algorithms in Motion, a practical, hands-on video course available exclusively at Manning.com (www.manning.com/livevideo/algorithms-?in-motion). Purchase of the print book includes a free eBook in PDF, Kindle, and ePub formats from Manning Publications. About the Technology An algorithm is nothing more than a step-by-step procedure for solving a problem. The algorithms you'll use most often as a programmer have already been discovered, tested, and proven. If you want to understand them but refuse to slog through dense multipage proofs, this is the 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. About the Book Grokking Algorithms is a friendly take on this core computer science topic. In it, you'll learn how to apply common algorithms to the practical programming problems you face every day. You'll start with tasks like sorting and searching. As you build up your skills, you'll tackle more complex problems like data compression and artificial intelligence. Each carefully presented example includes helpful diagrams and fully annotated code samples in Python. By the end of this book, you will have mastered widely applicable algorithms as well as how and when to use them. What's Inside <ul> <li>Covers search, sort, and graph algorithms</li> <li>Over 400 pictures with detailed walkthroughs</li> <li>Performance trade-offs between algorithms</li> <li>Python-based code samples</li> </ul> About the Reader This easy-to-read, picture-heavy introduction is suitable for self-taught programmers, engineers, or anyone who wants to brush up on algorithms. About the Author Aditya Bhargava is a Software Engineer with a dual background in Computer Science and Fine Arts. He blogs on programming at adit.io. Table of Contents <ol> <li>Introduction to algorithms</li> <li>Selection sort</li> <li>Recursion</li> <li>Quicksort</li> <li>Hash tables</li> <li>Breadth-first search</li> <li>Dijkstra's algorithm</li> <li>Greedy algorithms</li> <li>Dynamic programming</li> <li>K-nearest neighbors</li> </ol>

Grokking Algorithms

Hash Tables Under The Hood

On Graph Algorithms

NP-completeness

Other curated ideas on this topic: