Algorithm Insights

Merge sort is not an in-place sort, it requires space
Insertion sort is an in-place sort, O(n) if already sort, so good on almost sorted stuff

Heap sort is an in-place sort, "who is where in the heap?" impossible, because it's not a binary search tree. A max-heap is good for job scheduling on a shared computer (highest priority); a min-heap is good for an event-driven simulator (smallest time/key must run first, or future events might got messed up =p) p. 138

Quick sort is an in-place sort, O(n^2) if the stuff is already sorted
why? each iteration will need n times (sort in place), if partition is so bad, we divide the array n times, so n*n, if partition is good, we divide logn time, so n*log n

A hash function is a mathematical function that maps keys to integers.
The result is unique identifier numbers, but they are so large they will quickly
exceed the number of slots in our hash table (denoted by m). We must reduce this
number to an integer between 0 and m−1, by taking the remainder of H(S) mod m
(ideally m is a large prime not too close to 2i − 1) p.101
why?
Collision- chaining (bucket), open addressing (next value), Cuckoo hashing(hash twice)

compare: cryptographic hashing
compare: database index http://en.wikipedia.org/wiki/Index_(database) http://mattfleming.com/node/192