1. It's Growing Exponentially! (a) From the Wall Street Journal (5/6/09), in a story about Vint Cerf: "Some other online pioneers argued for 128 bits [to store Internet addresses], but they lost out. `I couldn't imagine arguing that we needed 340 trillion trillion addresses to carry out an experiment,' Mr. Cerf says." (i) What is the number of possible 128-bit addresses? (An expression is fine.) (ii) What is the relationship between that number and "340 trillion trillion"? (i) 2 ^ 128 (1 point) (ii) 2^128 = 340 * 10^36. Cerf was misquoted; it should have been "340 trillion trillion trillion". (2 points) * -1 point if there is an error in calculations * no point for answers without quantitative reasoning (b) In 2004, ICANN announced that the first IPv6 addresses were added to the root servers. The press release said that IPv6 provided "trillions more addresses" than IPv4. Approximately how many trillions is that? 2^128 / 2^32 = 2^96. 2^96 / 10^12 ~ 80 * 10^15 trillions, or "eighty thousand trillion trillions" or the like. or 2^128 - 2^32 ~ 2^128, 2^128 / 10^12 = "340 trillion trillion" more (2 points) * -1 point if there is an error in calculations * no point for answers without quantitative reasoning (c) In this Foxtrot cartoon, if Paige agrees to the math teacher's proposal, how much total work (approximately!) would she be signing up for? 2 ^ 37. the amount of work in the 36th week is 2^36, and all the previous weeks add up to another 2^36. 2^37-1 is more correct; either is fine. (2 points) * full credit for 2^36, 2^36-1, 2^37, 2^37-1 * -1 point for 2^35 * no point for approximated answer without reasoning (e.g. about 2000 years) (d) The image below comes from a short-lived Wendy's advertisement. (i) List all the positive integer pairs of x and y for which xy is 256. (ii) Assuming the options are things like "do you want cheese?", what's the most likely number of options that a customer is offered? (i) 2 ^ 8, 4 ^ 4, 16 ^ 2, 256 ^ 1. don't forget the last one. (2 points) * -1 point if they miss one of above (or add one more which is not an answer) * no point if they miss more than two (ii) 8 options is likely, since 2^8 is 256 (1 point) * full credit for "4 options with 4 choices" (e) An article in Physical Review Letters, published several years earlier but noted on Slashdot on 10/13/09, says that there really is an absolute limit to Moore's Law. Simplifying the numbers a bit, it says that there is still a factor of 10^15 to be had from repeated doublings of capacity by making things smaller. If the doubling time is the usual 18 months, in how many years will Moore's Law finally run out? 10^15 is about 2^50, so 50 doublings. at 1.5 years each, that's 75 years. (2 points) * -1 point if student gets 50 doublings but made a mistake in multiplying 1.5 years (f) A report from UC Berkeley entitled How Much Information 2003 estimates that in the year 2002 "the human species stored about five exabytes of new information on paper, film, optical or magnetic media, a number that has doubled in the past three years." The next names in the SI (Système International d'Unités) series tera, peta, exa are zetta and yotta. (i) If data accumulation does double every three years and if it did amount to 5 EB in 2002, in what year will the annual amount stored be 5 zettabytes? doubles every 3 years, so a factor of 1000 is 30 years: 2032 (2 points) * -1 point if there is an error in calculations (ii) In what year will it be 5 yottabytes? another factor of 1000, so 2062 (2 points) * -1 point if there is an error in calculations (g) At some point the SI series will have to be extended on beyond yotta. Suggest names for the next couple of units. The names can't begin with letters already used: KMGTPEZY. [There's no credit for this question, but we will award some useless prize for the best answer. The decision of the judges is not only final, but capricious and arbitrary. You must be present in class to win.] 2. Faster than a speeding bullet (a) A story in the New York Times on 11/21/11 says that Microsoft sells "a copy of Office 2010 every second -- over 100 million so far." Microsoft's Office division revenue is nearly $6 billion per year. Using these facts, (i) Very roughly, how long has Office 2010 been on sale? 100M / 31.6M is about 3 years, or 3 years & 2 months. (2 points) * -1 point if there is an error in calculations (ii) About how much does one copy of Office 2010 cost? (2 points) $6B / 31M = about $200 * full credit even if the answer is wrong (because of the wrong answer of (a)(i)), if calculations are correct. * -1 point if there is an error in calculations * -1 point for $6B/100M = about $60 (b) CBS Evening News said last year that at $1 per second, it would take 425,000 years to pay off the US national debt. Is this number too high, too low, or roughly right? (The story is at least a year old, so the operative word is "roughly".) about right; the debt is noticeably higher now. (2 points) * -1 point if there is an error in calculations (c) The November 2011 issue of Scientific American says that "the world's most powerful supercomputer, the K from Fujitsu, computes four times faster and holds 10 times as much data" as the human brain. (Scary thought?) The numbers (somewhat rounded from the article) are 30 TB and 10 Pflops for the computer and 3 TB and 2 Pflops for the brain. The good news is that the brain is a lot more energy efficient: 20 watts instead of 10 GW. What is the power consumption per Tflop of the computer and of the brain? computer is 10 * 10^9 watts / 10000 Tflops or about 10^6 watts/Tflop. person is 20 watts / 2000 Tflops, or .01 watts/Tflop (2 points) * 1 point for the each number. Error in calculations not allowed * -1 point if the unit of the final answer is not (power consumption) / Tflops but Pflops * no point if student calculates Tflops / (power consumption) [bwk note: i transcribed the data wrong from scientific american; it should have been 10 MW for the computer.] 3. Key Rings One major problem with secret-key cryptographic systems like DES and AES is key distribution -- how to send a secret key to the other people you want to talk to. This question concerns a second major problem -- the proliferation of keys if various information is to be shared among different independent combinations of people. (a) Suppose that Alice, Bob and Carol have a relationship in which each person wishes to encrypt their own personal information (for which each needs an individual key) and also carry on private conversations with each other person (i.e., Alice and Bob want to talk without including Carol, and Alice and Carol want to talk without Bob, and so on), and also talk among all three so that outsiders can't understand those conversations either. How many different secret keys do they need in total? List the keys by the people who will share them. 7: a b c (group 1) ab bc ac (group 2) abc (group 3) (2 points) * -1 point if student misses one group of keys. (b) Suppose that David joins the group, and relationships are even more complicated: they need keys for every individual and every possible combination of private conversations among subgroups (e.g., Alice, Carol and David want to be able to talk among themselves while excluding Bob) as well as excluding outsiders. How many different secret keys are now needed? List the keys by the people who will share them. 15: a b c d (group 1) ab ac ad bc bd cd (group 2) abc abd acd bcd (group 3) abcd (group 4) (2 points) * -1 point if student misses one group of keys. (c) As the group grows, more and more keys will be needed. Give a general formula or way to express how the number of keys varies as a function of N, the number of people involved. If you don't see a formula, then give the numbers you have computed, for 1 through 6 people. 2^N - 1 (2 points) * 1 point if students presents complete correct sequence up to 6 people, but no formula * 1 point if the sequence is wrong (including the answers for (a) and (b)) but the formula fits for the sequence