15-112 F24

Practice Final

Recommended Time: 3 hours

Reminders that will also be true for the Final:

●   You may not use any concepts (including builtin functions) which were not covered during the semester.

●    Read each question carefully, as some questions may restrict what topics you can use to write your solution.

●   You may assume that almost Equal(x, y) and rounded(n) have been supplied for you. You must write all other helper functions that you wish to use.

●   You’re going to do great :)

Please utilize the CS Academy Sandbox tool to test your solutions – especially CTs. If you are unsure how to start a problem or if your solution is correct, feel free to attend OH for help!

There will also be a Practice Final Solution Session where you will be able to see TAs solve the practice midterm and ask any questions that you have! Please check Ed for details.

Note that, like on quizzes and other exams, the test cases provided to you are not exhaustive; you should account for edge cases unless otherwise specified in the problem statement.

True or False

1. .sort() and sorted() both run in O(N^2) time

 True  False

2. All iterative functions can be written recursively

 True  False

3. The following code will cause an MVC violation

def redrawAll(app):

app.color = ‘blue’

drawCircle(100, 100, 40, fill = app.color)

 True  False

Multiple Choice

1. Which of the following is NOT a list method?

 L.index()  L.find()  L.count()  L.append()

2. Converting a list to a set runs in ____

 O(1)  O(log N)  O(N)  O(N^2)

3. Which of the following searching & sorting algorithms has the best efficiency?

 Binary Search  Selection Sort  Merge Sort  Linear Search

CT1:

Indicate what the following code prints. Place your answer (and nothing else) in the box below.

def ct1(L, M):

if len(M) - len(L) <= 2:

return sorted(M)

if (M[0] % 2 == 1):

L.append(M[0])

return [L[0] - M[-1]] + ct1(L, M[1:])

else:

return [L[0] + M[-1]] + ct1(L[2:], M[1:])

print(ct1([], [1, 2, 1, 3, 2]))

CT2:

Indicate what the following code prints. Place your answer (and nothing else) in the box below.

def foo(x):

x + 1

return x - 1

def bar(y):

a = y % 3

print(f"a: {a}")

a += 1

return a

def ct2(x):

print(x + 3)

y = foo(bar(x) + foo(12))

print(f"y: {y}")

print(2 * bar(y))

return y

print("Go!")

ct2(5)

CT3:

Indicate what the following code prints. Place your answer (and nothing else) in the box below.

def ct3(x):

j = c = 0

for i in range(x):

while j < 2 * i:

j += i

c += 1

if (i ** i != j): continue

print(i, j)

return c

print(ct3(3))

CT4:

Indicate what the following code prints. Place your answer (and nothing else) in the box below.

class Point():

def __init__(self, a, b):

self.a = a

self.b = b

def sum(self, other):

return Point(self.a + other.a, self.b + other.b)

def ct4 (a, b):

p1 = Point(a, a * 2)

p2 = Point(b, b - 1)

p3 = p1.sum(p2)

return (p3.a, p3.b)

print(ct4(1, 2))

Free Response 1: nthBalancedPrime(n)

Background: A number is a balanced prime if the following conditions are true:

1.   The number itself is prime, and

2.   It is equal to the average of the nearest prime below it and the nearest prime above it.

For example, 5 is a balanced prime because it is prime and the average of 3 (the nearest prime less than 5) and 7 (the nearest prime greater than 5) is 5.

With this in mind, write the function nthBalanced Prime(n) that takes in a non-negative integer n and returns the nth integer which is a balanced prime.

Here are some test cases:

Free Response 2: Chow Time Animation!

Write an animation that does the following:

1.   Kimchee, a red circle with radius 20, starts at the center of the app and begins moving

towards the user’s mouse. If the user’s mouse is already centered on Kimchee, Kimchee should not be moving. Otherwise, every 0.05 seconds, Kimchee moves one pixel in each direction (x and y) towards the user’s mouse.

2.   Every 2 seconds Mike drops in a piece of food at a random location within the canvas, as represented by a blue circle with radius 10.

3.   There should be no more than 10 pieces of food at any time; if there are 10 pieces in the tank, Mike will wait to drop in any more until Kimchee has eaten one.

4.  A score, drawn in the top right corner of the screen, starts off at zero.

5.   If Kimchee intersects with any part of a ‘food’ circle:

a.   The food should disappear.

b.   The score should increase by 1.

6.   If the ‘r’ key is pressed, all of the food should leave the tank, but Kimchee’s position should not reset. The score should also reset to 0.

7.   app.stepsPerSecond should be set to 20.

Note: You may not assume a specific canvas size. Your solution should be resizable.

Free Response 3: bishopDict(L, color)

Write the function bishopDict(L, color) which takes in a rectangular 2D list L representing a chessboard (of any dimensions), where each cell is guaranteed to be one of the following:

"-" = empty

"b" = black bishop

"w" = white bishop,

as well as a color (either "b" or "w").

This function returns a dictionary mapping each (row, col) where there is a bishop of our specified color to the set of all (row, col) tuples that the bishop can attack. In other words, we map each existing bishop to targetable bishops of the other color.

A bishop can only move diagonally and it cannot move through other pieces. This function should be  non-mutating.

Here is a test case:

L = [["b", "-", "w", "-", "-"],

["-", "b", "-", "-", "-"],

["-", "-", "w", "-", "w"],

["-", "-", "-", "b", "-"],

["-", "-", "-", "-", "-"],

["-", "w", "-", "w", "-"]]

assert(bishopDict(L, "b") == {

(0, 0) : set(),

(1, 1) : {(0, 2), (2, 2)},

(3, 3) : {(2, 2), (2, 4), (5, 1)}})

assert(bishopDict(L, "w") == {

(0, 2) : {(1, 1)},

(2, 2) : {(1, 1), (3, 3)},

(2, 4) : {(3, 3)},

(5, 1) : {(3, 3)},

(5, 3) : set()})

Free Response 4: evensAreSorted(L)

Without using loops or strings, write function evensAreSorted(L) that takes a possibly-empty list  L and returns True if the evens are sorted in strictly increasing order. Odd values are ignored. Lists containing no even values (including an empty list) should also return True.

Note:  Your solution must use recursion. You may not use loops or strings in your solution.

You may not use builtin functions which run in O(N) or worse.

You may not create a new list containing only the even digits.

Here are some test cases:

assert(evensAreSorted([2, 4, 8]) == True)

assert(evensAreSorted([1, 2, 3, 4, 5, 8]) == True)

assert(evensAreSorted([4, 2, 4, 2, 4]) == False)

assert(evensAreSorted([1,2,3,3,2,1]) == False)

assert(evensAreSorted([42, 33, 10, 80]) == False)

assert(evensAreSorted([4]) == True)

assert(evensAreSorted([9]) == True)

assert(evensAreSorted([]) == True)

Free Response 5: kSuperSplit(L, k, n)

Write the function kSuperSplit which takes in a list of positive integers L, a positive integer k,    and a positive integer n, and returns a list of k 1D lists that, when combined, they contain each element of L exactly once, and that the sum of each of each 1D list is at most n.

For example:

L = [1, 5, 1, 1, 2, 3, 4, 5]

k = 3

n = 8

The following is one possible return value for kSuperSplit(L, k, n) given the values above:

L = [ [1, 5, 1, 1],   [3, 5],   [2, 4] ]

The example below has no possible solutions, so kSuperSplit(L, k, n) would return None.

L = [1, 5, 1, 1, 2, 3, 4, 5]

k = 6

n = 4

Here are some test cases:

L = [1, 5, 1, 1, 2, 3, 4, 5]

res = kSuperSplit(L, 3, 8)

assert(res != None)

assert(len(res) == 3)

assert(sorted(res[0] + res[1] + res[2]) == sorted(L))

assert(sum(res[0]) <= 8 and sum(res[1]) <= 8 and sum(res[2]) <= 8)

L = [1, 5, 1, 1, 2, 3, 4, 5]

res = kSuperSplit(L, 4, 6)

assert(res != None)

assert(len(res) == 4)

assert(sorted(res[0] + res[1] + res[2] + res[3]) == sorted(L))

assert(sum(res[0]) <= 6 and sum(res[1]) <= 6 and sum(res[2]) <= 6 and

sum(res[3]) <= 6)

res = kSuperSplit([1, 5, 1, 1, 2, 3, 4, 5], 6, 4)

assert(res == None)

res = kSuperSplit([1, 5, 1, 1, 2, 3, 4, 5], 7, 3)

assert(res == None)

Note: This function must be solved using recursive backtracking! Non-recursive functions may receive zero points, and solutions that do not meet the requirements for backtracking will only be eligible for up to half credit, even if they pass the test cases.