Computer Science 15-112, Spring 2012
Class Notes:  Practice (through week 1)


Read these instructions first!
  1. Code Tracing
    Briefly explain why each line produces the output that it does.  Show your work, and be precise.

    print 3 ** (2 << 1) / 5
    print ((3 | 4) / 2 * 1.0) / 2
    print (64 >> ( 7 ^ 3) ) ** 3

    print 1|2|4|8|16|32|64  # your answer should work for this series ending in any power of 2, not just 64
    print 1+1|2|4|8|16|32|64 # and why when we add 1 do we get a smaller number?

    x = 53
    y = x << 1
    y |= x
    x ^= y
    print x, y

    print (1/2**4) or ((1/2)**4) or (float(1/2)**4) or ((float(1)/2)**4) or float(1/2**4)

     
  2. Short Answers.
    Show your work, even for True/False, and be precise.
    1. If you type the expression 2+2 into the python interpreter, it prints 4.  But if you type 2+2 as the only text in the file foo.py, then run python foo.py, it seems like nothing happened (in particular, the 4 is not printed).  What, precisely, is going on?
    2. When you run a script in python, you can include the -i flag, like this:  python -i foo.py
      Try it out and discuss the meaning of the -i flag, and why it might be useful.
    3. TRUE or FALSE: Any binary number that ends in a 1 must be odd.  Remember to show your work!
    4. TRUE or FALSE: Any binary number that contains exactly one 1 must be a power of 2.
    5. TRUE or FALSE: If x and y are positive integers where x < y, then (x / y) will always equal zero and (x % y) will always equal x.
    6. Use algebra to show that (x % y) is equal to (x - (x/y)*y) as long as y is not zero.
      Hint: x/y is integer division, so it truncates.
      Hint: Express x as some multiple of y plus some remainder that is less than y. That is, x = ky + r, where 0 <= r < y.
      Question: does it matter whether or not x or y is positive?
    7. In Java and many other programming languages, (-3 % 5) is -3.  In Python, (-3 % 5) is 2.  Explain why Python's semantics are more consistent.  You may want to draw a graph of (x % 5) in each case.  Be sure to use both positive and negative values for x.
    8. At the end of lecture, I showed a "trick" using bitwise-xor (^):  say you have a list of numbers (int's, to be more precise), where each number occurs an even number of times, except one number occurs an odd number of times.  The numbers are not in any specific order.  So you bitwise-xor all the numbers together.  The result will be that special number that occurred an odd number of times.  For example, consider this list:
         6, 3, 5, 6, 3, 7, 3, 7, 6, 3, 5
      It contains four 3's, two 5's, three 6's, and two 7's.  Now, consider this expression:
         6^3^5^6^3^7^3^7^6^3^5
      This evaluates to 6, which indeed is the right answer.  Explain why this "trick" with bitwise-xor works regardless of the order of the list.  Be precise.
       
  3. Base conversions
    Show your work!
    1. Convert 143 from base 10 to base 2.
    2. Convert 01001011 from base 2 to base 10.
       
  4. Logic and Truth Tables
    For booleans x and y, write an expression equivalent to (x and (not y)) that does not use the and operator.  Using truth tables, prove that your answer is correct.
     
  5. Mystery Functions
    In just a few words of plain English, what does each of the following functions do?  Provide some explanation for your answer.
    1. def f(x,y):
          epsilon = 0.0000001
          d1 = abs(x)**2
          d2 = abs(y)**0.5
          return abs(d1 - d2) < epsilon

       
    2. def g(x):
          return (type(x) == int) and (x/10 == x%10)

       
    3. def h(x):
          return (type(x) == int) and (x >= 0) and ((int(round(x**0.5)))**2 == x)

       
  6. Review examples from class notes
    1. onesDigit
    2. tensDigit
    3. eggCartons
    4. militaryTimeToStandardTime
       
  7. Write functions
    1. fabricYards
      Fabric must be purchased in whole yards.  Write a function that takes the number of inches of fabric desired, and returns the smallest number of whole yards of fabric that must be purchased.

      def fabricYards(inches):
          return 42

      def testFabricYards():
          print "Testing fabricYards... ",
          assert(fabricYards(0) == 0)
          assert(fabricYards(1) == 1)
          assert(fabricYards(35) == 1)
          assert(fabricYards(36) == 1)
          assert(fabricYards(37) == 2)
          assert(fabricYards(72) == 2)
          assert(fabricYards(73) == 3)
          assert(fabricYards(108) == 3)
          assert(fabricYards(109) == 4)
          assert(fabricYards(-12345) == 0)
          print "Passed all tests!"
             
      testFabricYards()

       
    2. fabricExcess
      Write a function that takes the number of inches of fabric desired and returns the number of inches of excess fabric that must be purchased (as purchases must be in whole yards).
      Hint: you may want to use fabricYards, which you just wrote!

      def fabricExcess(inches):
          return 42

      def testFabricExcess():
          print "Testing fabricExcess... ",
          assert(fabricExcess(0) == 0)
          assert(fabricExcess(1) == 35)
          assert(fabricExcess(35) == 1)
          assert(fabricExcess(36) == 0)
          assert(fabricExcess(37) == 35)
          assert(fabricExcess(72) == 0)
          assert(fabricExcess(73) == 35)
          assert(fabricExcess(108) == 0)
          assert(fabricExcess(109) == 35)
          assert(fabricExcess(-12345) == 0)
          print "Passed all tests!"
             
      testFabricExcess()

       
    3. dayOfWeek
      Write a function that takes a date represented by three integers, the month (1-12), the day (1-31), and the year, and returns an integer representing the day-of-week for that date, where Sunday is 1, Monday is 2, and so on, and Saturday is 7.

      While there are several ways to do this, you must use this formula (from the most-excellent web site mathforum.org):
            N = d + 2m + [3(m+1)/5] + y + [y/4] - [y/100] + [y/400] + 2
      Then the remainder when you divide N by 7 is the day-of-week, where Saturday is 0 and Friday is 6.  Note that these values for the days are not quite the same as those returned by this method.

      Here is mathforum's description of the formula:
          "d is the number or the day of the month, m is the number
           of the month, and y is the year. The brackets around the
           divisions mean to drop the remainder and just use the
           integer part that you get.
           Also, a VERY IMPORTANT RULE is the number to use for the
           months for January and February. The numbers of these months
           are 13 and 14 of the PREVIOUS YEAR. This means that to find
           the day of the week of New Year's Day [of 1998], 1/1/98,
           you must use the date 13/1/97."

      Note: you must make the adjustment to the month and year when appropriate.  So, for example, the date of New Year's Day for 1998 would be obtained in the natural way:  dayOfWeek(1, 1, 1998).  You may ignore the cases where the month, day, or year are out of bounds.

      def testDayOfWeek():
          print "Testing dayOfWeek... ",
          # On 2/5/2006, the Steelers won Super Bowl XL on a Sunday!
          assert(dayOfWeek(2, 5, 2006) == 1)
          # On 6/15/1215, the Magna Carta was signed on a Monday!
          assert(dayOfWeek(6, 15, 1215) == 2)
          # On 3/11/1952, the author Douglas Adams was born on a Tuesday!
          assert(dayOfWeek(3, 11, 1952) == 3)
          # on 4/12/1961, Yuri Gagarin became the first man in space, on a Wednesday!
          assert(dayOfWeek(4, 12, 1961) == 4)
          # On 7/4/1776, the Declaration of Independence was signed on a Thursday!
          assert(dayOfWeek(7, 4, 1776) == 5)
          # on 1/2/1920, Isaac Asimov was born on a Friday!
          assert(dayOfWeek(1, 2, 1920) == 6)
          # on 10/11/1975, Saturday Night Live debuted on a Saturday (of course)!
          assert(dayOfWeek(10, 11, 1975) == 7)
          print "Passed all tests!"

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem