# 15110 Fall 2014

## By: Benjamin Lam

### Instructions

Try these practice problems to prepare you for the upcoming lab exam. They may be slightly easier or harder than the actual difficulty of the lab exam, so if you would like to gauge the difficulty of the exam, take a look at some of the past exams on the course web page. These exercises were designed in mind to help you practice two major themes-manipulation of 2D lists and recursion-that I noticed were important on past lab exams.

If you want to see the answers to these exercises, please email me at bklam@andrew.cmu.edu with your potential solutions attached . They don't have to be complete or correct, but it's a measure to try help you figure out for yourself what you do and don't know if you get stuck on a particular problem.

1. Write a function f1(matrix) that takes a 2D-list matrix of size N x N and returns a boolean describing whether the input matrix is an identity matrix. An identity matrix is defined as a matrix with ones located along the diagonal (top left to bottom right) and zeroes at every other index. Your solution should work for any general N x N size.

Hint: See sample usage.

Sample Usage:

  >>> f1([[1]])
True
>>> f1([[1, 0, 0], [0, 1, 0], [0, 0, 1]])
True
>>> f1([[1, 0, 0], [0, 1, 5], [0, 0, 1]])
False
2. Write a function f2(rows, cols) that generates a 2D-list, where the number at each index indicates how many neighbors a particular index has. (This version excludes diagonal neighbors. Try to write both versions!)

Hint: To make this easier to see and debug, I wrote a function you can use that prints the result of the f2 function call in an easy-to-read fashion.

  def print2darray(matrix):
print("[")
for element in matrix:
print(" " + str(element))
if len(matrix) > 0:
print(" " * len(str(matrix[0])) + " ]")
else:
print(" ]")

Sample Usage:

  >>> f2(3, 3)
[[2, 3, 2], [3, 4, 3], [2, 3, 2]]
>>> f2(5, 1)
[[1], [2], [2], [2], [1]]
or, alternatively:
  >>> print2darray(f2(3, 3))
[
[2, 3, 2]
[3, 4, 3]
[2, 3, 2]
]
>>> print2darray(f2(5, 0))
[
[]
[]
[]
[]
[]
]
>>> print2darray(f2(5, 1))
[
[1]
[2]
[2]
[2]
[1]
]
>>> print2darray(f2(0, 5))
[
]
>>> print2darray(f2(2, 2))
[
[2, 2]
[2, 2]
]
>>> print2darray(f2(4, 3))
[
[2, 3, 2]
[3, 4, 3]
[3, 4, 3]
[2, 3, 2]
]
3. Write a function f3(matrix) that takes in a 2D-list/matrix and draws an 80x60 rectangle for each element in the matrix. The rectangles should be colored yellow or blue depending on whether the element at that corresponding index is odd or even, respectively.

Hint: This question is just like question 2 from lab 11, only instead of only taking in a 4x4 array as its parameter, f3 can take in any arbitrary matrix.

Sample Usage:

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

4. Write a function f4(n) that returns the $n$th Lucas number. The Lucas numbers are defined as: $$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}$$

Sample Usage:

  >>> f4(3)
4
>>> f4(14)
843
>>> f4(22)
39603
>>> f4(0)
2
5. Write a function f5(a) that recursively multiplies all of the odd elements in the list a by 3 and then prints the results in backwards order.

Hint: Try breaking the problem down into pieces. First try and write a recursive function that prints all elements in a list in backwards order. Then try modifying that function to print only odd elements. Then try and print the odd elements times three in backwards order. The function should return None.

Sample Usage:

  >>> f5([1, 2, 3, 4, 5, 6])
15
9
3
>>> f5([2, 4])
>>> f5([11, 42, 63, 15])
45
189
33
6. Write a function f6(width, height), that takes a width and height and recursively draws rectangles, where the first rectangle is the size of the canvas (size width x height) and each consecutive rectangle has the same width but has a height that is exactly 7/8 the size of the previous height (see image). The function should stop drawing once the height is less than 5.

Hint: You will most likely need a helper function. You can write a main function that initializes the canvas and then calls the recursive helper function.

Sample Usage:

  >>> f6(400, 400)

7. Write a function f7(a) that takes any multidimensional list and returns a one-dimensional version of the input list a (known as flattening a list).

Hint: This function will probably be recursive since there are lists inside lists inside lists... Also, remember that there are different types of data in Python. For example, the expression type(3) == int will return True, as well as type([3, 4, 5]) == list. There should be one base case and two recursive cases.

Sample Usage:

  >>> f7(['baa'])
['baa']
>>> f7(['baa', [4, True, [10, 5], [1, 2, ['moo']]], ["chirp"]])
['baa', 4, True, 10, 5, 1, 2, 'moo', "chirp"]
>>> f7([])
[]
>>> f7([[[[[[[[[[[[[[23]]]]]]]]]]]]]])
[23]
8. Consider the following function definition for any positive integer: $$f(n) = \begin{cases} n/2 & \text{if n is even} \\ 3n+1 & \text{if n is odd} \\ \end{cases}$$ It is believed that if any positive integer is chosen, then computing this function repeatedly on the result will ultimately end at 1 (known as the Collatz Conjecture). For instance, consider $f(6)$, which generates the following sequence: $$6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1$$ for a total of 9 terms (8 steps). Write a function f8(n) that takes a positive integer n and returns the number of terms generated in this sequence.

Sample Usage:

  >>> f8(1)
1
>>> f8(6)
9
>>> f8(11)
15
>>> f8(63728127)
950