15-112 Fall 2012 Midterm 1 (80 minutes)

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

a. TRUE or FALSE: For any positive integers x and y, if ((x&y) == (x|y)) is True, then (x^y == 0) is True.

b. TRUE or FALSE: For any positive integers x and y, if ((x%y) == (x>>y)) is True, then (x == y) is True.

c. TRUE or FALSE: Any list of N integers, where they are all between 1 and 5, can be sorted in O(N) time.

d. TRUE or FALSE: If f(N) runs in O(N**2) time and g(N) runs in O(N**3) time, then f(N) is always faster than g(N) for all positive integers N.

e. TRUE or FALSE: Polya’s “How to Solve It” was originally written with Fortran examples but recently was updated to use Python examples.

f. TRUE or FALSE: For a 1d List L that only contains int values, copy.copy(L) is effectively the same as copy.deepcopy(L).

g. TRUE or FALSE: Lists cannot be added to sets, but sets can be added to lists.

h. TRUE or FALSE: Circles are drawn in Tkinter using create_oval and not create_circle.

i. TRUE or FALSE: In Tkinter it is generally easy to center text on some location but relatively harder to right-align text to some location.

j. TRUE or FALSE: Magic numbers are not allowed in 15-112’s style guide, but this is a simplification for novice programmers, and experts are generally encouraged to use them liberally in their code.

2. [15 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. Very briefly give one clear reason why f(s) is not a very good hash function for strings:
def f(s): return sum([ord(c) for c in s])

b. Say that f(A) is a destructive function that takes a 1d list A. Write the function g(A) that does the same thing as f(A) but is non-destructive. You will want to call f(A) somewhere in g(A).

c. 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**3) time.

d.Assuming n>0, what is the big-oh runtime of f(n):    [Hint: it is not O(1).]
def f(n):
   (s, count) = (set(), 0)
   for c in str(n):
       if (c not in s): count += 1
       s.add(c)
   return count

e. Given the tuple T containing an odd number of int values, write a single expression, not a statement, that computes the median value in T. For half credit, if you do not know the difference between an expression and a statement (or for any other reason), you may write a function instead.

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.

Statement(s):	Prints:
t = "tt\\tt\tt" print len(t), t.find("\t"), t[1:4]
def f(s): (u,i) = ([],-1) while True: i += 1 if (i >= len(s)): break elif (i % 3 == 0): continue if (s[i] == s[(i+4)%len(s)]): u += [i] return u print f("dog-done")
def f(L): result = [ ] for i in xrange(len(L)): for val in L[i]: if (i%3 == 0): result.append(val%3) elif (val%3 == 0): result.append(i) return result print f([[2, 4, 6],[5, 6, 7],[7, 8, 9]])
def f(g,x): return g(x2) + g(x3) a = [1,4] print f(len,a), f(sum,a)
(x1,y1) = (200,0) for x in xrange(50,500,200): for y in xrange(x, 400, 150): canvas.create_line(x,y,x1,y1) canvas.create_text(x,y,text=str((x,y))) (x1,y1) = (x,y)

4. [30 pts; 6 pts each] Reasoning about code
For each of the functions f, find values of the parameters so that f will return True. Circle your answers.

def f(x, y):
    return ((100>x>y>0) and
            (x|y == 31) and
            (x-y == 3) and
            (x^y == 3))

def f(t):
return ((len(t) == 5) and
(t[1:3] == t[-1:-3:-1]) and
(len(set(t)) == 3))

def f(L):
    assert(sorted(L) == range(6))
    ok = 0
    for i in xrange(1,len(L)):
        if (L[i]%2 != ok):
            if (ok == 1):
                return False
            ok = 1
    return True

def f(L):
    count = 0
    for val in L:
        if (type(val) != str):
            count += 1
            c = chr(ord("a")+val)
            if ((val < 0) or
                (val >= len(L)) or
                (L[val] != c)):
                return False
    return (count == 3)

def f(L):
    (rows,cols) = (len(L), len(L[0]))
    assert((rows == 2) and (cols == 4))
    i = 0
    for col in xrange(cols):
        for row in xrange(rows):
            assert(L[row][cols-1-col] == i)
            i += 1
    return True

5.       [30 pts] Free Response: isKingsTour
Background: in Chess, a King can move from any square to any adjacent square. A King’s Tour is a series of legal King moves so that every square is visited exactly once. We can represent a Kings Tour in a 2d list where the numbers represent the order the squares are visited, going from 1 to N². For example, consider these 2d lists:
   [ [ 3, 2, 1 ],        [ [ 1, 2, 3 ],      [ [ 3, 2, 1 ],
     [ 6, 4, 9 ],          [ 7, 4, 8 ],        [ 6, 4, 0 ],
     [ 5, 7, 8 ] ]         [ 6, 5, 9 ] ]       [ 5, 7, 8 ] ]
The first is a legal Kings Tour but the second is not, because there is no way to legally move from the 7 to the 8, and the third is not, because it contains a 0 which is out of range. With this in mind, write the function isKingsTour(board) that takes a 2d list of integers, which you may assume is NxN for some N>0, and returns True if it represents a legal Kings Tour and False otherwise.

Bonus/Optional: [2.5 pts] In just a few words of plain English, for what values of n does f(n) return True in general?

def f(n):
    assert((type(n) == int) and (n > 1))
    c = d = 2
    while (n > 1):
        if (n%d == 0):
            c += 1
            while (n%d == 0): n/=d
        d += 1
    return (c == 4)

Bonus/Optional: [2.5 pts] What will this print?

def map(f,a): return [f(v) for v in a]
def f(g):
    def h(x): return x+g(x)
    return h
def i(x): return x**2
def j(x): return map(f(i),range(x))
print j(5)