15-112 Midterm #1 – Fall 2013
(80 minutes)

INSTRUCTIONS

• You may not use any books, notes, or electronic devices during this exam.
• You may not ask questions about the exam except for language clarifications

1.       [10 pts; 1 pt each] True or False (circle one):

a.    TRUE or FALSE:  For all integers x, ((x|-1) <= x) is True.

b.   TRUE or FALSE: In 2’s Complement, we define -x to be ~x, which is the complement of x in base 2.

c.    TRUE or FALSE: Polya did not write How To Solve It as a Computer Science text, but more of a general-purpose guide to problem solving.

d.   TRUE or FALSE: Given some c > 1, if f(N) runs in O(c**N) time and g(N) runs in O(N**c) time, then for large enough N, there is no limit to how many times longer it might take to run f(N) than g(N).

e.   TRUE or FALSE: Python’s builtin sort is considerably faster than any sort we might write in Python mainly because it uses an especially clever sorting algorithm

f.     TRUE or FALSE:  If each of a and b refer to 1d lists of integers, and whenever we change a[0] we see that b[0] also changes, then a and b must be aliases.

g.    TRUE or FALSE:  Destructive functions never return values except None.

h.   TRUE or FALSE: If an expression contains K distinct boolean variables, then the truth table for that expression must contain 2K rows (not including the row of labels at the top).

i.      TRUE or FALSE:  Tuples and strings are immutable, but all other types are mutable.

j.     TRUE or FALSE:  In a bitwise version of DeMorgan’s Law, the expression (x&y == ~(~x|~y)) is True for all integer values x and y.

2.       [30 pts; 3 pts each] Very Short Answers:
Answer each of the following with only a few words or numbers (or a function, where appropriate).  Longer answers will be incorrect.

a.What is the big-o runtime of this function:

    def f(n):
       for x in range(0, n, 42):
           y = n
           while (y > 0):
               y /= 42
               print (x,y)

b.   What is the big-o runtime of this function:

    def g(a):
      n = len(a)
      for x in xrange(0, n, len(str(n))):
          a[x%n] += 5
          a.sort()
          if (a[0] == 5): print "amazing!"
 

c.    Circle all the expressions that are equal to (x&1) for all integer values of x:

x%2    (x<<4)/16      x-((x>>1)<<1)    int(bin(x)[-1])    x&(-1)&1

d.   The following function is supposed to take a string that is a boolean expression using the variables x and y, and print a truth table for that expression.  The function actually works just fine, but has very poor style.  List 3 distinct style rules that this code violates, and clearly indicate where it does so:

def bs(e):

    print "x   y   ",e

    b1 = 0

    b2 = 0

    while (b1+b2 < 3):

        for b2 in [False, True]:

            print("%d   %d    %d" % (b1,b2,eval(e.replace("x",

            str(True*b1)).replace("y",str(b2)))))

        b1 += 1
 

e.   Briefly explain how you can use timing information to verify whether or not a given function f(N), for positive int values N, runs in O(N**42) time.

f.     List all the non-negative numbers that have the same representation in binary (base 2) as decimal (base 10).

g.    Say we have variables cx, cy, r, and hour.  Write a few lines of Python that draws an hour hand from the center (cx, cy) with radius r at the appropriate angle for the given hour.  Also assume canvas is defined.

h.   Very concisely prove that mergesort runs in O(NlogN) time.

i.      Say you have a function f(n) that takes an integer value n and returns the nearest prime number to n, or if there are two such numbers, returns both in a list (smaller first).  If n is not an integer, the function should not crash but instead return None.  Do not write this function!  Instead, write a test function for this function that conforms to our test function conventions, and that includes 5 of the important edge cases and does not include unnecessary extra tests.

j.     In just a few words, explain why "\" is not a valid string in Python.
 

3.       [15 pts; 3 pts each] Indicate what each will print or draw (assume a 400x400 canvas):
For graphics output, do not explain the output in words, but simply draw the resulting canvas.

4.  [10 pts; 4 pts for f1, 3 pts each for f2 and f3] Reasoning about code
For each of the functions, find values of the parameters so the function will return True.  Circle your answers.

def f1(x, y):
    return ((100>x>y>0) and
            (x+y == 20) and
            (x>>y == 2))

def f2(s, t):
    result = ""
    assert(len(t) == 4)
    for i in xrange(len(s)):
        result += t[i]*i if (i == int(s[i])) else str(int(s[i])+i)
    return (result == "9x7yyy")

def f3(a):
    b = [ "b" ]
    c = [ ]
    for i in xrange(len(a)):
        if (a[i] == i):
            b += ["*"]
        elif (a[i]%(i+1) == 0):
            b.append(a[i] + i/10.0)
        else:
            c.extend([i, a[i]])
    # note: don't worry about approximate values of floats
    return (c+b == [3, 5, 'b', 6.0, 8.1, '*'])
 

5.       [20 pts]  Free Response:  partiallyMergesorted
Note: there is another free response after this!
Background:  given a list of N values (where we assume N is some power of 2), when mergesort first starts, after 0 passes, we have N sub-lists of size 1 that are all sorted by default.  After 1 pass, we have N/2 lists of size 2 that are all sorted.  And so on.  Since even an unsorted list is “partially sorted with 0 passes”, we can think of any list as being partially sorted by mergesort.  With this in mind, write the function  partiallyMergesorted(a, passes) that takes a list a of length N (which is a power of 2) and a non-negative integer number of passes, and returns True if the list could be partially sorted by mergesort after the given number of passes.

For example:

    partiallyMergesorted ([4,2,1,3], 0) returns True
    partiallyMergesorted ([4,2,1,3], 1) returns False

    partiallyMergesorted ([2,4,1,3], 0) returns True
    partiallyMergesorted ([2,4,1,3], 1) returns True
    partiallyMergesorted ([2,4,1,3], 2) returns False

Note that you should not implement mergesort here!  Also, carefully the 5 given examples to understand the problem (Polya step 1!).
 

6.       [15 pts]  Free Response:  encode
Background:  similar to a homework exercise, here we will consider a simple encoding scheme where we encode a string as a single integer.  First, we start with the integer 42.  Then, we ignore all the non-letters in the string, and convert the letters to uppercase.  Then for each letter, we find the distance of that letter to “A”, and encode that distance as a two-digit number appended to the right side of the result.  So if the first letter is “B”, we append the digits 01 to the result, which then is 4201.  If the second letter is “Z”, we append the digits 25 to the result, which is then 420125.  So encode("BZ") returns the integer (and not the string!) 420125, as does encode("   B?!?!?  z!!!   ").  Similarly, decode(420125) returns "BZ".  With this in mind, write the function encode(s) that works as described.  Note that you do not have to write decode.
 

7.  Bonus/Optional:  [2.5 pts] Write an equivalent function to f(n) that does not use any loops or recursion.
def f(n): return sum([(x-(x|-1))**2 - (x+(x^~x))**2 for x in xrange(n+1)])

Bonus/Optional:  [2.5 pts]  In a few words of plain English, what does the following anonymous (unnamed) lambda function compute?
lambda n: (lambda f: f((f, n))) (lambda ((f, a)):
                                 1 if a <= 1 else a * f((f, a - 1)))