ICS 1F, Homework 1 Solutions

  1. List three things you think computers can now do better than you, and three things you think you can do better than computers.

    My answer: Computers can play chess, perform arithmetic, and predict weather better than I can. I can speak English, make new mathematical discoveries, and program computers better than computers can.

  2. Is there a (whole number) value of x that would cause an infinite loop in the procedure described below? Explain why or why not. (Hint: Try it with a few small numbers to see what happens.)

        Read a number x.
    Initialize a counter to zero.

    While x is greater than zero, perform the following steps:

        Increase the counter by one.
        If x is odd, replace x by (x+1)/2;
        otherwise (if x is even) replace x by x-2.

    Once the loop terminates (if it does),
    output the value of the counter and halt.
    Answer: If x=1, then (x+1)/2 is also 1, so the program goes into an infinite loop.

  3. In the imaginary country of Binaria, the currency is based on the centina, which is worth approximately the same as a penny. The coins of Binaria have values that are powers of two: 1, 2, 4, 8, 16, 32, and 64 centinas.

    (a) What coins should you use to make change for the following amounts of money? (In each case answer with the smallest possible set of coins that adds up to the correct value.)

    1. 15 centinas
    2. 29 centinas
    3. 39 centinas
    4. 108 centinas
    Answers:
    1. 1, 2, 4, and 8 centinas.
    2. 1, 4, 8, and 16 centinas.
    3. 1, 2, 4, and 32 centinas.
    4. 4, 8, 32, and 64 centinas.

    (b) Why might it be useful for Binarian cash registers to display amounts of money using binary notation?

    Answer: Because the 1's in the binary representation of a number would tell you exactly which coins to use to make change. E.g. for 29 centinas, the binary representation of 29 is 11101. The rightmost 1 tells you to use a 1-centina coin, the zero means you don't need any 2-centina coins, the second one from the right tells you to use a 4-centina coin, etc.