Grokking Algorithms

answers to exercises

---

---

235
A
adit.io 212
algorithms
approximation algorithms
147–150
calculating answer 149
code for setup 147–148
sets 149–150
Bellman-Ford 130
Big O notation and 10–19
common run times 15–16
drawing squares example
13–14
exercises 17
growth of run times at difer-
ent rates 11–13
overview 10
traveling salesperson prob-
lem 17–19
worst-case run time 15
binary search 3–10
better way to search 5–7
exercises 6–9
overview 3–4
running time 10
breadt
h-irst search 107–113
exercise 111–113
running time 111
Dijkstra’s algorithm 115–139
exercise 139
implementation 131–139
negative-weight edges
128–130
overview 115–119
terminology related to
120–122
trading for piano example
122–128
distributed, usefulness of 209
Euclid’s 54
Feynman 180
greedy algorithms 141–159
classroom scheduling prob-
lem 142–144
exercises 145–146
knapsack problem 144–145
NP-complete problems
152–158
overview 141
set-covering problem
146–151
HyperLogLog algorithm 213
k-nearest neighbors algorithm
building recommendations 
system 189–194
classifying oranges vs. grape-
fruit 187–189
exercises 195–199
machine learning 199–201
MapReduce algorithm 209–211
map function 209–210
reduce function 210–211
parallel 208
SHA algorithms 213–216
checking passwords 215–216
comparing iles 214
overview 213
approximation algorithms
147–150
calculating answer 149
code for setup 147–148
sets 149–150
arrays
deletions and 30
exercises 30–31
insertions and 28–29
overview 28
terminology used with 27–28
uses of 26–27
B
base case 40–41, 41, 53
Bellman-Ford algorithm 130
best_station 151
Better Explained website 207
Big O notation 10–19
common run times 15–16
drawing squares example 13–14
exercises 17
growth of run times at diferent 
rates 11–13
overview 10
quicksort and 66–71
average case vs. worst case
68–71
exercises 72