Due: September 8, 2003 M. Shamos

General homework policies:

You are encouraged to work together to discuss the problems and solve them. However, every paper you turn in must be written completely by you alone. You may not share written work. The purpose of this policy is to ensure that everyone learns the material individually and has a full understanding of his own answers. Copying from others is of no assistance in understanding.

You must list on your homework paper the name of every person you worked with. If you answer includes content from any other source, you must state the source. Failure to do so is cheating and will result in sanctions.

If there is information you need to solve a problem but the information is not stated in the problem, try to find the data somewhere. If you cannot find it, state what data you need, make a reasonable estimate of its value, and justify any assumptions you make. You will be graded not on whether your answer is correct, but whether you have done an intelligent analysis.

Only answer the questions that are asked. Do not answer questions that are not asked, and do not waste your time on side discussions of minor issues. FOCUS. If a short answer (such as yes or no) is called for, you must always explain your answer. Answers that happen to be correct but have no explanation will receive little credit. Answer that happen to be wrong but whose explanations indicate sound reasoning will receive substantial credit. Once you have explained your answer, however, extra material is neither desirable nor helpful. If the answer calls for a number, you must of course explain how you obtained the number.

Grading: Homework will not be re-graded except in cases of “manifest error.” A manifest error is one that is immediately apparent on inspection of the paper. Examples are: a numerical error in adding up the individual question scores, marking an answer wrong when it is fact right, or failing to write in a score for an individual question. Homework answers will not be re-examined subjectively to determine whether a question should have received a different number of points. Grades are important as a measure of your progress. To the extent that grades interfere with the process of learning and understanding, they are harmful.

All homework must be submitted as a Microsoft Word .doc file, by email to jieh@cs.cmu.edu, with a copy to shamos@cs.cmu.edu. Homework is due by 11:59 p.m. on the announced date.

This homework will require you to do some background research. They are typical of the kinds of questions that arise in developing new, global eCommerce business models. The answers cannot be found in the textbook or on the Internet, but require you to think carefully and develop your skills at making intelligent estimates. You will have to make many assumptions in arriving at your answers. Make good assumptions and state them clearly.

Ubiquitous Computing

[100 points total] The idea of ubiquitous (“everywhere”) computing is that chips are so cheap that we can put one in almost every object on Earth. Computers are so cheap we can put one in every wall, car, floor, roof and telephone pole on Earth and in many other places. That way, we can keep track of everything in the world and have objects exchange information with each other all the time. The purpose of this question is to explore the possible uses of ubiquitous computing in eCommerce.

A) [15 points] The IPv6 protocol uses 128-bit IP addresses. This is necessary since we are quickly running out of 32-bit addresses, but some people wonder whether 128 bits will be sufficient. Assume that we might want to give an IP address to every object on Earth that is the size of a grain of sand or larger. A typical grain of sand is a sphere of diameter one millimeter and that the surface of the Earth, including all land and the bottom of the ocean, is covered with grains of sand. Calculate what fraction of the IPv6 address space will be required to give every grain of sand an IP address.

B) [25 points] How many objects on Earth are worth more than one U.S. dollar? (We will call these “valuable objects.” [No one knows the answer to this question. You will be graded on your approach to estimating the number and how reasonable your assumptions are. This is a difficult question that can easily become overwhelming. Hint: do you think you have to count the number of cars and airplanes in the world in arriving at your answer? If you develop a sound approach you will not have to spend a lot of time on this question.]

C) [20 points] Assume that each valuable object reports its position every five minutes some computer over the Internet. Does the present Internet backbone have enough capacity to transmit this much information?

D) [40 points] You are the chief executive officer of a large food manufacturing company. Your eCommerce specialist tells you that it is now possible to put a device in EVERY ONE of the company’s products and this will enable the company to track the location of that product every five minutes from the time it is manufactured until the time its container is destroyed. (In this question we will not deal with any privacy concerns. It will never reveal information about any specific person outside the company.)

List the five BEST uses you would make of this location data to improve the company’s business and explain what benefit you would achieve from each use. “Best” means most improvement in profitability or customer service. Each of your five answers should be limited to four sentences. Think very carefully. “Five best” is not the same as “any five you can think of.”