15-112 Spring 2012 Quiz 5

* 20 Minutes.  No calculators, no notes, no books, no computers.

1.       [50  pts, 10 pts each]  For each of the following functions f, find values of the parameters so that f will return True.  Circle your answers.

def f1(n,k,x):
    s = "ab\tc\\d"
    assert(len(s) == n)
    assert(s[k] in string.whitespace)
    assert(s.find("b") == s.find("e") + x)
    return True

def f2(fmt):
    # string formatting, you supply the format string!
    s1 = fmt % (2, 3.56)
    assert (s1 == "+2abc3.6")
    s2 = fmt % (-2, 3.4)
    assert (s2 == "-2abc3.4")
    return True

def f3(s):
    assert (s[0] == "d" and len(s) == 5)
    for i in xrange(1, len(s)):
        if (ord(s[i]) != (i + ord(s[i-1]))):
            return False
    return True

def f4(s,t):
    return (t[2] == str(len(t))) and (s[1:len(s)] == t[4:0:-1])

def f5(s):
    assert("-" not in s)
    t = ""
    ok = False
    try:
        try:
            for i in xrange(len(s)):
                t += str(int(s[i]))
                t += "-"
        except:
            for i in xrange(2,-2,-1):
                t += str(2/i)
    except:
        ok = (t == "3-4-12")
    return ok
 

2.  [50 pts]  Write didWin1 from our TicTacToe example.  You may use any helper functions we wrote without writing them here.

 

3.  Bonus/optional: [ 5pts]:  What is the worst-case big-oh runtime of f (assuming n>0, ignore crashes):
def f(n):
    x = 0
    for i in xrange((len("%d" % n) - len("%x" % n)) * (len("%o" % n))):
        m = 0
        while m*m<n: (m,x) = (m+42,x+1)
    return x