Information Technology Reference
In-Depth Information
In the fable that opened this chapter, suppose Paul would
serve a microsecond as ruler of the kingdom rather than take
a kernel of corn. Thus, Paul's payment would be as follows:
Paul would rule one microsecond for the first square of a
chess board.
Paul would rule two microseconds for the second square.
Paul would rule four microseconds for the third square.
Paul would rule eight microseconds for the fourth square.
This pattern would continue, with successive doubling for
each square, until payment was made for each square of a
chess board.
Estimate how long Paul's reign would last using this pay
ment system.
4.
Figure 6.1 gives the costs charged for flying between several
midwestern cities.
a.
Find the least expensive routing that allows someone to go
to all of these cities exactly once before returning home.
b.
Suppose some additional air links were added to Figure 6.1
so that direct flights were possible between any two cities
listed. (Make up some fares that seem reasonable for these
new flights.) Now find the leastexpensive routing covering
each city once, and prove that your answer is the cheapest
solution.
c.
Compare your approaches to finding the solution in parts
a and b. Did you use some special properties of the graph
in part a that you could not use in part b?
d.
Discuss how your solution to part b might be simplified if
you could organize a team of people to help find the least
expensive route.
