• Unlike other labs and homeworks, this lab will not be autograded.
• Instead, after you are done, you will meet for an hour in a small group of 5 or 6 students and both of your CA's and mutually write and review the solutions (and informally grade each other's work).
• The point of this lab is to be sure you are ready to start hw1, to create an environment where you collaborate with your classmates, and to be sure you know your CA's and are comfortable asking them for help.
• This lab is Pass/Fail, with the intention of everyone passing.  You score "P" (for pass, which does not affect your semester average) if you make serious attempts to solve the entire lab, and in addition you also attend the small group grading session.  Otherwise, you score 0/100 (even if you leave just one problem unattempted, so be sure to try them all!).
• All the work for this lab should be done collaboratively, with other students in the course, preferably in groups of about 4-5.  Form study groups and work together.  If you need help, ask for it.  If you are in the position to offer help, please do so!
• Your non-programming work may be handwritten this week.
• For all programs:  You must use Linux (both directly in the Cluster and, separately, via ssh).  You must use vi and no other editor.  You may not use loops or conditionals (which we've not covered yet).
• Students who are away this weekend with a university-approved absence (such as for athletic events), and only those students, may meet for their grading sessions on Monday.
• The grading sessions will be scheduled as part of this week's recitation, where you will also start working on this lab.

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