Unformatted text preview:

163 163163 1631552010-04-23 17:14:36 / rev 948a7c3d3530+8.2 Why divide and conquer worksHow does divide-and-conquer reasoning (Chapter 1) produce such ac-curate estimates? Alas, this problem is hard to analyze directly becausewe do not know the accuracy in advance. But we can analyze a relatedproblem: how divide-and-conquer reasoning increases our confidence inan estimate or, more precisely, decreases our uncertainty.The telegraphic answer is that it works by subdividing a quantity aboutwhich we know little into several quantities about which we know more.Even if we need many subdivisions before we reach reliable information,the increased certainty outweighs the small penalty for combining manyquantities. To explain that telegraphic answer, let’s analyze in slow motiona short estimation problem using divide-and-conquer done.8.2.1 Area of a sheet of paperThe slow-motion problem is to estimate area of a sheet of A4 paper (A4is the standard sheet size in Europe). On first thought, even looking at asheet I have little idea about its area. On second thought, I know some-thing. For example, the area is more than 1 cm2and less than 105cm2.That wide range makes it hard to be wrong but is also too wide to beuseful. To narrow the range, I’ll drew a small square with an area ofroughly 1 cm2and guess how many squares fit on the sheet: probably atleast a few hundred and at most a few thousand. Turning ‘few’ into 3, Ioffer 300 cm2to 3000 cm2as a plausible range for the area.Now let’s use divide-and-conquer and get a more studied range. Subdi-vide the area into the width and height; about two quantities my knowl-edge is more precise than it is about area itself. The extra precision has ageneral reason and a reason specific to this problem. The general reason isthat we have more experience with lengths than areas: Which is the morefamiliar quantity, your height or your cross-sectional area? Therefore, ourlength estimates are usually more accurate than our area estimates.The reason specific to this problem is that A4 paper is the Europeanequivalent of standard American paper. American paper is known tocomputers and laser printers as ‘letter’ paper and known commonly inthe United States as ‘eight-and-a-half by eleven’ (inches!). In metric units,those dimensions are 21.59 cm × 27.94 cm. If A4 paper were identical toletter paper, I could now compute its exact area. However, A4 paper is, I163 163163 1631552010-04-23 17:14:36 / rev 948a7c3d3530+8.2 Why divide and conquer worksHow does divide-and-conquer reasoning (Chapter 1) produce such ac-curate estimates? Alas, this problem is hard to analyze directly becausewe do not know the accuracy in advance. But we can analyze a relatedproblem: how divide-and-conquer reasoning increases our confidence inan estimate or, more precisely, decreases our uncertainty.The telegraphic answer is that it works by subdividing a quantity aboutwhich we know little into several quantities about which we know more.Even if we need many subdivisions before we reach reliable information,the increased certainty outweighs the small penalty for combining manyquantities. To explain that telegraphic answer, let’s analyze in slow motiona short estimation problem using divide-and-conquer done.8.2.1 Area of a sheet of paperThe slow-motion problem is to estimate area of a sheet of A4 paper (A4is the standard sheet size in Europe). On first thought, even looking at asheet I have little idea about its area. On second thought, I know some-thing. For example, the area is more than 1 cm2and less than 105cm2.That wide range makes it hard to be wrong but is also too wide to beuseful. To narrow the range, I’ll drew a small square with an area ofroughly 1 cm2and guess how many squares fit on the sheet: probably atleast a few hundred and at most a few thousand. Turning ‘few’ into 3, Ioffer 300 cm2to 3000 cm2as a plausible range for the area.Now let’s use divide-and-conquer and get a more studied range. Subdi-vide the area into the width and height; about two quantities my knowl-edge is more precise than it is about area itself. The extra precision has ageneral reason and a reason specific to this problem. The general reason isthat we have more experience with lengths than areas: Which is the morefamiliar quantity, your height or your cross-sectional area? Therefore, ourlength estimates are usually more accurate than our area estimates.The reason specific to this problem is that A4 paper is the Europeanequivalent of standard American paper. American paper is known tocomputers and laser printers as ‘letter’ paper and known commonly inthe United States as ‘eight-and-a-half by eleven’ (inches!). In metric units,those dimensions are 21.59 cm × 27.94 cm. If A4 paper were identical toletter paper, I could now compute its exact area. However, A4 paper is, IComments on page 1 1Comments on page 1Another thought I had was... I do understand that dividing will eliminate errors.. but ifyou think about it... having many steps might exponentially increase the chances of erroras well?It seems like this should have been earlier - maybe right after divide and conquer wasdescribedI agree this section would have helped reaffirm the power of divide and conquer andwould have been helpful earlier in the course. That said, you’d probably have to movethe probability section up with it, which may effect the flow of the course material.Read this section for Monday (memo due Monday at 9am). It applies the probabilitytools to analyze one of the other tools (divide and conquer).It doesn’t seem like something that could be inaccurate – breaking up a big probleminto smaller problems seems like such a classic problem-solving method, how could it bewrong?I agree. Isn’t this the basis of all problem solving techniques? Start with what you knowin order to get to an unknown value?Is there a reason why this section comes way after the introduction of divide-and-conqueris this comparing to the confidence of just throwing a random number out there vs break-ing it down using divide and conquer?i’ve always been kinda puzzled by this. in divide-and-conquer reasoning, we guess morenumbers. if we guess a lot of individual numbers, as is the case for divide and conquer,how does that not decrease our confidence?I think in general, breaking the problem down into many smaller pieces allows us toreduce our overall error. For example, we may have generated a lot more error in thebandwidth over the


View Full Document

MIT 6 055J - Lecture notes

Download Lecture notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?