## Lab Exam 2 Practice Problems

#### Recursion

1. Write a function f1(list) that returns the sum of the elements in the list.
>>> f1([1,2,3,4])
10
>>> f1([])
0

def f1(list):
if list == []:
return 0
return list[0] + f1(list[1:])


2. Consider the following function:

$f(n) = \begin{cases} n//2 & \text{if n is even} \\ 3n+1 & \text{if n is odd} \\ \end{cases}$

Write a function f2(n) that returns the number of steps of the function $f(n)$ until it reaches 1 (this is also known as the Collatz Conjecture). For example, consider $f(6): 6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$, since there are a total of 9 steps, f2(6) evaluates to 9.
>>> f2(1)
1
>>> f2(6)
9
>>> f2(11)
15
>>> f2(637228127)
276

def f2(n):
if n == 1:
return 1
if n % 2 == 0:
return 1 + f2(n//2)
else:
return 1 + f2(3*n+1)


3. Write a function f3(list) that prints out the elements in the list in reverse order.
>>> f3([1,2,3])
3
2
1
>>> f3([])
>>> f3([3,2,1])
1
2
3

def f3(list):
if list == []:
return
f3(list[1:])
print(list[0])


4. Write a function f4(list) that multiplies all of the odd elements in the list by 3 and prints out each tripled element.
>>> f4([1,2,3,4])
3
9
>>> f4([2,4])
>>> f4([11,42,63,15])
33
189
45

def f4(list):
if list == []:
return
if list[0] % 2 == 1:
print(3*list[0])
f4(list[1:])


5. Write a function f5(list) that multiplies all of the odd elements in the list by 3 and prints out each element of the modified list in reverse order.
>>> f5([1,2,3,4])
4
9
2
3
>>> f5([2,4])
4
2
>>> f5([11,42,64,15])
45
64
42
33

def f5(list):
if list == []:
return
f5(list[1:])
if list[0] % 2 == 1:
print(3*list[0])
else:
print(list[0])


6. Write a function f6(lst) that takes any multidimensional list and returns a one dimensional list with the same values. This is also known as flattening a list. Remember that you can use type([1,2,3]) == list to determine if something is a list. There should be one base case and two recursive cases.
>>> f6(['baa'])
['baa']
>>> f6(['baa', [4, True, [10, 5], [1, 2, ['moo']]], ["chirp"]])
['baa', 4, True, 10, 5, 1, 2, 'moo', "chirp"]
>>> f6([])
[]
>>> f6([[[[[[[[[[[[[[23]]]]]]]]]]]]]])
[23]

def f6(lst):
if type(lst) != list or lst == []:
return lst
elif type(lst[0]) != list:
return [lst[0]] + f6(lst[1:])
else:
return f6(lst[0]) + f6(lst[1:])


7. Consider a function $L_n$:

$L_n = \begin{cases} 2 & \text{if } n = 0; \\ 1 & \text{if } n = 1; \\ L_{n-1}+L_{n-2} & \text{if } n > 1; \\ \end{cases}$

Write a function f7(n) that calculates $L_n$
>>> f7(3)
4
>>> f7(14)
843
>>> f7(0)
2
>>> f7(22)
39603

def f7(n):
if n == 0:
return 2
if n == 1:
return 1
return f7(n-1) + f7(n-2)


8. Write a function f8(s) that returns True if s is a palindrome, and False otherwise.
>>> f8("")
True
>>> f8("kayak")
True
>>> f8("penguin")
False
>>> f8("a")
True

def f8(s):
if s == "":
return True
if s[0] == s[-1]:
return f8(s[1:-1])
return False


9. Write a function f9(n) that returns $n!$
>>> f9(0)
1
>>> f9(1)
1
>>> f9(2)
2
>>> f9(3)
6

def f9(n):
if n == 0:
return 1
return n * f9(n-1)


10. Write a function f10(list) that returns len(list).
>>> f10([1,2,3])
3
>>> f10([])
0
>>> f10([2])
1

def f10(list):
if list == []:
return 0
return 1 + f10(list[1:])


11. Write a function f11(list) that returns the last element in the list.
>>> f11([1,2,3])
3
>>> f11([])
>>> f11([1])
1

def f11(list):
if list == []:
return None
if len(list) == 1:
return list[0]
return f11(list[1:])


12. Write a function f12(n) that prints the numbers n through 1 in descending order.
>>> f12(3)
3
2
1
>>> f12(0)
>>> f12(1)
1

def f12(n):
if n > 0:
print(n)
f12(n-1)


13. Write a function f13(n) that returns the number of digits in n. You may assume n is a positive integer.
>>> f13(9175)
4
>>> f13(34)
2
>>> f13(268)
3
>>> f13(0)
1

def f13(n):
if n < 10:
return 1
return 1 + f13(n//10)


14. Write a function f14(list) that returns the first odd number in the list, and None if there are no odd numbers in the list.
>>> f14([1,2,3])
1
>>> f14([2,4])
>>> f14([2,4,6,8,10,3])
3

def f14(list):
if list == []:
return None
if list[0] % 2 == 1:
return list[0]
return f14(list[1:])


15. Write a function f15(list) that returns the sum of all the odd numbers in the list.
>>> f15([1,2,3])
4
>>> f15([2,4])
0
>>> f15([1,3,6,9])
13

def f15(list):
if list == []:
return 0
if list[0] % 2 == 1:
return list[0] + f15(list[1:])
return f15(list[1:])


16. Write a function f16(list) that returns a list of all the odd numbers in the list.
>>> f16([1,3,5,7])
[1, 3, 5, 7]
>>> f16([2,4])
[]
>>> f16([1,2,3,4,5])
[1, 3, 5]

def f16(list):
if list == []:
return []
if list[0] % 2 == 1:
return [list[0]] + f16(list[1:])
return f16(list[1:])


17. Write a function f17(list) that returns the second to last element in the list. Assume len(list) > 1.
>>> f17([1,2])
1
>>> f17([1,2,3,4])
3
>>> f17([1,2,3])
2

def f17(list):
if len(list) == 2:
return list[0]
return f17(list[1:])


18. Write a function f18(a,b) that returns the greatest common divisor of a and b.
>>> f18(5,4)
1
>>> f18(40,60)
20
>>> f18(9,3)
3

def f18(a,b):
if b == 0:
return a
return f18(b, a%b)


19. Write a function f19(list1, list2) that merges list1 and list2 in ascending order. Assume list1 and list2 are already sorted.
>>> f19([1,2,3],[4,5])
[1, 2, 3, 4, 5]
>>> f19([4,5],[1,2,3])
[1, 2, 3, 4, 5]
>>> f19([],[1,2,3])
[1, 2, 3]
>>> f19([1,2,3],[])
[1, 2, 3]
>>> f19([], [])
[]

def f19(list1, list2):
if list1 == []:
return list2
if list2 == []:
return list1
if list1[0] < list2[0]:
return [list1[0]] + f19(list1[1:], list2)
return [list2[0]] + f19(list1, list2[1:])


20. Write a function f20(list) that mergesorts the list. Consider using f19(list1, list2) for the merging step.
>>> f20([3,2,1])
[1, 2, 3]
>>> f20([])
[]
>>> f20([5,3,1,2,4,6])
[1, 2, 3, 4, 5, 6]

def f20(list):
if len(list) <= 1:
return list
else:
mid = len(list)//2
list1 = f20(list[:mid])
list2 = f20(list[mid:])
return f19(list1, list2)


21. Write a function f21(tree) that returns the height of the tree. The tree has the structure [value, left subtree, right subtree].
>>> f21([])
0
>>> f21([1,[],[]])
1
>>> f21([1,[1,[],[]],[]])
2

def f21(tree):
if tree == []:
return 0
return 1 + max(f21(tree[1]), f21(tree[2]))


22. Write a function f22(tree) that returns the number of nodes in the tree. The tree has the structure [value, left subtree, right subtree].
>>> f22([])
0
>>> f22([1,[],[]])
1
>>> f22([1,[1,[],[]],[1,[],[]])
3

def f22(tree):
if tree == []:
return 0
return 1 + f22(tree[1]) + f22(tree[2])


23. Write a function f23(tree) that returns the sum of the nodes in the tree. The tree has the structure [value, left subtree, right subtree].
>>> f23([])
0
>>> f23([1,[],[]])
1
>>> f23([1,[2,[],[]],[3,[],[]])
6

def f23(tree):
if tree == []:
return 0
return tree[0] + f23(tree[1]) + f23(tree[2])


24. Write a function f24(tree) that prints out the values of the tree in ascending order. The tree has the structure [value, left subtree, right subtree] and is a binary search tree.
>>> f24([])
>>> f24([1,[],[]])
1
>>> f24([2,[1,[],[]],[3,[],[4,[],[]]])
1
2
3
4

def f24(tree):
if tree == []:
return
f24(tree[1])
print(tree[0])
f24(tree[2])


25. Write a function f25(tree) that returns the smallest element in the tree. The tree has the structure [value, left subtree, right subtree] and is a binary search tree. Return -1 if the tree is empty.
>>> f25([])
-1
>>> f25([1,[],[]])
1
>>> f25([2,[1,[],[]],[3,[],[4,[],[]]])
1

def f25(tree):
if tree == []:
return -1
if tree[1] == [] and tree[2] == []:
return tree[0]
return f25(tree[1])


#### Looping

1. Write a function f1(n) that prints the following triangle.
>>> f1(5)
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
>>> f1(0)
>>> f1(1)
1

def f1(n):
for i in range(n):
for j in range(i+1):
print(j+1, end=" ")
print()


2. Write a function f2(n) that prints the following triangle.
>>> f2(3)
1
2 3
4 5 6
>>> f2(0)
>>> f2(1)
1
>>> f2(5)
1
2 3
4 5 6
7 8 9 10
11 12 13 14 15

def f2(n):
count = 1
for i in range(n):
for j in range(i+1):
print(count, end=" ")
count = count + 1
print()


3. Write a function f3(n) that prints the following triangle.
>>> f3(3)
1
2 3
4 5 6
2 3
1
>>> f3(4)
1
2 3
4 5 6
7 8 9 10
4 5 6
2 3
1
>>> f3(0)
>>> f3(1)
1

def f3(n):
count = 1
for i in range(n):
for j in range(i+1):
print(count, end=" ")
count = count + 1
print()
for i in range(n-1):
count = count - (2*(n-i-1)+1)
for j in range(n-i-1):
print(count, end=" ")
count = count + 1
print()


4. Write a function f4(n) that prints the following triangle.
>>> f4(3)
1
2 3
4 5 6
7 8
9
>>> f4(0)
>>> f4(1)
1

def f4(n):
count = 1
for i in range(n):
for j in range(i+1):
print(count, end=" ")
count = count + 1
print()
for i in range(n-1):
for j in range(n-i-1):
print(count, end=" ")
count = count + 1
print()


5. Write a function f5(matrix) that prints the sum of every row in the matrix.
>>> f5([[1,0],[0,1]])
1
1
>>> f5([[1,2,3],[4,5,6]])
6
15
>>> f5([[1],[2],[3],[4]])
1
2
3
4

def f5(matrix):
for i in range(len(matrix)):
sum = 0
for j in range(len(matrix[i])):
sum = sum + matrix[i][j]
print(sum)


6. Write a function f6(matrix) that returns the sum of all the elements in the matrix.
>>> f6([[1,0],[0,1]])
2
>>> f6([[1,2,3],[4,5,6]])
21
>>> f6([[1],[2],[3],[4]])
10

def f6(matrix):
sum = 0
for i in range(len(matrix)):
for j in range(len(matrix[i])):
sum = sum + matrix[i][j]
return sum


7. Write a function f7(matrix) that returns the product of all the elements in the matrix.
>>> f7([[1,0],[0,1]])
0
>>> f7([[1,2,3],[4,5,6]])
720
>>> f7([[1],[2],[3],[4]])
24

def f7(matrix):
prod = 1
for i in range(len(matrix)):
for j in range(len(matrix[i])):
prod = prod * matrix[i][j]
return prod


8. Write a function f8(matrix) that will print the odd numbers in the matrix with each row on one line.
>>> f8([[1,0],[0,1]])
1
1
>>> f8([[1,2,3],[4,5,6]])
1 3
5
>>> f8([[1],[2],[3],[4]])
1

3


def f8(matrix):
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if matrix[i][j] % 2 == 1:
print(matrix[i][j], end=" ")
print()


9. Write a function f9(matrix1, matrix2) that will return the sum of matrix1 and matrix2. Assume matrix1 and matrix2 have the same dimensions.
>>> f9([[1,0],[0,1]],[[1,0],[0,1]])
[[2, 0], [0, 2]]
>>> f8([[1,2,3],[4,5,6]],[[-1,-1,-1],[-1,-1,-1]])
[[0, 1, 2], [3, 4, 5]]
>>> f15([[1],[2],[3],[4]],[[4],[3],[2],[1]])
[[5], [5], [5], [5]]

def f9(matrix1, matrix2):
res = []
for i in range(len(matrix1)):
row = []
for j in range(len(matrix1[i])):
row.append(None)
res.append(row)
for i in range(len(matrix1)):
for j in range(len(matrix1[i])):
res[i][j] = matrix1[i][j] + matrix2[i][j]


10. Write a function f10(matrix1, matrix2) that will return the product of matrix1 and matrix2. Assume len(matrix1) == len(matrix2[0]).
>>> f10([[1,0],[0,1]],[[1,0],[0,1]],)
[[1, 0], [0, 1]]
>>> f10([[1,2,3],[4,5,6]],[[-1,-1],[-1,-1],[-1,-1]])
[[-6, -6], [-15, -15]]
>>> f10([[4,3,2,1]],[[1],[2],[3],[4]])
[20]

def f10(matrix1, matrix2):
res = []
for i in range(len(matrix1)):
row = []
for j in range(len(matrix2[0])):
row.append(0)
res.append(row)

for i in range(len(matrix1)):
for j in range(len(matrix2[0])):
for k in range(len(matrix1[0])):
res[i][j] = res[i][j] + matrix1[i][k] * matrix2[k][j]

return res


11. Write a function f11(matrix) that returns True if the matrix is the identity matrix, and False otherwise. Assume len(matrix) == len(matrix[0]).
>>> f11([[1]])
True
>>> f11([[1,0,0],[0,1,0],[0,0,1]])
True
>>> f11([[1,0,0],[0,1,5],[0,0,1]])
False

def f11(matrix):
for i in range(len(matrix)):
for j in range(len(matrix[i])):
if i == j and matrix[i][j] != 1:
return False
if i != j and matrix[i][j] != 0:
return False
return True


12. Write a function f12(rows, cols) that returns a two dimensional list where each element corresponds to how many adjacent neighbors it has. Neighbors are defined as spaces above, below, to the left, and to the right.
>>> f12(3,3)
[[2, 3, 2], [3, 4, 3], [2, 3, 2]]
>>> f12(5,1)
[[1], [2], [2], [2], [1]]
>>> f12(5,0)
[[], [], [], [], []]
>>> f12(0,5)
[]
>>> f12(2,2)
[[2, 2], [2, 2]]

def f12(rows, cols):
matrix = []
for i in range(rows):
row = []
for j in range(cols):
row.append(0)
matrix.append(row)

for row in range(rows):
for col in range(cols):
num_neighbors = 0
if (row - 1) in range(rows):
num_neighbors += 1
if (row + 1) in range(rows):
num_neighbors += 1
if (col - 1) in range(cols):
num_neighbors += 1
if (col + 1) in range(cols):
num_neighbors += 1
matrix[row][col] = num_neighbors
return matrix


#### Canvas

1. Write a function f1(matrix) that draws 80x60 rectangles for each element in the two dimensional matrix. The rectangles should be colored blue if the element is even, and yellow otherwise.
>>> f1([[1, 0], [0, 1], [1, 0], [0, 1]])

>>> f1([[0,2,1,4], [4,5,3,8], [9,4,7,1], [5,1,7,0]])

>>> f1([[7, 4, 2, 3, 1, 3, 8, 9]])

import tkinter
from tkinter import Canvas

def f1(matrix):
num_rows = len(matrix)
num_cols = len(matrix[0])
rect_width = 80
rect_height = 60
my_window = tkinter.Tk()
my_canvas = Canvas(my_window, width = num_cols*rect_width, height = num_rows*rect_height)
my_canvas.pack()

colors = ["blue", "yellow"]
for row in range(num_rows):
for col in range(num_cols):
my_canvas.create_rectangle(col*rect_width, row*rect_height,
col*rect_width + rect_width,
row*rect_height + rect_height,
fill = colors[matrix[row][col] % 2])


2. Write a function f2() that draws the picture below on a 400x400 window. The radius of the larger red circle is 100 units, the radius of the inner white circle is 75 units, and the radius of the inner red circle is 30 units. The circles are all positioned at the center of the windows.
import tkinter
from tkinter import Canvas

def f2():
my_window = tkinter.Tk()
my_canvas = Canvas(my_window, width = 400, height = 400)
my_canvas.pack()
my_canvas.create_rectangle(0,0,400,400,fill='white')
my_canvas.create_oval(100,100,300,300,fill='red')
my_canvas.create_oval(125,125,275,275,fill='white')
my_canvas.create_oval(170,170,230,230,fill='red')


3. Write a function f3(width, height), that takes a width and height and recursively draws rectangles, where the first rectangle is the size of the canvas and each consecutive rectangle has the same width but has a height that is exactly 7/8 the size of the previous heightt. The function should stop drawing once the height is less than 5. You will most likely need a helper function
>>> f3(400, 400)

import tkinter
from tkinter import Canvas
from random import randint

def f3(width, height):
my_window = tkinter.Tk()
my_canvas = Canvas(my_window, width = width, height = height)
my_canvas.pack()
# can input any arbitrary color at first
f3_helper(my_canvas, width, height, "white")

def f3_helper(my_canvas, width, height, last_color):
if height < 5:
return None
else:
colors = ["red", "orange", "yellow", "green", "blue", "magenta",
"white", "grey"]
fill_color = colors[randint(0, len(colors) - 1)]
while fill_color == last_color: #this prevents repetition of colors
fill_color = colors[randint(0, len(colors) - 1)]
my_canvas.create_rectangle(1, 1, width, height, fill = fill_color)
f3_helper(my_canvas, width, 7*height/8, fill_color)