1. Reasoning About Code [30 pts; 2.5 pts each]
For each of the following functions, find values of
the parameters so that the functions will return True. You should assume
that x, y, and z are ints, and that s is a string. Hint: reason your
way through this. How you find your answer is just as
important, if not more so, than what the answer is! While you may
confirm your answer by running it in a Python interpreter, do not use the
Python interpreter at all when solving the problem. You will be given
similar problems such as these on written quizzes without access to Python
interpreters! Also, consider only the possible inputs. For example, if you
are given that x+y==16, since x>y>0, we only need consider (15,1), (14,2),
..., (9,7). That's only 7 (x,y) points in total, one of which must be
correct! Also, CIRCLE YOUR ANSWERS!
import string
def f1(s):
assert((type(s) == str) and (len(s) == 5))
i = 0
for j in xrange(len(string.ascii_lowercase)):
if (j % len(s) == 0):
assert(s[i] == string.ascii_lowercase[j])
i += 1
if (i == len(s)):
return True
return False
import copy
def f2(a):
assert(sorted(a) == range(5,9))
b = copy.copy(a)
for i in xrange(len(b)):
b[len(b)-1-i] *= i
return ((b[0] == 18) and (min(a) == b[2]) and (a[1] > a[3]))
def f3(x, y):
return ((100>x>y>0) and
(y == 1 << (x/10)) and
((y<<(x/10)) + x == 100))
def f4(s):
assert(type(s) == str)
t = "CBBD"
for i in xrange(4):
assert(s.count(s[i]) ==
(ord(t[i]) - ord("A")))
return (s[::3] == s[5:2:-1])
def f5(y):
x = 28
while (x > 0):
c = 0
for z in xrange(1,x+1):
if (x % z == 0):
c += 1
if (c == 2):
return (x == y)
x -= 1
return (2*y == -y)
def f6(n):
assert(type(n) == int)
m = 1
for x in xrange(10*1000):
r = 1
for c in str(x):
r *= (ord(c) - ord("5"))
if (r == 6):
m = x
return (n == m)
def f7(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 f8(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 f9(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 f10(s,t):
return (t[2] == str(len(t))) and (s[1:len(s)] == t[4:0:-1])
def f11(a):
assert(len(a) == 8)
s = 0
for i in xrange(0, 8, 2):
assert(a[i] > s)
s += a[i]
assert(str(s) == a[i+1])
return True
def f12(a):
b = sorted(a)
assert(b == range(len(a)))
i = a.index(b[1])
return (b[1:6:2] == a[i:i+3])
2. True or False (circle one): [10 pts; 1 pt each]
a. TRUE or FALSE: For any non-negative integers x and y, (x|y) >= max(x,y).
b. TRUE or FALSE: For any integers x and y and z, if (x > y) is True, then ((x % z) > (y % z)) is True.
c. TRUE or FALSE: In general, for loops run faster than while loops.
d. TRUE or FALSE: We would expect fasterIsPrime(N**2) to run in about the same time as isPrime(N).
e. TRUE or FALSE: If we changed mergesort so that instead of merging halves of the list, it merged thirds of the list, this would not change the big-oh runtime, which would still be O(NlogN).
f. TRUE or FALSE: Polya’s “How to Solve It” explains how to use math, mainly algebra, to solve a variety of problems, and serves as our basis for our big-oh theory of run-time analysis.
g. TRUE or FALSE: Selectionsort can be faster than mergesort in some cases.
h. TRUE or FALSE: In Eck’s xSortLab simulator, a bar turns black when it is about to be swapped.
i. TRUE or FALSE: When we create a string and then no longer use it, the string becomes garbage, and Python automatically detects this situation and reuses the memory that the string used.
j. TRUE or FALSE: The Google Python Style Guide is similar to but distinct from the Official PEP-8 Python Style Guide written by Guido van Rossum.
3. Very Short Answers [10 pts; 2 pts each]
Answer each of the following with only a few words or numbers. Longer
answers will be incorrect.
a.
Using different-height bars for values (as in
xSortLab), sketch what a list with 8 elements would probably look like if we are
halfway done sorting using mergesort (as it works in xSortLab).
b. Assuming f(s,t)
takes two non-empty strings, rewrite the following function so that it works the
same way only it does not use a loop or recursion.
def f(s,t):
for i in xrange(len(t)):
if (t[i] != s[i%len(s)]): return False
return (len(t) % len(s) == 0)
c.
On a certain computer, running binary search on a
random sorted list with 1 thousand elements takes 2 milliseconds. About how
long would you expect the same computer to run binary search on a random sorted
list with 1 billion elements?
d.
Assuming n is a positive integer, what is the big-oh
runtime of each of these functions:
def fa(n):
count = 0
for x in xrange(len(str(n))):
for y in xrange(n, n/2, -3):
count += 1
return count
def fb(n):
count = 0
for x in xrange(1, n*100000, n*0.00001):
count += 1
return count
def fc(n):
rows = n
cols = n*n
count = 0
for row in xrange(rows):
for col in xrange(cols):
count += 1
count += 1
return count
def fd(n):
x,y,count1,count2 = n,1,0,0
while (x > 1): (x,count1) = (x/5,1+count1)
while (y < n): (y,count2) = (count1+y,1+count2)
return count2
e. In just a few words, explain what short-circuit evaluation is in Python.
carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem