More Programming Pearls - Reading notes

==## Part I: Programming techniques ##==

==Column 1== Profilers

- Profilers: 1) line-count, 2) procedure-time
- e.g. Optimize prime testing
* test until square root
* rule out 2, 3, 5
* use multiplication instead of division
* test only previous primes
* simple sieve of Evatosthenes
(complexity: time - O((nlogn)(loglogn)), space - O(n)).
(Complexity with optimizations such as wheel factorization: time - O(n), space - O(n^{1 / 2}loglogn / logn)

- A specialized profiler
- Building profiler: 1) insert counter to source code, 2) run it, 3) collect counter output.

==Column 2== Associative arrays

- i.e., Associative array in AWK, or Hash in perl.
- e.g., A finite state machine simulator
- e.g., Topological sorting

==Column 3== Confession of a coder

- Scaffolding for testing and debugging
- e.g. Binary search
- e.g. k-th smallest selection
- e.g. A subroutine library

==Column 4== Self-describing data

- Name-value pairs
- Provenances in programming. (metadata, e.g., history of the code)
- e.g. A sorting lab

==## Part II: Tricks of the trade ##==

==Column 5== Cutting the gordian knot (finding a clever solution to a complex problem)

- Gordius tied the knot. Asia was the promised prize to anyone who can untie it. Alexander the Great approached it in 333 B.C. He drew his sword and slashed through the knot. Asia was soon his.
- Mail sorting: instead of let a clerk do the sorting, just let the mailman drop to different mailbox.
- Data transmission: instead of an automobile courier, use a pigeon.
- Random sample: draw from a box.

==Column 6== Bumper-sticker computer science

- pi seconds is a nano century
- Plagiarism is the sincerest form of flattery
- Coding
* If you can't write it down in English, you can't code it.
- User Interface
- Debugging
- Performance
- Documentation
- Managing software
- Miscellaneous rules

==Column 7== The envelope is back (Back of envelop calculation)

- Order of magnitude.
- Little's Law (Law of system flow and congestion): the average of things in the system is the product of the average rate at which things leave the system and the average time each one spends in the system.

==Column 8== The furbelow memorandum

- Larger programmer stuff team leads to larger cost than expected
- Fred Brooke's Mythical Man Month (1975).

==## Part III: I/O Fit for Humans ##==

==Column 9== Little language

- The PIC language

==Column 10== Document design

- Tables
- 3 design principles: interaction, consistency, minimalism
- Figures
- Text
- Medium

==Column 11== Graphic output

==Column 12== A survey of surveys

==## Part IV: Algorithms ##==

==Column 13== Random sampling

- A flawed algorithm
- * Floyd's algorithm
- * Random permutations

==Column 14== Birth of a cruncher

- The problem
- Newton iteration
- Decide starting point
- Coding

==Column 15== k-th smallest selection

- Problem
- Program.
* O(n log(n)) algorithm
* An O(n) algorithm by L.A.R. Hoare: by quick-sort
- Analysis
- Principles