Final Exam Practice Problems — CS111, Boston University

Python Fundamentals, tracing

What does the following code print?

x = 15
y = x
z = x // 2 
w = x / 2
x = x + 2 
print(x, y, z, w)

What does the following code print?
```
a = [1, 2, 3, 4]
b = a
b[2] = 6
print('a =', a, 'b =', b)
```
Using a memory diagram and a couple of sentences, explain the result printed.

What does the following code print?

num = 30
if num > 20:
    print("do")
    if num < 15:
        print("go")
    print("no")
elif num < 0:
    print("lo")
    if num == 30:
        print("mo")
elif num // 3 == 10:
    print("so")
if num > 5:
    print("to")

What does the following code print?

for i in range(3, 5):
    for j in range(2, i):
        print(i, j)
    print(i + j)
print(i * j)

What does the following code print?

def foo(a, b):
    while b > 0:
        a += 1
        b -= 1
    print(a, b)
    return a

a = 7
b = 3
foo(b, a)
print(a, b)

Using a memory diagram and a couple of sentences, explain the result printed.

What is printed when you invoke prob3() below?
```
def eat(x):
    x[1] = 9
    x[3] = 11

def prob3():
    food = [4, 5, 6, 7]
    eat(food)
    print('food =', food)
```
Using a memory diagram and a couple of sentences, explain the result printed.

Recursion

Consider the following function that returns the nth Fibonacci number, where the zeroth Fibonacci number is 1 and the first Fibonacci number is also 1:
```
def fib(n):
    if n < 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)
```
If you were to evaluate the following at the Python prompt: >>> fib(5) 8 How many times was fib called in this evaluation of fib(5)?
Use recursion (no loops!) to write a Python function uniquify(lst), which takes in any list lst and returns a list of the distinct elements in the list lst. The order of the elements may be preserved, but they do not have to be. For example:
```
>>> uniquify( [ 42, 'spam', 42, 5, 42, 5, 'spam', 42, 5, 5, 5 ] ) [ 'spam', 42, 5 ]
>>> mylist = range(4) + range(3)
>>> uniquify(mylist)
[ 3, 0, 1, 2 ]
```
Hint: Your function may make use of the in operator.
Write a recursive Python function named merge that will merge two sorted lists of integers and return the merged sorted list. For example:
```
>>> a = [1, 4, 7, 11, 14]
>>> b = [2, 3, 6, 11, 13, 17]
>>> c = merge(a, b)
>>> print('c is', c)
c is [1, 2, 3, 4, 6, 7, 11, 11, 13, 14, 17]
```

Loops

Use a loop to write a Python function is_prime(n), which takes in an integer n and returns True if n is prime and False if n is composite. You may assume that n will be strictly greater than 1.
Use recursion (no loops!) to write a Python function add_primes(lst), which takes in a list lst of integers (all integers will be at least 2) and it returns the sum of only the prime numbers in the list lst. Hint: Use the function you wrote in (8)!
Write a function create_2d that takes as input two integers height and width, and that creates and returns a 2D list (i.e., a list of lists) with values that are the row number multiplied by the column number. For example:
```
>>> create_2d(3, 5)
[[0, 0, 0, 0, 0], [0, 1, 2, 3, 4], [0, 2, 4, 6, 8]]
```
Write a function add_one that takes an input grid that is a 2D list (a list of lists). Your function should add 1 to each element of grid, but it should not return anything. For example:
```
>>> my_grid = create_2d(3, 5)
>>> add_one(my_grid)
>>> my_grid
[[1, 1, 1, 1, 1], [1, 2, 3, 4, 5], [1, 3, 5, 7, 9]]
```
Write a Python function symmetric(grid), which takes in a 2-D list of numbers, grid. You should assume that grid is a square array, with an equal number of rows and columns. Then, symmetric should return True if the values of grid are symmetric across the NW-SE diagonal— i.e., if the values “mirror” each other on either side of that diagonal (see below)—and should return False if the values of grid are not symmetric across the NW-SE diagonal. (Start by solving this problem using iteration – i.e., one or more loops. For an optional extra challenge, try writing this function using recursion, list comprehensions, and slicing with no loops at all!)
```
>>> symmetric( [ [1] ] )
True
>>> symmetric( [ [1, 2],
                 [2, 5] ] )
True
>>> symmetric( [ [1, 2],
[1, 1] ] )
False
>>> symmetric( [ [1, 2, 3],
                 [2, 4, 5],
                 [3, 5, 6] ] )
# is symmetric because the 2s match
# not symmetric because 1 != 2
# is symmetric because 2s, 3s and 5s match
True
```

Object-oriented Design and Classes

Below is the start of a Matrix class that initializes each object’s data to a 2-D list of all zeros:
```
class Matrix:
    def __init__(self, nrows, ncols):
        self.nrows = nrows
        self.ncols = ncols
        self.data = [ [0]*ncols for r in range(nrows) ]
```
Write a method max(self, other) that takes in a second Matrix object other. This method should return a matrix with as many rows as are found in the shorter of self and other, and with as many columns as are found in the narrower of self and other. Each entry of the returned matrix should be the larger (the max) of the corresponding entries in self and other. Neither self nor other should change.
(a) Create a Python class named Phonebook with a single attribute called entries. The constructor should initialize entries to be a dictionary containing the following names and phone numbers:
Bob 72345, Sally 71000, John 79999. Use the names as the keys of the dictionary and the phone numbers (which you should represent as ints) as the values.

(b) Add a method named contains to your Phonebook class. It should take a parameter name and return True if name is present in the phonebook, and False otherwise. For example:
```
>>> book = Phonebook()
>>> book.contains('Foo')
False
>>> book.contains('Bob')
True
```
(c) Write another method for your Phonebook class called number_for that takes a parameter name and returns the phone number for name in the called Phonebook object. It should return -1 if name is not found. Here is an example:
```
>>> book = Phonebook()
>>> book.number_for('Sally')
71000
>>> book.number_for('foobar')
-1
```
Hint: Consider using your contains method from problem 8.

(d) Write another method for your Phonebook class called add_entry that takes as parameters a name and a number and adds an appropriate entry to the phonebook. For example:
```
>>> book = Phonebook()
>>> book.number_for('Turing')
-1
>>> book.add_entry('Turing', 77777)
>>> book.number_for('Turing')
77777
```
(a) Create a Python class called Triangle. The constructor for this class should take two arguments, base and height, and store those values in appropriately named attributes. In addition, you should add a method called area that computes and returns the area of the triangle. (The area of a triangle is 0.5 times the product of its base and height.) For example:
```
>>> tri = Triangle(3, 4)
>>> tri.area()
6.0
```
(b) Add a method to your Triangle class that enables you print a Triangle object in a readable way. For example:
```
>>> tri = Triangle(3, 4)
>>> print(tri)
triangle with base 3 and height 4
```
(c) Add a method to your Triangle class that will allow you to use the == operator to test if two Triangle objects are equal–i.e., if they have the same base and height. For example:
```
>>> tri1 = Triangle(3, 4)
>>> tri2 = Triangle(3, 4)
>>> tri3 = Triangle(4, 3)
>>> tri1 == tri2
True
>>> tri1 == tri3
False
```
(d) Write a function called main that creates three triangle objects tri1 (with base 3 and height 4), tri2 (with base 6 and height 6), and tri3 (also with base 3 and height 4). The function should print the three objects and their areas. Next, it should test whether tri1 and tri2 are equal and report the result. Finally, it should test whether tri1 and tri3 are equal and report the result. Your function should take full advantage of the Triangle methods you have written. Here is the desired output:
```
>>> main()
tri1: triangle with base 3 and height 4 (area = 6.0)
tri2: triangle with base 6 and height 6 (area = 18.0)
tri3: triangle with base 3 and height 4 (area = 6.0)
tri1 and tri2 are not equal
tri1 and tri3 are equal
```
(a) Write a subclass of Triangle called EquilateralTriangle. Its constructor should take a single parameter side representing the length of a side. However, the new class should not have any new attributes. Rather, it should use the attributes that are inherited from Triangle, and you should initialize those attributes by calling the superclass constructor and passing it the appropriate values. (You should approximate the height of the triangle as 0.866 times the side length.) For example:
```
>>> tri1 = EquilateralTriangle(6)
>>> print(tri1)
triangle with base 6 and height 5.196
```
(b) Override the appropriate method in EquilateralTriangle so that printing an EquilateralTriangle object produces an output that looks like the following:
```
>>> tri1 = EquilateralTriangle(6)
>>> print(tri1)
equilateral triangle with side 6
```