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(x*2) + g(x*3)
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 N2.  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)