### COS 109: Problem Set 4

Due 5:00 PM, Tuesday, Oct 17 by submission to drop box at https://dropbox.cs.princeton.edu/COS109_F2017/Problem_Set_4
Answers need not be long, merely clear so we can understand what you have done. Please submit typed material, not hand-written, if at all possible, and keep a copy for yourself just in case something goes astray. Thanks.

 Collaboration policy for COS 109: Working together to really understand the material in problem sets and labs is encouraged, but once you have things figured out, you must part company and compose your written answers independently. That helps you to be sure that you understand the material, and it obviates questions of whether the collaboration was too close. You must list any other class members with whom you collaborated.

#### 1. The Rule of 72

The "Rule of 72" is a very useful rule of thumb for estimating the effects of compounding, where some quantity grows by a fixed percentage in each of a series of identical time periods. The rule of 72 says that if a quantity is compounding at x percent per time period, it will double in approximately 72/x periods.

For example, if gas prices are rising 8% per year, in 72/8 or 9 years a gallon of gas will cost twice as much as it does today. But if prices are only rising 6% per year, doubling will take 72/6 or 12 years. Conversely, if the doubling time is given, you can compute the number of periods by dividing 72 by the rate: if something doubles in 10 years, the rate is 72/10, or about 7% per year. The approximation breaks down if the rate is too high, but it's good enough for typical values. (The web site given above has a good explanation of how it works, and a simple Javascript implementation that you might enjoy looking at. But don't use it to do the calculations below, and don't use your calculator; this problem is about learning to do your own arithmetic in your head.)

(a) Suppose that 25 years from now, you're trying to send your kids to Princeton and you discover that the tuition has quadrupled from what it is now. Approximately what annual rate of tuition increase would that correspond to?

(b) Princeton's rate of return on its endowment investments was about 12% in the fiscal year that just ended. Past performance certainly does not guarantee future results, but if this rate were to continue, roughly what would the value of today's \$22B endowment be 25 years from now? (This assumes that nothing is spent from the endowment, which of course is not true.)

(c) In 1981, I purchased 1 MB of memory for \$4000. Now, 36 years later, I can purchase 32GB of memory for \$20. What has been the percentage drop is cost per year over this period?

(d) An NPR story (10/3/08) states that getting 20% interest for five years doubles your money. Right or wrong, and why?

#### 2. Circuitry

(a) Draw the circuitry in terms of basic gates for D = NOT ((A OR (NOT B)) XOR C)

(b) Show the truth table for "NOT ((A OR (NOT B)) X OR C)"

(c) What function this truth table represent?

#### 3. A state machine

Design a state machine to control a vending machine that converts coins of smaller values into coins of larger values. This machine will have the following characteristics:
• You operate the vending machine by inserting a coin of value 1 or 2 or 3
• When you have inserted coins with a total value of 5, the machine asks if you would like a coin of value 5. If so, the machine returns such a coin. If not, the machine continues to accumulate your coins.
• When you have accumulated coins of value 10 or more, the machine returns a coin of value 10. The machine will then subtract 10 from your balance.

You can think of the state machine as having a string of inputs which consist of coins of value either 1 or 2 or 3.

The states of your machine will want to record the current value of coins in the machine

The transitions in your machine will record changes in the value of coins that have been inserted.

When the value is greater than 5, your machine will expect an input of Y or N telling whetehr to return a coin of value 5. If it is a Y, the coin will be returned and 5 will be subtracted from your accumulated coin total. Your machine will need to record that a coin has been returned and then transition to a state that records the new coin total. This can be done via a transition that writes a charcter symbolizing that a coin has been returned and then proceeds to the new state. This is the only situation where the input can be Y or N rather than 1, 2, or 3.

When the value is 10 or more, a coin of value 10 will automatically be returned and 10 will be subtracted from your accumulated coin total. Your machine will need to record that a coin has been returned and then move to a state where 10 has been subtracted from the current value of coins in the machine. This can be done via a transition that writes a character and then proceeds to the new state.