【正文】 than 1 Mbyte per image. The full database requires some 3035 CDs. (b) Since we needed 3035 CDs before, pressing by a factor of 10 is not sufficient to get the database onto one CD. [Note that if the student picked a smaller format, such as estimating the size of a “typical” gif image, the result might well fit onto a single CD.]  (I saw this problem in John Bentley’s Programming Pearls.) Approach 1: The model is Depth X Width X Flow where Depth and Width are in miles and Flow is in miles/day. The Mississippi river at its mouth is about 1/4 mile wide and 100 feet (1/50 mile) deep, with a flow of around 15 miles/hour = 360 miles/day. Thus, the flow is about 2 cubic miles/day. Approach 2: What goes out must equal what goes in. The model is Area X Rainfall where Area is in square miles and Rainfall is in (linear) miles/day. The Mississipi watershed is about 1000 X 1000 miles, and the average rainfal is about 40 inches/year ≈ .1 inches/day ≈ .000002 miles/day (2 X ). Thus, the flow is about 2 cubic miles/day. Note that the student should NOT be providing answers that look like they were done using a calculator. This is supposed to be an exercise in estimation! The amount of the mortgage is irrelevant, since this is a question about rates. However, to give some numbers to help you visualize the problem, pick a $100,000 mortgage. The upfront charge would be $1,000, and the savings would be 1/4% each payment over the life of the mortgage. The monthly charge will be on the remaining principle, being the highest at first and gradually reducing over time. But, that has little effect for the first few years. At the grossest approximation, you paid 1% to start and will save 1/4% each year, requiring 4 years. To be more precise, 8% of $100,000 is $8,000, while 7 3/4% is $7,750 (for the first year), with a little less interest paid (and therefore saved) in following years. This will require a payback period of slightly over 4 years to save $1000. If the money had been invested, then in 5 years the investment would be worth about $1300 (at 5would be close to 5 1/2 years. Disk drive seek time is somewhere around 10 milliseconds or a little less in 2000. RAM memory requires around 50 nanoseconds – much less than a microsecond. Given that there are about 30 million seconds in a year, a machine capable of executing at 100 MIPS would execute about 3 billion billion (3 . 1018) instructions in a year. Typical books have around 500 pages/inch of thickness, so one million pages requires 2000 inches or 150200 feet of bookshelf. This would be in excess of 50 typical shelves, or 1020 bookshelves. It is within the realm of possibility that an individual home has this many books, but it is rather unusual. A typical page has around 400 words (best way to derive this is to estimate the number of words/line and lines/page), and the book has around 500 pages, so the total is around 200,000 words. 16 Chap. 2 Mathematical Preliminaries An hour has 3600 seconds, so one million seconds is a bit less than 300 hours. A good estimater will notice that 3600 is about 10% greater than 3333, so the actual number of hours is about 10% less than 300, or close to 270. (The real value is just under 278). Of course, this is just over 11 days. Well over 100,000, depending on what you wish to classify as a city or town. The real question is what technique the student uses. (a) The time required is 1 minute for the first mile, then 60/59 minutes for the second mile, and so on until the last mile requires 60/1=60 minutes. The result is the following summation. 60 60 60/i =60 1/i =60H60. i=1 i=1 (b) This is actually quite easy. The man will never reach his destination, since his speed approaches zero as he approaches the end of the journey. 3 Algorithm Analysis Note that nis a positive integer. 5nlog nis most efficient for n=1. 2n is most efficient when 2 ≤ n≤ 4. 10nis most efficient for all n5. 20nand 2n are never more efficient than the other choices. Both log3 nand log2 nwill have value 0 when n=1. Otherwise, 2 is the most efficient expression for all n1. 2/32 3n 2 log3n log2 nn20n 4nn!. (a) n+6 inputs (an additive amount, independent of n). (b) 8ninputs (a multiplicative factor). (c) 64ninputs. 100n. 10n. √ About (actually, 3 100n). n+6. (a) These questions are quite hard. If f(n)=2n = x, then f(2n)=22n = 2(2n)2 = x. (b) The answer is 2(nlog2 3). Extending from part (a), we need some way to make the growth rate even higher. In particular, we seek some way to log2 3 =make the exponent go up by a factor of 3. Note that, if f(n)= n)=2log2 3log2 3 =3xy, then f(2nn. So, we bine this observation with part (a) to get the desired answer. First, we need to find constants cand no such that 1 ≤ c 1 for nn0. This is true for any positive value c1 and any positive value of n0 (since nplays no role in the equation). Next, we need to find constants cand n0 such that 1 ≤ c nfor nn0. This is true for, say, c=1 and n0 =1. 17 18 Chap. 3 Algorithm Analysis Other values for n0 and care possible than what is given here. (a) The upper bound is O(n) for n0 0 and c= c1. The lower bound is Ω(n) for n0 0 and c= c1. (b) The upper bound is O(n3) for n0 c3 and c = c2 +1. The lower bound is Ω(n3) for n0 c3 and c= c2. (c) The upper bound is O(nlog n) for n0 c5 and c= c4 +1. The lower bound is Ω(nlog n) for n0 c5 and c= c4. (d) The upper bound is O(2n) for n0 c7100 and c = c6 + lower bound is Ω(2n) for n0 c7100 and c = c6. (100 is used for convenience to insure that 2n n6) (a) f(n)=Θ(g(n)) since log n2 = 2 log n. (b) f(n) is in Ω(g(n)) since nc grows faster than log nc for any c. (