15-111 Fall 2011 Midterm 1   (80 minutes)

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

a.    TRUE or FALSE:  For any integers x and y, ~(x&y) == (~x|~y).

b.   TRUE or FALSE:  For any integers x and y, x^y > max(x,y).

c.    TRUE or FALSE:  Nested loops always run in O(N**2).

d.   TRUE or FALSE:  Destructive list methods like a.sort create new lists, but non-destructive functions like sorted(a) do not.

e.   TRUE or FALSE:  Mergesort is O(NlogN), and selectionsort is O(N**2), but this alone does not guarantee that mergesort will be faster than selectionsort in all cases.

f.     TRUE or FALSE:  FasterIsPrime runs in O(N**0.5) which is faster than O(N) but slower than O(logN).

g.    TRUE or FALSE:  Contracts may be used to ensure the correct types of parameters and return values.

h.   TRUE or FALSE:  To work correctly, binary search requires that a list is sorted.

i.      TRUE or FALSE:  For a rectangular 2d list L, len(L[0]) is the number of rows in L.

j.     TRUE or FALSE:  2d lists in Python are really 1d lists containing 1d lists as elements.

2.       [15 pts; 3 pts each] Very Short Answers:
Answer each of the following with only a few words or numbers.  Longer answers will be incorrect.

a.    Partway through sorting a list of random numbers, you notice that the first half of the list is sorted, and the second half of the list is also sorted.  What sorting algorithm do you suppose is running?

 

b.   Write an assert that checks that the non-ragged 3d list a is cubic (same-sized in all 3 dimensions).

 

c.    On a certain computer, running selectionsort on a random list with 1 million elements takes 2 seconds.  About how long would you expect the same computer to selectionsort a random list with 3 million elements?

d.   What is the big-oh runtime of the following function:
def f(n):
    count = 0
    while (n > 0):
        count += 1
        n /= 10
    return count

e.   When an exception occurs, Python often prints a stack trace that is full of useful information.  List 3 different pieces of information available in a stack trace.


 

3.      [15 pts; 3 pts each] Indicate what each will print:

Statement(s):

Prints:

s = "ab\\c\"d"
print s[2:], s[3:5], s[-2]

 

for x in xrange(5,10):
    for y in xrange(5,x):
        if ((x+y)%4 == 1):
            print x,y,

 

for x in xrange(454, 460, 3):
    print "%d %0.2f" % (x, 0.001*x)

 

 

s = "2 red foxes and 3 bison"
t = ""
x = ord("a")
for word in s.split():
    try:
        t += str(int(word))
    except:
        t += chr(x)
        x += 1
print t

 

import copy
def f(a):
    b = copy.copy(a)
    a.sort()
    result = []
    for (x,y) in zip(a,b):
        if (x == y):
            result += [x]
    return result
a = [4,2,3,1]
b = f(a)
print a,b

 

 

4.       [20 pts; 4 pts each] Reasoning about code
In these exercises, you should provide the arguments that cause the function to return the specified value.  In most cases, there are many valid answers.  You only need to provide one of them.

 

def f(x,y):
    assert((x>3) and (y%x > 0))
    result = 0
    for z in xrange(y):
        if (z%x == 0):
            result += 1
    return result

# provide values of x and y
# where f(x,y) returns 5



 


 

#4 continued.  Reasoning About Code
In these exercises, you should provide the arguments that cause the function to return the specified value.  In most cases, there are many valid answers.  You only need to provide one of them.

 

def f(a):
    rows = len(a)
    cols = len(a[0])
    result = []
    row = 0
    for col in xrange(cols):
        if (col >= rows):
            result += [a[row][col]]
            row += 1
    return result

# provide a value of a
# where f(a) returns [2,5]

 

def f(str):
    result = 0
    for c in str:
        try:
            result += int(c)
        except:
            result += 1000
    return result

# provide a value of str
# where f(str) returns 2011








 


#4 continued.

 

def f(a):
    s = set()
    d = dict()
    for i in range(len(a)):
        if (i%2 == 0):
            if (a[i] in d):
                s.add(a[i+1])
            else:
                d[a[i]] = a[i+1]
    return (sorted(s), d[42])

# private a value of a
# where f(a) returns ([4,5],6)










 

def f(a):
    count = 0
    (oldx, oldy, oldz) = (1,1,1)
    for (x,y,z) in a:
        if ((x != oldy) or (y != oldz)):
            return 42
        elif (x+y != z):
            return -42
        else:
            (oldx, oldy, oldz) = (x,y,z)
            count += 1
    return count

# provide a value of a
# where f(a) returns 3


 

 

5.       [15 pts]  Free Response:  nthPerfect
A number is “perfect” if it equals the sum of its factors (not including itself).  For example, 6 is the first perfect number, because the factors of 6 are 1, 2, and 3, and 6 = 1+2+3.  Similarly, 28 is the next perfect number, because 28 = 1+2+4+7+14.  Write the function nthPerfect(n), which returns the nth perfect number, so that nthPerfect(0) returns 6, nthPerfect(1) returns 28, and so on.  You are not responsible for malformed input.


 

6.       [25 pts]  Free Response:  bestQuiz
Write the function bestQuiz(a), which takes a rectangular 2d list of numbers that represents a gradebook, where each column represents a quiz, and each row represents a student, and each value represents that student’s score on that quiz (except -1 indicates the student did not take the quiz).  For example:
  a = [ [ 88,  80, 91 ], [ 68, 100, -1 ] ]
This list indicates that student0 scored 88 on quiz0, 80 on quiz1, and 91 on quiz2.  Also, student1 scored 68 on quiz0, 100 on quiz1, and did not take quiz2.  The function returns the quiz with the highest average.  In this case, quiz0 average is 78, quiz1 average is 90, and quiz2 average is 91 (since we ignore the -1).  Thus, quiz2 is the best, and so the function returns 2 in this case.  You are not responsible for malformed input, except you should return None if there are no quizzes.  Also, resolve ties in favor of the lower quiz number.


7.  Bonus/Optional

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

def f(n):
    assert(isinstance(n,int) and (n>1))
    product = 1
    for i in xrange(2,n):
        j = 1
        while (j < n):
            j *= i
        product *= (n % j)
    return (product == 0)

 

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

def f(s):
    return ("".join([s[max(i,1):i+3]
                   for i in xrange(0,len(s),7)])
              .replace("?",""))
print f("shun pizza pie?!?")