STATS 507: Practice Final Exam¶
name: ___
uniqname: ___
You have 120 minutes to complete this exam.
You may not communicate with anyone (other the course instructors) during the exam.
You may not view local files on your computer other than the course lecture slides and past homework submissions.
You may access not access the web sites during the exam except for the follow sites:
• Textbook: https://www.py4e.com/
• Built-in Python functions: https://docs.python.org/3.8/
• Numpy: https://docs.scipy.org/doc/numpy/user/
• Matplotlib: https://matplotlib.org/
• Pytorch: https://pytorch.org/docs/stable/index.html
• Slides & To submit: https://umich.instructure.com/courses/
In [ ]:
%matplotlib inline
import math
import itertools
import functools
import numpy as np
import matplotlib.pyplot as plt
import torch
import pandas as pd
Problem 1¶
When analysing data collected as part of a science experiment it may be desirable to remove the most extreme values before performing other calculations. Write a function that takes a list of values and an non-negative integer, n, as its parameters. The function should create a new copy of the list with the $n$ largest elements and the $n$ smallest elements removed. Then it should return the new copy of the list as the function’s only result. The order of the elements in the returned list does not have to match the order of the elements in the original list.
In [ ]:
def remove_extremes(lst, n):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
input_lst = [3, 5, 9, 7, 11, 1]
output_lst = remove_extremes(input_lst, 1)
assert set(output_lst) == {3, 5, 7, 9}
In [ ]:
input_lst = [3, 5, 9, 7, 11, 1]
output_lst = remove_extremes(input_lst, 2)
assert set(output_lst) == {5, 7}
Problem 2¶
For $z \in [0, 2\pi)$, the infinite sum $$\sum_{k=0}^\infty \frac{(-1)^k z^{2k}}{(2k)!} = \cos z.$$ Implement a function that approximates cosine of $z$ by summing the first $n$ terms of the summation above.
In [ ]:
def cos_approx(z, n):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
assert abs(cos_approx(math.pi / 4, 10) – 0.7071) < 1e-4
Problem 3¶
The $n$-th Woodall number ($n = 1, 2, \ldots$) is given by $$W_{n}=n\cdot 2^{n}-1.$$ Write a generator function that enumerates the Woodall numbers.
In [ ]:
def woodall_gen():
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
woodall_iter = woodall_gen()
five_woodalls = [next(woodall_iter) for _ in range(5)]
assert five_woodalls == [1, 7, 23, 63, 159]
Problem 4¶
Write a function named is_integer that determines whether or not a string represents a valid integer. When determining if a string represents an integer you should ignore any leading or trailing white space. Once this white space is ignored, a string represents an integer if its length is at least one and it only contains digits, or if its first character is either + or - and the first character is followed by one or more characters, all of which are digits. You may not use the built-in int function in your solution, nor may you use regular expressions.
In [ ]:
def is_integer(s):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
assert is_integer("42")
assert not is_integer("funny hat")
In [ ]:
assert is_integer("+1")
assert is_integer("-9999")
assert not is_integer("99+77")
In [ ]:
assert not is_integer("-9999.9")
assert not is_integer("99 + 77")
assert not is_integer("")
Problem 5¶
For this problem, trigrams are sequences of three words appearing consecutively in text, which are not separated by punctuation. Write a function that takes text as an argument and returns a set of all trigrams that appear more than once in it. You can assume the input text will only contain lowercase characters, periods, and commas.
In [ ]:
def common_trigrams(text):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
text = "it was the best of times, it was the worst of times."
assert common_trigrams(text) == {'it was the'}
text = ("the current governor of michigan is gretchen esther whitmer. "
"but gretchen esther whitmer was not always the governor of michigan.")
correct = {'governor of michigan', 'gretchen esther whitmer'}
claimed = common_trigrams(text)
assert claimed == correct
In [ ]:
Problem 6¶
You are given an integer $n$. Your task is to return a pattern (as a string) of size $n$ like the ones shown below.
# size n = 3
----c----
--c-b-c--
c-b-a-b-c
--c-b-c--
----c----
# size n = 5
--------e--------
------e-d-e------
----e-d-c-d-e----
--e-d-c-b-c-d-e--
e-d-c-b-a-b-c-d-e
--e-d-c-b-c-d-e--
----e-d-c-d-e----
------e-d-e------
--------e--------
In [ ]:
def make_ascii_art(n):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
assert make_ascii_art(1) == "a\n"
assert make_ascii_art(3) == ("----c----\n"
"--c-b-c--\n"
"c-b-a-b-c\n"
"--c-b-c--\n"
"----c----\n")
Problem 7¶
Suppose $d$ is a positive integer. Suppose $A \in \mathbb R^{d \times d}$, $B \in \mathbb R^{d}$, and $C \in \mathbb R^1$. Let $$f(x) = x^\top Ax + B^\top x + C.$$ Use numpy to implement the mathematical function $f$.
In [ ]:
def eval_f(A, B, C, x):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
A = np.ones((3, 3))
B = np.ones(3)
assert abs(eval_f(A, B, 42., np.zeros(3)) - 42.0) < 1e-6
assert abs(eval_f(A, B, 0., np.ones(3)) - 12.0) < 1e-6
Problem 8¶
Make a contour plot showing $f$ from Problem 7, with $A$ set to the $2\times 2$ identity matrix, $B = (1, 9)^\top$, and $C = -1$. Your plot should show $f$ on the domain $[-20, 20] \times [-20, 20]$.
In [ ]:
# YOUR CODE HERE
raise NotImplementedError()
Problem 9¶
Use PyTorch and gradient descent to find the minimum of $f$ from Problem 6. Assume that $A$, $B$, and $C$ are selected so that $f$ has exactly one local minimum. In addition to A, B, and C, your function should take as arguments an initial iterate x0, a learning rate lr, and a number of iterations num_iters.
In [ ]:
def minimize_f(A, B, C, x0, lr, num_iters):
# YOUR CODE HERE
raise NotImplementedError()
In [ ]:
A = torch.tensor([[3., 1.], [1., 2.]])
B = torch.tensor([5., 6.])
C = torch.tensor(7.)
x0 = torch.ones(2, dtype=torch.float32)
assert abs(minimize_f(A, B, C, x0, 0.1, 100) - 2.1) < 1e-2
A = torch.eye(2)
B = torch.zeros(2)
C = torch.tensor(7.)
x0 = torch.ones(2)
assert abs(minimize_f(A, B, C, x0, 0.1, 100) - 7) < 1e-2