Grokking Algorithms

E
edges 99, 113
empty array 57, 58
encrypted messages 218
enqueue operation 104
Euclid’s algorithm 54
F
Facebook, 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–208
G
git diff 185
graphs
breadth-first search and 99–104
exercises 104
finding shortest path
102–104
overview 99–101
queues 103–104
overview 96–98
graph[“start”] hash table 132
greedy algorithms 141–159

---

237
i
ndex
classroom scheduling problem
142–144
exercises 145–146
knapsack problem 144–145
NP-complete problems 152–158
set-covering problem 146–151
approximation algorithms
147–150
back to code 151–152
exercise 152
overview 146
greet2 function 44
greet function 43–45
H
hash tables 73–88
collisions 86–88
hash functions 76–78
performance 88–91
exercises 93
good hash function 90–91
load factor 90–91
use cases 79–86
preventing duplicate entries
81–83
using hash tables as cache
83–85
using hash tables for lookups
79–81
Haskell 59
HyperLogLog algorithm 213
I
inductive proofs 65
infinity, representing in Python
133
insertions 28–29
inverted indexes 206–207
IP address, mapping web address 
to 81
J
JPG format 207
K
Khan Academy 7, 54
knapsack problem
changing order of rows 174
FAQ 171–173
filling in grid column-wise 174
guitar row 164–167
if solution doesn’t fill knapsack 
completely 178
if solution requires more than 
two sub-knapsacks 177
laptop row 168–170
optimizing travel itinerary
175–177
overview 144–145, 161
simple solution 162–163
stealing fractions of an item 175
stereo row 166–168
k-nearest neighbors algorithm
building recommendations 
system 189–194
classifying oranges vs. grapefruit
187–189
exercises 195–198
machine learning 199–201
L
Levenshtein distance 185
LIFO (Last In, Last Out) data 
structure 104
linear programming 218–219
linear time 10, 15, 89
linked lists 25–26
deletions and 30
exercises 28, 30–31
insertions and 28–29
overview 25–26
terminology used with 27–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–81
M
machine learning 199–201
MapReduce algorithm
map function 209–210
reduce function 210–211
memory 22–23
merge sort vs. quicksort 67–68
MP3 format 207
N
Naive Bayes classifier 200
name variable 43
neighbors 99
n! (n factorial) operations 19
nodes 99, 105
n operations 12
NP-complete problems 152–158