15-112 Fall 2012 Homework 1
Due Sunday, 2-Sep, at
10pm
Read these
instructions first!
- Unlike other homeworks, this lab will not be autograded.
- Instead, you will first be assigned to groups in recitation, and then you
will finish these problems working as a group.
- Then, after you are done, you will meet for an hour in a small group of 5
or 6 students and at least 2 of your 3 recitation CA's and review the solutions
(and informally grade each other's work).
- The point of this lab is to get you started with the (soon-to-be-harder!)
material, 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!). This is
the first and last time that you can pass based solely on effort!
- All the work for this lab should be done collaboratively, with other
students in your assigned group. Plan to spend at least 4 hours with your
group before Sunday night. Also, if you
need help, ask for it. If you are in the position to offer help, please do
so!
- You will not submit anything this week -- instead, the CA's will review and
grade your materials (pass/fail) right on the spot at the grading session. Your non-programming work may be handwritten this week.
And your code should be printed out or available on your laptop at the grading
session rather than electronically submitted this week.
- For all programs: 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 (which will mostly occur on Sunday) will be scheduled
during this week's recitation,
where you will also start working on this lab.
- 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?
- A Few More...
Do these, too...
- 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!
- 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])
- 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
- 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.
- 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!
- 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