Algorithms

Programming Pearls

Programing Pearls - Jon Bentley Excellent. Until now, there is no such book which makes me shout out like this after receiving from Amazon. Let brieftly review some favoriate books: CLRS: theoretically, this really is an “introduction” textbook about algorithms. Nonetheless, it still is an extensive reference and full of details. However, I am not impressed by the writing style and the pseudo-code. Algorithms, Sedgewick: one of the best textbooks ever.

Generate the inversion table from an integer sequence

The programming exercise is from TAoCP, Vol3, 5.1.1-6: Design an algorithm that computes the inversion table $b_1, b_2 \cdots b_n$ corresponding to a given permutation $a_1a_2 \cdots a_n$ of ${1, 2, \cdots , n}$, where the running time is essentially proportional to $n\ log n$ on typical computers. I was really stuck on the solution Knuth given in the book. The author also mentioned another approach which actually is a modifination of merge sort.

An adventure in The Art of Computer Programming

My notes whilst reading TAoCP