Computer Science 15-112,
Spring 2012
Class Notes: Practice (through week 1)
Read these
instructions first!
- This material is not to be submitted. It is just for practice.
- For all programs in this lab (even though they are not to be submitted): You
should use Linux (both directly in the
Cluster and, separately, via ssh). You should use vi and no other editor.
You may not use loops or conditionals (which we've not covered yet).
- 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)
- Short Answers.
Show your work, even for True/False, and be precise.
- 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?
- 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.
- TRUE or FALSE: Any binary number that ends in a 1 must be odd.
Remember to show your work!
- TRUE or FALSE: Any binary number that contains exactly one 1 must be a power
of 2.
- 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.
- 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?
- 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.
- 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.
- Base conversions
Show your work!
- Convert 143 from base 10 to base 2.
- Convert 01001011 from base 2 to base 10.
- 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.
- Mystery Functions
In just a few words of plain English, what does each of the following functions
do? Provide some explanation for your answer.
- def f(x,y):
epsilon = 0.0000001
d1 = abs(x)**2
d2 = abs(y)**0.5
return abs(d1 - d2) < epsilon
- def g(x):
return (type(x) == int) and (x/10 == x%10)
- def h(x):
return (type(x) == int) and (x >= 0) and ((int(round(x**0.5)))**2 == x)
- Review examples from class notes
- onesDigit
- tensDigit
- eggCartons
- militaryTimeToStandardTime
- Write functions
- 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()
- 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()
- 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