15-112 Fall 2012 Quiz 1

* 20 Minutes.  No calculators, no notes, no books, no computers.  SHOW YOUR WORK, CIRCLE YOUR ANSWERS.

1.       [50 pts; 10 pts each] Short Answers.

a.       For any integer value x, what does (~x + x) equal?  Remember:  always show your work!

b.      Prove any version of DeMorgan’s Law using truth tables.

c.       Convert 101 from binary to decimal

d.      Convert 101 from decimal to binary

e.      For positive int values x, y, and z, if (z%x == y), what is the largest possible value of y in terms of x and z?
 

2.  [30 pts; 10 pts each]  Indicate what each will print.  SHOW YOUR WORK.  CIRCLE YOUR ANSWERS.

def f1(x,y):
    z = (x<<(y/2))
    z ^= y**(x>>1)
    return x|z
print f1(5, 0b11)

---------------------------------------------------------------------------

def f2(x,y):
    print x/y, y/x, (x/y or y/x or 42)
f2(5, 23)

---------------------------------------------------------------------------

x = 5  # global!
def f3(y,z):
    x = y+z
    y **= z
    print x, y, z,
f3(2,3)
print x

3.       [20  pts, 10 pts each]  For each of the following functions f, find a pair of int values (x,y), where 100>x>y>0, such that f(x,y) will return True.  Hint:  reason your way through this.  Consider only the possible inputs.  For example, if you are given that x+y==16, since x>y>0, we only need consider (15,1), (14,2), ..., (9,7).  That's only 7 (x,y) points in total, one of which must be correct!  Also, CIRCLE YOUR ANSWERS!

def f(x, y):
    z = 10+x*y
    # note: almostEqual is as defined in the class notes
    return (100>x>y>0) and (x-y<10) and almostEqual(z%(z-5),z**0.5)

---------------------------------------------------------------------

def f(x, y):
    return (100>x>y>0) and (x&y == 0) and (x|y == 15) and (x>>1 == y)

4.       Bonus/Optional [5 pts].  Once again, find a pair of int values such that f(x,y) will return True.

def f(x, y):
    z = x-y
    return (100>x>y>0) and (z**(y-z) == ((x<<2)-x-z))