Grokking Algorithms

Index

---

236
i
ndex
merge sort vs. quicksort
67–68
overview 66
traveling salesperson problem
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
binary search trees 204–205
bloom filters 211–212
breadth-first search 95–113
graphs and 99–104
exercises 104
finding shortest path
102–103
overview 107–110
queues 103–104
implementing 105–106
implementing algorithm
107–113
exercise 111–113
overview 107–110
running time 111
overview 95–98
built-in hash table 90
bye function 44
C
cache, using hash tables as 83–85
Caldwell, Leigh 40
call stack
overview 42–45
with recursion 45–50
cheapest node 117, 125
classification 189
classroom scheduling problem
142–144
common substring 184
constants 35
constant time 88–89
covered set 151
Ctrl-C shortcut 41
cycles, graph 121
D
DAGs (directed acyclic graphs)
122
D&C (divide and conquer) 52–60
def countdown(i) function 41
deletions 30
deque function 107
dict function 78
Diffie-Hellman key exchange 217
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
directed graph 106
distance formula 194
distributed algorithms 209
DNS resolution 81
double-ended queue 107
duplicate entries, preventing
81–83
dynamic programming 161–185
exercises 173–178, 186
knapsack problem 161–171
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 161
simple solution 162–163
stealing fractions of an item
175
stereo row 166–168
longest common substring
178–185
filling in grid 180–182
longest common
subsequence 183–186
making grid 179–180
overview 179–180
solution 182–183