Grokking Algorithms: An illustrated guide for programmers and other curious people

Previous Chapter

Appendix. Answers to Exercises

Index

[A][B][C][D][E][F][G][H][I][J][K][L][M][N][O][P][Q][R][S][T][U][W]

A

adit.io algorithms approximation algorithms calculating answer code for setup sets Bellman-Ford Big O notation and common run times drawing squares example exercises growth of run times at different rates overview traveling salesperson problem worst-case run time binary search binary search better way to search exercises overview running time breadth-first search breadth-first search exercise running time Dijkstra’s algorithm Dijkstra’s algorithm exercise implementation negative-weight edges overview terminology related to trading for piano example distributed, usefulness of Euclid’s Feynman greedy algorithms greedy algorithms classroom scheduling problem exercises knapsack problem NP-complete problems overview set-covering problem approximation algorithms back to code exercise overview HyperLogLog algorithm k-nearest neighbors algorithm building recommendations system classifying oranges vs. grapefruit exercises machine learning MapReduce algorithm map function reduce function parallel SHA algorithms SHA algorithms checking passwords comparing files overview approximation algorithms calculating answer code for setup sets arrays deletions and exercises insertions and overview terminology used with uses of

B

base case, 2^nd, 3^rd Bellman-Ford algorithm best_station Better Explained website Big O notation common run times drawing squares example exercises growth of run times at different rates overview quicksort and average case vs. worst case exercises merge sort vs. quicksort overview traveling salesperson problem worst-case run time binary search binary search better way to search exercises overview running time binary search trees bloom filters breadth-first search breadth-first search graphs and exercises finding shortest path overview queues implementing implementing algorithm exercise overview running time overview built-in hash table bye function

C

cache, using hash tables as Caldwell, Leigh call stack overview with recursion cheapest node, 2^nd classification classroom scheduling problem common substring constants constant time covered set Ctrl-C shortcut cycles, graph

D

DAGs (directed acyclic graphs) D&C (divide and conquer) def countdown(i) function deletions deque function dict function Diffie-Hellman key exchange Dijkstra’s algorithm Dijkstra’s algorithm exercise implementation negative-weight edges overview terminology related to trading for piano example directed graph distance formula distributed algorithms DNS resolution double-ended queue duplicate entries, preventing dynamic programming exercises, 2^nd knapsack problem changing order of rows FAQ filling in grid column-wise guitar row if solution doesn’t fill knapsack completely if solution requires more than two sub-knapsacks laptop row optimizing travel itinerary overview simple solution stealing fractions of an item stereo row longest common substring filling in grid longest common subsequence making grid overview solution

E

edges, 2^nd empty array, 2^nd encrypted messages enqueue operation Euclid’s algorithm

F

Facebook, user login and signups example fact function, 2^nd factorial function factorial time false negatives false positives Feynman algorithm FIFO (First In, First Out) data structure find_lowest_cost_node function, 2^nd first-degree connection for loop for node Fourier transform

G

git diff graphs breadth-first search and exercises finding shortest path overview queues overview graph[“start”] hash table greedy algorithms greedy algorithms classroom scheduling problem exercises knapsack problem NP-complete problems set-covering problem approximation algorithms back to code exercise overview greet2 function greet function

H

hash tables collisions hash functions performance exercises good hash function load factor use cases preventing duplicate entries using hash tables as cache using hash tables for lookups Haskell HyperLogLog algorithm

I

inductive proofs infinity, representing in Python insertions inverted indexes IP address, mapping web address to

J

K

Khan Academy, 2^nd knapsack problem changing order of rows FAQ filling in grid column-wise guitar row if solution doesn’t fill knapsack completely if solution requires more than two sub-knapsacks laptop row optimizing travel itinerary overview, 2^nd simple solution stealing fractions of an item stereo row k-nearest neighbors algorithm building recommendations system classifying oranges vs. grapefruit exercises machine learning

L

Levenshtein distance LIFO (Last In, Last Out) data structure linear programming linear time, 2^nd, 3^rd linked lists deletions and exercises, 2^nd insertions and overview terminology used with load balancing locality-sensitive hashing logarithmic time. See log time. logarithms log time, 2^nd, 3^rd lookups, using hash tables for

M

machine learning MapReduce algorithm map function reduce function memory merge sort vs. quicksort MP3 format

N

Naive Bayes classifier name variable neighbors n! (n factorial) operations nodes, 2^nd n operations NP-complete problems

O

OCR (optical character recognition)

P

parallel algorithms partitioning person_is_seller function, 2^nd pivot element pop (remove and read) action Print function print_items function private key, Diffie-Hellman probabilistic data structure pseudocode, 2^nd, 3^rd public key, Diffie-Hellman push (insert) action Pythagorean formula

Q

queues quicksort, Big O notation and average case vs. worst case exercises merge sort vs. quicksort

R

random access recommendations system, building recursion base case and recursive case call stack with overview regression resizing run time common run times growth of at different rates overview

S

searches binary search as better way to search exercises overview running time breadth-first search graphs and implementing implementing algorithm selection sort sequential access set-covering problem approximation algorithms calculating answer code for setup sets exercise overview set difference set intersection sets set union SHA algorithms SHA algorithms checking passwords comparing files overview SHA (Secure Hash Algorithm) function, 2^nd shortest path, 2^nd signals, processing Simhash, 2^nd simple search, 2^nd, 3^rd SQL query stacks call stack call stack with recursion exercise, 2^nd overview states_covered set states_for_station states_needed stock market, predicting strings, mapping to numbers sum function, 2^nd

T

third-degree connection topological sort training trees

U

undirected graph unique searches unweighted graph

W

weighted graph

Previous Chapter

Appendix. Answers to Exercises