Some Review Practice Problems (variables, expressions, loops, conditionals, strings)
1d-List and Tuple Problems
Do not use recursion
Make all your functions non-destructive unless explicitly indicated otherwise.
10. 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!
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]))
# Hint: (a << b) is the same as (a * (2**b))
# and: (a >> b) is the same as (a / (2**b))
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])
11. True or False:
[10 pts; 1 pt each; 11a is bonus]
Be sure to include a very brief explanation as to WHY it is True or
False.
a. (bonus) 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.
12. 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.
Bonus/Optional: subsetSum
Write the function subsetSum(a) that takes a list of int values and returns
a list of indexes i0, i1, ..., ik, in increasing order, such that a[i0] + a[i1]
+ ... + a[ik] equals 0. If no such list exists, return None. For
example, subsetSum([2,5,-13,-6,4,3]) could return [0,3,4] since a[0]+a[3]+a[4]
== 2+-6+4 == 0. There may be more than one valid answer for any given
list, in which case your function may return any one of them. To solve
this, you will want to use the technique we discussed in class: if n=len(a),
iterate a counter from 0 to 2n, then each of these values of the
counter corresponds to a unique subset in the powerset of a, where element a[i]
is in the subset if the ith bit of the counter is set to 1.
Bonus/Optional Graphics: Read this
carefully! The following problems are
bonus/optional. They are graphical, and you should be certain to place
them (and any helper functions they require) below the #ignore_rest line in your
hw6.py submission. Unlike the autograded problems, the bonus graphics problems will be graded only in person on
Monday or Tuesday night at office hours. To get your bonus graphics grade, go to
office hours where you should download your submitted code (and it must be just
as submitted, with no modifications), run it and show the CA the result.
The CA will grade your bonus at that time, mainly visually but also by looking
at the code as needed.
Bonus/Optional: Radial and Spiral Tilings
[2 pts]
Write a function that draws either
this picture or
this picture from
this page on Radial and Spiral Tilings.
Bonus/Optional: Logarithmic Spiral Tilings
[3 pts]
Write a function that draws any one of
this picture or
this picture or
this picture from
this page on Logarithmic Spiral Tilings.
carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem - carpe diem