15-112 Fall 2013 Quiz 4
* Note that there were 2 very similar
versions of this quiz. Each is included here.
15-112 Fall 2013 Quiz 4
* 20 Minutes. No calculators, no notes, no books, no computers. * Show your
work. Circle your answers.
1. Quick Answers. [50 pts; 5 pts each] Be very brief.
a. List all integers x and y where (((x|y) ^ (y|x)) > 0).
b. Assuming x is an integer, find an equivalent expression to (x ^ (-1)) without using bitwise operators.
c. Binary and decimal:
i. True or False: For any integer k>=0, the binary representation of 2**k contains exactly one 1.
ii. Convert the number 23 from decimal to binary.
iii. What is the smallest integer that can be represented in 4-bit two’s complement?
d.
Below each algorithm (as we discussed in class), write its Big-O runtime:
a) mergesort b) selectionsort c) binary search d) linear
search e) fasterIsPrime f) isPrime
O( ) O( ) O(
) O( ) O( )
O( )
e. Say the list (5, 7, 1, 8, 2, 4, 6, 3) is being sorted with mergesort. Write the partially-sorted list just before the start of the final pass (just before the last merge).
f. Sort the list (6, 8, 2, 7) using selectionsort, as implemented in xSortLab, by writing the list after each swap.
g. In just a few words, what leads to logN being part of the proof that mergesort is O(NlogN)?
h. Say we have variables cx, cy, r, and hour. Write a few lines of Python that draws an hour hand from the center (cx, cy) with radius r at the appropriate angle for the given hour. Also assume canvas is defined.
i. Say we used our own customSort, which (for suitably large lists), broke the list into 256 smaller lists, sorted each of those with selectionsort, and then merged each of the 256 sorted lists repeatedly (basically using mergesort on those lists).
i. What is the big-o of the first half of customSort: selectionsort over the 256 smaller lists?
ii. What is the big-o of the second half of customSort: mergesort over the 256 sorted lists?
iii. What is the big-o of customSort?
j. More big-o:
a. Given a function f where the runtime of f(2n) is the square of the runtime of f(n). What is O(f(n))?
b. Given a function f where the runtime of f(2n) is one hour longer than the runtime of f(n). What is O(f(n))?
2. Code Tracing [25 pts] Indicate what this will print:
(x, y) = (0b10110, 17>>2)
print "a:",x
print "b:",y
print "c:",~x
print "d:",(x&11)<<y
print "e:",x^y, bin(x^y)
3. Big-O [25 pts] For each of the following functions, indicate the big-O worst-case runtime:
def r1(n):
for x in xrange(0, 2**n, 2**n/n**2):
print "This may print a lot!"
def r2(n):
s = "Yippee!" * n
for x in xrange(len(bin(n))):
c = chr(ord('a') + x%26)
print s.count(c)
def r3(n):
x = y = 0 # hint: note that this is outside both loops!
while (x < n):
while (y < n):
print "y",
y += 3
print "x",
x += 4
def r4(n):
for x in xrange(n):
for y in xrange(-n, n):
for z in xrange(100):
print (x,y,z),
for x in xrange(n):
print "huzzah!",
def r5(n):
step = int(round(n**0.5))
for x in xrange(123, n**2, step):
print "Go team!",
4.
Bonus/Optional: [5 pts] What will the following print?
Show your work!
def b(x):
def c(d):
for c in xrange(5*d+x):
d &= d-1
if (not d): return -~c
while (c(c(max(x,1))) < 3): x += 1
return x
print b(0), c(b(0))
15-112 Fall 2013 Quiz 4
* 20 Minutes. No calculators, no notes, no books, no computers. * Show your
work. Circle your answers.
1. Quick Answers. [50 pts; 3 pts each] Be very brief.
a.
Below each algorithm (as we discussed in class), write its Big-O runtime:
a) mergesort b) selectionsort c) binary search d) linear
search e) fasterIsPrime f) isPrime
O( ) O( ) O(
) O( ) O( )
O( )
b. Say the list (2, 4, 6, 3, 5, 7, 1, 8) is being sorted with mergesort. Write the partially-sorted list just before the start of the final pass (just before the last merge).
c. Sort the list (6, 2, 8, 7) using selectionsort, as implemented in xSortLab, by writing the list after each swap.
d. Binary and decimal:
i. Convert the number 21 from decimal to binary.
ii. True or False: For any integer k>=0, the binary representation of 2**k contains exactly one 1.
iii. What is the smallest integer that can be represented in 3-bit two’s complement?
e. Assuming x is an integer, find an equivalent expression to (x ^ (-1)) without using bitwise operators.
f. In just a few words, what leads to logN being part of the proof that mergesort is O(NlogN)?
g. Say we have variables cx, cy, r, and hour. Write a few lines of Python that draws an hour hand from the center (cx, cy) with radius r at the appropriate angle for the given hour. Also assume canvas is defined.
h. Say we used our own customSort, which (for suitably large lists), broke the list into 256 smaller lists, sorted each of those with selectionsort, and then merged each of the 256 sorted lists repeatedly (basically using mergesort on those lists).
i. What is the big-o of the first half of customSort: selectionsort over the 256 smaller lists?
ii. What is the big-o of the second half of customSort: mergesort over the 256 sorted lists?
iii. What is the big-o of customSort?
i. More big-o:
a. Given a function f where the runtime of f(2n) is the square of the runtime of f(n). What is O(f(n))?
b. Given a function f where the runtime of f(2n) is one hour longer than the runtime of f(n). What is O(f(n))?
j.
List all integers x and y where
(((x|y) ^ (y|x)) > 0).
2. Code Tracing [25 pts] Indicate what this will print:
(x, y) = (0b10110, 21>>2)
print "a:",x
print "b:",y
print "c:",~x
print "d:",(x&11)<<y
print "e:",x^y, bin(x^y)
3. Big-O [25 pts] For each of the following functions, indicate the big-O worst-case runtime:
def r1(n):
x = y = 0 # hint: note that this is outside both loops!
while (x < n):
while (y < n):
print "y",
y += 3
print "x",
x += 4
def r2(n):
for x in xrange(0, 2**n, 2**n/n**2):
print "This may print a lot!"
def r3(n):
for x in xrange(n):
for y in xrange(-n, n):
for z in xrange(100):
print (x,y,z),
for x in xrange(n):
print "huzzah!",
def r4(n):
s = "Yippee!" * n
for x in xrange(len(bin(n))):
c = chr(ord('a') + x%26)
print s.count(c)
def r5(n):
step = int(round(n**0.5))
for x in xrange(123, n**2, step):
print "Go team!",
4.
Bonus/Optional: [5 pts] What will the following print?
Show your work!
def b(x):
def c(d):
for c in xrange(5*d+x):
d &= d-1
if (not d): return -~c
while (c(c(max(x,1))) < 3): x += 1
return x
print b(0), c(b(0))