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" |
|
for x in
xrange(5,10): |
|
for x in
xrange(454, 460, 3): |
|
s = "2 red
foxes and 3 bison" |
|
import copy |
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): |
#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): |
def f(str): |
#4 continued.
def f(a): |
def f(a): |
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?!?")