Chapter 11: Next?

• Tree

  • Binary Search Tree

  • B-trees

  • Red-black trees

  • Heaps

  • Splay trees

• Inverted indexes

  • search engine works

• The Fourier transform

  • given a song, the transform can separate it into individual frequencies.

• Parallel algorithms

  • Overhead of managing the parallelism

  • Load balancing

• MapReduce

  • the distributed algorithm

  • Suppose you have a table with billions or trillions of rows, and you want to run a complicated SQL query on it. You can’t run it on MySQL, because it struggles after a few billion rows. Use MapReduce through Hadoop!

  • MapReduce in particular is built up from two simple ideas: the map function and the reduce function

• Bloom filters and HyperLogLog

• The SHA algorithms

  • Comparing files

  • Checking passwords

• Locality-sensitive hashing

• Diffie-Hellman key exchange

  • RSA

• Linear programming