Grokking Algorithms: An illustrated guide for programmers and other curious people
256
Grokking Algorithms: An illustrated guide for programmers and other curious people
256eBook
Related collections and offers
Overview
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
- Covers search, sort, and graph algorithms
- Over 400 pictures with detailed walkthroughs
- Performance trade-offs between algorithms
- Python-based code samples
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
- Introduction to algorithms
- Selection sort
- Recursion
- Quicksort
- Hash tables
- Breadth-first search
- Dijkstra's algorithm
- Greedy algorithms
- Dynamic programming
- K-nearest neighbors
Product Details
| ISBN-13: | 9781638353348 |
|---|---|
| Publisher: | Manning |
| Publication date: | 05/12/2016 |
| Sold by: | SIMON & SCHUSTER |
| Format: | eBook |
| Pages: | 256 |
| Sales rank: | 935,532 |
| File size: | 10 MB |
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
Preface xiii
Acknowledgments xiv
About this book xv
1 Introduction to algorithms 1
Introduction 1
What you'll learn about performance 2
What you'll learn about solving problems 2
Binary search 3
A better way to search 5
Running time 10
Big O notation 10
Algorithm running times grow at different rates 11
Visualizing different Big O run times 13
Big O establishes a worst-case run time 15
Some common Big O run times 15
The traveling salesperson 17
Recap 19
2 Selection sort 21
How memory works 22
Arrays and linked lists 24
Linked lists 25
Arrays 26
Terminology 27
Inserting into the middle of a list 29
Deletions 30
Selection sort 32
Recap 36
3 Recursion 37
Recursion 38
Base case and recursive case 40
The stack 42
The call stack 43
The call stack with recursion 45
Recap 50
4 Quicksort 51
Divide & conquer 52
Quicksort 60
Big O notation revisited 66
Merge sort vs. quicksort 67
Average case vs. worst case 68
Recap 72
5 Hash tables 73
Hash functions 76
Use cases 79
Using hash tables for lookups 79
Preventing duplicate entries 81
Using hash tables as a cache 83
Recap 86
Collisions 86
Performance 88
Load factor 90
A good hash function 92
Recap 93
6 Breadth-first search 95
Introduction to graphs 96
What is a graph? 98
Breadth-first search 99
Finding the shortest path 102
Queues 103
Implementing the graph 105
Implementing the algorithm 107
Running time 111
Recap 114
7 Dijkstra's algorithm 115
Working with Dijkstra's algorithm 116
Terminology 120
Trading for a piano 122
Negative-weight edges 128
Implementation 131
Recap 140
8 Greedy algorithms 141
The classroom scheduling problem 142
The knapsack problem 144
The set-covering problem 146
Approximation algorithms 147
NP-complete problems 152
Traveling salesperson, step by step 153
How do you tell if a problem is NP-complete? 158
Recap 160
9 Dynamic programming 161
The knapsack problem 161
The simple solution 162
Dynamic programming 163
Knapsack problem FAQ 171
What happens if you add an item? 171
What happens if you change the order of the rows? 174
Can you fill in the grid column-wise instead of row-wise? 174
What happens if you add a smaller item? 174
Can you steal fractions of an item? 175
Optimizing your travel itinerary 175
Handling items that depend on each other 177
Is it possible that the solution will require more than two sub-knapsacks? 177
Is it possible that the best solution doesn't fill the knapsack completely? 178
Longest common substring 178
Making the grid 179
Filling in the grid 180
The solution 182
Longest common subsequence 183
Longest common subsequence-solution 184
Recap 186
10 K-nearest neighbors 187
Classifying oranges vs. grapefruit 187
Building a recommendations system 189
Feature extraction 191
Regression 195
Picking good features 198
Introduction to machine learning 199
OCR 199
Building a spam filter 200
Predicting the stock market 201
Recap 201
11 Where to go next 203
Trees 203
Inverted indexes 206
The Fourier transform 207
Parallel algorithms 208
MapReduce 209
Why are distributed algorithms useful? 209
The map function 209
The reduce function 210
Bloom filters and HyperLogLog 211
Bloom filters 212
HyperLogLog 213
The SHA algorithms 213
Comparing files 214
Checking passwords 215
Locality-sensitive hashing 216
Diffie-Hellman key exchange 217
Linear programming 218
Epilogue 219
Answers to exercises 221
Index 235