15-112 Fall 2012 Homework 1
Due Sunday, 2-Sep, at 10pm

Read these instructions first!
  1. Practice Thru Week1
    Do all the practice-thru-week1 problems (except #4, the "Additional Practice", which is optional).  Have fun!

    Note:
      one of those problems talks about a "trick" with xor that we did not discuss in class after all.  So here it is:  say you have a large list of integer values, and while the list is unsorted, you happen to know that every number in the list occurs an even number of times (maybe twice, maybe 4 times, maybe 32 times, whatever).  Ok, it's unlikely, but go with it.  Now, you randomly select one of the numbers in the list and randomly add one more of that number to the list in a random location.  Then you give the list to someone else, who has to quickly determine which number occurs an odd number of times.  What do they do?  They could sort the list, which would make the problem easy (of course), but it takes too long.  So instead, they just xor all the numbers together, and voila, out pops the answer!!!  The question is:  why does this work?
     
  2. A Few More...
    Do these, too...
    1. and with nor
      Assume that Python had a function called "nor" where nor(A,B) returned True when both A and B are False, and False otherwise (when either or both of A or B is True).  Thus, nor(A,B) is the same as (not (A or B)).  With this in mind, write the function AND(A,B) (in all caps because you cannot have a function named "and") that returns True when both A and B are True.  Of course, you could just return (A and B), except you are not allowed to use any functions or operators except nor, which you can and should use repeatedly.  Write your answer in a Python file, and also write a test function that verifies that it works correctly (by comparing its behavior to (A and B) for all 4 possible combinations of boolean values for A and B).  Hint:  to test your function, you will have to implement "nor", since Python does not, but that's easy, right?  Another hint:  use DeMorgan's Law, then reduce "not" and "or" to nor.  Have fun!
       
    2. getInRange
      Write the function getInRange which takes 3 values (which you may assume are all numeric) -- x, bound1, and bound2, where bound1 is not necessarily less than bound2. If x is between the two bounds, just return it unmodified.  Otherwise, if x is less than the lower bound, return the lower bound, or if x is greater than the upper bound, return the upper bound.
      For example:
          getInRange(1, 3, 5) returns 3 (the lower bound, since 1 lies to the left of the range [3,5])
          getInRange(4, 3, 5) returns 4 (the original value, since 4 is in the range [3,5])
          getInRange(6, 3, 5) returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
          getInRange(6, 5, 3) also returns 5 (the upper bound, since 6 lies to the right of the range [3,5])
       
    3. encodeRGBA
      Background:  computer programs often store colors using their red, green, blue, and alpha (transparency) components.  These are often stored in a single 32-bit integer, where each successive 8-bit portion of the 32-bit number represents each of red (most-significant), green, blue, and alpha (least-significant) in order.  So, for example, consider the rgba value 0x40ff0080 (which is hex for the decimal value 1090453632).  This single number represents a color with some red (0x40, or 64, with a max of 255, so about 1/4th intensity), full-on green (0xff, or 255, which is full intensity), no blue at all (0x00, or 0, so none), and an alpha transparency of 0x80 (or 128, or about half-transparent).

      With this in mind, write the function encodeRgba that takes 4 values representing the red, green, blue, and alpha portions of an rgba value. You may assume those values are int's, but you may not assume they are in the right range. Use the getInRange function you just wrote to adjust each value as needed to be in the range [0,255] (inclusive). Then, use bitwise operators as needed to encode a single 32-bit int value with these 4 8-bit values, with red on the top, then green, then blue, and finally alpha at the bottom. Finally, return that int value.  For example:
          encodeRgba(0x12, 0x34, 0x56, 0x78) returns 0x12345678
          encodeRgba(1234,-1234, 1234,-1234) returns 0xff00ff00
       
    4. sameGreen
      Write the function sameGreen that takes 2 RGBA values (as just described) and returns True if they have the same amount of green in them, and False otherwise.
       
  3. Write Practice Quiz1 Problems
    Your group should create a document (which must be in .doc or .docx format) containing around 10 practice problems (2 problems from each group member), similar in difficulty to those in the practice-thru-week1 notes, to help prepare for Quiz1 (which we will take on Tuesday).  These problems will not be helpful if they are either too easy or too hard, nor if they are just obvious duplicates of each other or of the existing practice problems.  At the end of the document, also include sample solutions to the problems.  You might wish to focus on portions of the lecture notes that are not covered as much by the existing practice problems, but that's just a suggestion.  At the grading session, email your final version of this document to your CA.  We will gather up all these practice problems and distribute all of them back to all of you!
     
  4. Meet your CA
    The grading session is important not just for grading, but to get to know your CA's a bit.  So do not miss these!  And have fun!

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