11 1111 112010-02-03 15:16:38 / rev cd07877f087c+1Divide and conquer1.1 Example 1: CDROM design 41.2 Theory 1: Multiple estimates 71.3 Theory 2: Tree representations 101.4 Example 2: Oil imports 131.5 Example 4: The UNIX philosophy 15How can ancient Sumerian history help us solve problems of our time?From Sumerian times, and maybe before, every empire solved a hardproblem – how to maintain dominion over resentful subjects. The obvioussolution, brute force, costs too much: If you spend the riches of the empirejust to retain it, why have an empire? But what if the resentful subjectswould expend their energy fighting one another instead of uniting againsttheir rulers? This strategy was summarized by Machiavelli [19, Book VI]:A Captain ought. . . endeavor with every art to divide the forces of the enemy,either by making him suspicious of his men in whom he trusted, or by givinghim cause that he has to separate his forces, and, because of this, become weaker.[my italics]Or, in imperial application, divide the resentful subjects into tiny tribes,each too small to discomfort the empire. (For extra credit, reduce thediscomfort by convincing the tribes to fight one another.)Divide and conquer! As an everyday illustration of its importance, imag-ine taking all the files on your computer – mine claims to have 2, 789, 164files – and moving them all into one directory or folder. How wouldyou ever find what you need? The only hope for managing so muchcomplexity is to place the millions of files in a hierarchy. In general,11 1111 112010-02-03 15:16:38 / rev cd07877f087c+1Divide and conquer1.1 Example 1: CDROM design 41.2 Theory 1: Multiple estimates 71.3 Theory 2: Tree representations 101.4 Example 2: Oil imports 131.5 Example 4: The UNIX philosophy 15How can ancient Sumerian history help us solve problems of our time?From Sumerian times, and maybe before, every empire solved a hardproblem – how to maintain dominion over resentful subjects. The obvioussolution, brute force, costs too much: If you spend the riches of the empirejust to retain it, why have an empire? But what if the resentful subjectswould expend their energy fighting one another instead of uniting againsttheir rulers? This strategy was summarized by Machiavelli [19, Book VI]:A Captain ought. . . endeavor with every art to divide the forces of the enemy,either by making him suspicious of his men in whom he trusted, or by givinghim cause that he has to separate his forces, and, because of this, become weaker.[my italics]Or, in imperial application, divide the resentful subjects into tiny tribes,each too small to discomfort the empire. (For extra credit, reduce thediscomfort by convincing the tribes to fight one another.)Divide and conquer! As an everyday illustration of its importance, imag-ine taking all the files on your computer – mine claims to have 2, 789, 164files – and moving them all into one directory or folder. How wouldyou ever find what you need? The only hope for managing so muchcomplexity is to place the millions of files in a hierarchy. In general,Global comments 1Global commentsIs there a reason other than simplicity for estimating the CD’s area as a square rather thana circle? If we overestimated the length of a side (or accurately estimated it) we wouldhave a bigger error.I’m guessing that it’s just so you can do the calculations easily without a calculator.I’m fairly sure it has to do with using pi. If you took the estimate of 10, and did 5ˆ2 * 3(for pi), you get 75. 10ˆ2 is 100. The actual is 6ˆ2 *3.14 which is 113. Obviously if it weresmaller, it would miss by a larger amount, but you can probably deduce that for yourselfand make that judgement.It just feels so counterintuitive to just square the lengths of the cd when we’ve beentaught that the area is pi*rˆ2. Can’t we just multiply by 3 instead of not multiplyingby pi at all?I think that all we’re doing here is assuming that the area of a circle is about thesame as the area of a square with a side length slightly less than the circle’s diam-eter, which makes our lives easy and doesn’t require multiplication by anythingbut 10s.I think simplicity is the sole motivator, which is especially justifiable in estimation – no?Is it alright that in the estimations I would have picked quite different numbers? Forinstance, in estimating sampling rate, I have read that most adults cannot hear frequenciesover 16kHZ so I probably would have estimated 15 instead of 20 kHZ. Is it more importantto have the right numbers or is the emphasis more on being able to explain your reasoning?Given the inherently imperfect nature of estimation, I would imagine logic is more im-portant than actual numbers. Of course, the answer must make some sort of sense to beuseful.Are we supposed to answer the questions on page 6 (problems 1.1 and 1.2)? If so, I donot understand what problem 1.1 is asking, are there any definitions I am missing or amI just not reading it right?You don’t need to formally answer those inline problems (sorry for splitting theinfinitive). They are placed there to help you review ideas in the preceding material.I’ll add more of them as I revise the textbook. I hope that these questions help peopleuse the textbook for self study without an "Art of Approximation" course at theiruniversity (or they may be long graduated and, say, practicing as an engineer).11 1111 112010-02-03 15:16:38 / rev cd07877f087c+1Divide and conquer1.1 Example 1: CDROM design 41.2 Theory 1: Multiple estimates 71.3 Theory 2: Tree representations 101.4 Example 2: Oil imports 131.5 Example 4: The UNIX philosophy 15How can ancient Sumerian history help us solve problems of our time?From Sumerian times, and maybe before, every empire solved a hardproblem – how to maintain dominion over resentful subjects. The obvioussolution, brute force, costs too much: If you spend the riches of the empirejust to retain it, why have an empire? But what if the resentful subjectswould expend their energy fighting one another instead of uniting againsttheir rulers? This strategy was summarized by Machiavelli [19, Book VI]:A Captain ought. . . endeavor with every art to divide the forces of the enemy,either by making him suspicious of his men in whom he trusted, or by givinghim cause that he has to separate his forces, and, because of this, become weaker.[my italics]Or, in imperial application, divide the resentful subjects into tiny tribes,each too small to discomfort the empire.
View Full Document