CS 111: Final Exam Extra Practice Solutions
Question #1
Part A
do no to
Part B
17 15 7 7.5
Part C
32 5 42 43 7 12
Here is a table for part C:
range(3, 5) [3, 4]
|———–|————-|———–|———–|
|i |range(2,i)|j | output | |———–|————-|———–|———–|
|3 |[2] |2 |32 |
| | | none left | 5 | exit inner loop, print(i+j) | 4 | [2, 3] | 2 | 4 2 | |||3|43|
| | | none left | 7 | exit inner loop, print(i+j)
| none left | |
Part D
10 0 73
Here are some tables for part D:
global foo |———–| |———–| |a|b||a|b| |—–|—–| |—–|—–| |7|3||3|7| | | ||4|6| | | ||5|5| | | ||6|4| | | ||7|3| | | ||8|2| | | ||9|1| | | ||10|0|
|12| exit outer loop, print(i*j)
Notes:
1) Thefunctioncallisfoo(b,a),andthus:
foo’s a gets a copy of the global b foo’s b gets a copy of the global a
2) There are two different sets of variables — one in the global scope, and one belonging to foo, and any changes that foo makes to its variables do not change the variables in the global scope.
Question #2
Part A
def is_prime(n):
for i in range(2, n):
if n % i == 0:
return False
return True
Part B
def add_primes(lst):
if len(lst) == 0:
return 0
else:
# could also reduce range in various ways
sum_rest = add_primes(lst[1: ])
if is_prime(lst[0]):
return lst[0] + sum_rest
else:
return sum_rest
If we hadn’t required recursion, you could also have used a list comprehension here:
def add_primes(lst):
lc=[xforxinlstifis_prime(x)] #getallprimes! return sum(lc)
Question #3
15 times:
fib(0) and fib(1) are single calls
fib(2) == fib(1) + fib(0), means fib(2) creates 3 total calls (1 + 1 + the original call to fib(2)) fib(3) == fib(2) + fib(1), means fib(3) creates 5 total calls (3 + 1 + the original call to fib(3)) fib(4) == fib(3) + fib(2), means fib(4) creates 9 total calls (5 + 3 + the original call to fib(4)) fib(5) == fib(4) + fib(3), means fib(5) creates 15 total calls (9 + 5 + the original call to fib(5))
Question #4
def uniquify(lst):
if len(lst) == 0:
return []
else:
rest = uniquify(lst[1:])
if lst[0] in lst[1:]:
return rest
else:
return [lst[0]] + rest
Question #5
def merge(list1, list2):
if list1 == []:
return list2
elif list2 == []:
return list1
else:
if list1[0] < list2[0]:
return [list1[0]] + merge(list1[1:], list2)
else:
return [list2[0]] + merge(list1, list2[1:])
Question #6
Part A
This program calculates how many factors between 1 and n (inclusive) the input number has.
After lines 7, 8 and 9, r3 will only be 0 if r1 was evenly divisible by r2 (i.e., if r1 % r2 == 0), and this will cause us to increment r9, which is the count of the number of factors.
For example, let's trace through an input of 6:
line executed 00 read r1 01 setnr90 02copyr2r1 03 nop
04 nop
05 nop
06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 11 addnr91 12 addn r2 -1 13 jumpn 06
06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 12 addn r2 -1 13 jumpn 06
06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 12 addn r2 -1 13 jumpn 06
r1r2r3r9
6 60 66 0
#r2!=0,sodon'tjump
6610 6660 6600 #r3==0,sodon'tjump 6601 6501
# unconditional jump to line 6
#r2!=0,sodon'tjump
6511 6551 6511 #r3>0,sojumptoline12 6411
# unconditional jump to line 6
#r2!=0,sodon’tjump
6411 6441 6421 #r3>0,sojumptoline12 6321
# unconditional jump to line 6
line executed 06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 11 addnr91 12 addn r2 -1 13 jumpn 06
06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 11 addnr91 12 addn r2 -1 13 jumpn 06
06 jeqz r2 14 07divr3r1r2 08mulr3r2r3 09subr3r1r3 10 jgtz r3 12 11 addnr91 12 addn r2 -1 13 jumpn 06
06 jeqz r2 14
14 write r9
15 halt
Part B
14 setn r4 2
15 sub r9 r9 r4
16 jeqz r9 19
17 write 1
18 jumpn 20
19 write 0
20 halt
r1 r2 r3 r9
# r2 != 0, so don’t jump
6321 6361 6301
# r3 == 0, so don’t jump 6302 6202
# unconditional jump to line 6
# r2 != 0, so don’t jump
6232 6262 6202
# r3 == 0, so don’t jump 6203 6103
# unconditional jump to line 6
# r2 != 0, so don’t jump
6163 6163 6103
# r3 == 0, so don’t jump 6104 6004
# unconditional jump to line 6
# r2 == 0, so jump to line 14
# write 4 for the 4 factors (6,3,2,1)
# subtract 2 from the number of factors
# if get 0, there were only 2 factors, so prime
# if not 0, there were > 2, so write 1 (composite)
# could also have a halt here
# write 0 (prime)
Question #7
Part A
x3 x2 x1 x0 | is_prime 0000 0 0001 0 0010 1 0011 1 0100 0 0101 1 0110 0 0111 1 1000 0 1001 0 1010 0 1011 1 1100 0 1101 1 1110 0 1111 0
Part B
Each row of the truth table that has an output of 1 gets an AND gate, and those AND gates are then ORed together to produce the final output:
Question #8
# loop-based approach
def symmetric(grid):
for r in range(len(grid)):
for c in range(len(grid[r])):
if grid[r][c] != grid[c][r]:
return True
return False
# recursive approach (optional)
def symmetric(grid):
if len(grid) <= 1: # first base case
return True
top_row = grid[0]
left_col = [ grid[r][0] for r in range(len(grid)) ]
if top_row != left_col: # second base case
return False
rest_of_grid = [ grid[r][1:] for r in range(1, len(grid)) ]
return symmetric(rest_of_grid)
Question #9
def max(self, other):
minrows = min(self.nrows, other.nrows)
mincols = min(self.ncols, other.ncols)
maxmat = Matrix(minrows, mincols)
for r in range(minrows):
for c in range(mincols):
maxmat.data[r][c] = max(self.data[r][c], other.data[r][c])
return maxmat
Question #10