I plan on blogging my way through the chapters writing my answers to the questions as I go through the book. Like most of my plans they don't always work out, but one could try.
Here it goes!
Multiplying Matrices - graphics and scientific problems frequently require matrix operations.
Convex Hull - Collision detection for use in games, modeling biological systems, or other related work could make use of this
While most probabilistic structures have certain properties in common, bloom filters have a number of interesting pros and cons.
- A negative result is definitive - if a query returns that an element has not been added then one knows this to be 100% true.
- Since hashes are fixed size the amount of memory a Bloom Filter uses is known and bounded.
- Bloom filters can quickly become useless with large amounts of data. It is possible that every bit will be set to 1 which effectively makes the query a NOP.
- It is impossible to remove data from a bloom filter. One can't just set all the bits of the hash to a zero because that might be removing other elements as well.
- Without a second set of data there is no way to deterministically list all elements (unlike other probabilistic data structures such as Skip Lists).
- The shortest path problem is
- Given a weighted (undirected) graph G:
, a start vertex $V_0$ and an end vertex $V_e$, find a path between $V_0$ and $V_e$ such that the sum of the weights is minimized. This could be expanded to $Given a weighted graph G: , find a path between every pair such that the sum of the weights for each path is minimized.
- Traveling salesman is defined as:
- Given a weighted, undirected, graph G:
and a start vertex $V_0$ find a path starting and ending at $V_0$ such that it passes through every other vertex exactly once and the sum of the weights is minimized.