HW 0 -- Background

This assignment is a diagnostic of whether you have the prerequisite background for this subject.

• It has an introduction to cat-soop, our homework platform, including how questions are evaluated.
• It is followed by some analytical and some coding questions.
• If you find that it is very difficult, that might be a sign that you should strengthen your background in the prerequite areas. Feel free to ask a staff member (via private Piazza post) about this.

1) Intro to Homework§

Welcome to your first homework!

• We view homework as a critical mechanism for teaching and learning, not as an evaluation mechanism. There are class-grade points associated with it, as an incentive for you to do it.

• There is `free checking' in the sense that you can submit your anwers to questions as many times as you want to, and get feedback on their correctness. So, it's possible to get a perfect score through persistence.

• Note that you won't get credit for a question until you click 'submit' and that, once you click 'view answer', you will no longer be allowed to submit.

• You can read the late submission policy on the course information page. The way it interacts with cat-soop is best understood in two phases:

  1. First, ignoring extensions, for each question, we evaluate each of your submissions in terms of how late it was submitted and how correct it was. You will be given the score of the best submission (so, for example, if you submit a correct solution on time, but then go back and play with a question later and submit something incorrect, that won't decrease your score.)
  2. Second, in an outer loop, we will determine the best possible way to apply your extension days, where the policy above is now applied relative to the extended deadlines.

• Please take the questions seriously as educational material. For example, although a monkey could get all the multiple-choice questions right eventually, it might not learn much! Once you submit a solution we encourage you hit 'view answer' to see our solution and then hit 'view explanation' to see an explanation of the answer, and be sure you understand why your answer was right.

• Some of the material is brand new this semester and there will inevitably be bugs. Please post on Piazza if you suspect a bug (and/or if you're stuck). If your question reveals the answer, then please post privately. We also have not yet completed explanations for all the questions. If you'd like to contribute some, please post them!

• You may choose to tackle the questions in any order, but the homeworks are designed to be followed sequentially. Often, insights from the first problems will help with the later ones.

• This software environment (cat-soop) is great for many things, but it's not a great software debugging enviroment. We strongly encourage you to debug your solutions to coding questions using Google Colab (an online environment which means you don't need to install a particular version of Python or packages on your machine).

• Each week, we will provide a Colab notebook with predefined helper functions and test cases. You should draft and debug your solution in Colab, then paste it into cat-soop for final checking and submission.

• Though where you work and debug is ultimately up to you, please note that the colab notebooks are the only place where you can view the pre-defined imports and utility functions that will be extremely useful for completing the coding questions. So, before you start any coding, please look at colab! And if you leave colab for a different development environment, you will want to take these imports and functions with you. (They are already defined in catsoop, so copying them there is not necessary.)

• This week's Colab notebook can be found here: Colab Notebook (Click Me!)

Here are some practice questions. Play around with them, including checking wrong answers. When you're done, view answers and read the explanations.

Who is the best robot? -- Gort Bender Shakey There are no bad robots.

Enter a Python list of numbers corresponding to the first three Fibonacci numbers greater than 1.

1.1) Fibonacci§

Complete the following implementation of Fibonacci number that returns the n-th Fibonacci number

For reference, our solution is 5 line(s) of code.

def fib(n): '''Compute the Fibonacci number. The first and the second Fibonacci numbers are 1 and 1. Args: n: An int. Returns: fib_n: An int that is the n-th Fibonacci number. ''' raise NotImplementedError("Implement me!")

2) Non-coding questions§

2.1) Random vectors§

Indicate which of the following statements are true:

	A probability distribution can assign probability greater than 1 to an event.
	A probability density function can have values greater than 1.
	A probability density function can assign probability greater than 1 to an event.
	A probability density function of a Normal distribution can have values greater than 1.
	If the discrete random variables X and Y are independent, then P(X=x, Y=y) = P(X=x)P(Y=y)
	P(X=x|Y=y) = P(Y=y|X=x)P(Y=y)/P(X=x)
	P(X=x|Y=y) = P(Y=y|X=x)P(X=x)/P(Y=y)
	P(X=x|Y=y) = P(Y=y,X=x)/P(Y=y)
	Two random vectors {\bf x}_1 \in R^d and {\bf x}_2 \in R^d are said to be uncorrelated if \rho = E \left [(\bar{{\bf x}}_1 -{\bf x}_1)(\bar{{\bf x}}_2-{\bf x}_2)^T \right ] = 0.
	Two random vectors {\bf x}_1 \in R^d and {\bf x}_2 \in R^d are said to be independent if \rho = E \left [(\bar{{\bf x}}_1 -{\bf x}_1)(\bar{{\bf x}}_2-{\bf x}_2)^T \right ] = 0.
	Assume a multivariate Normal distribution over [x_1, x_2]^T, where [x_1, x_2]^T \sim N(0, \Sigma) with covariance \Sigma = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}. The marginal distribution over x_1 is N(0, 1).
	Assume a multivariate Normal distribution over [x_1, x_2]^T, where [x_1, x_2]^T \sim N(0, \Sigma) with covariance \Sigma = \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix}. The marginal distribution over x_1 is N(0, 2).
	Uncorrelated, jointly Gaussian random variables are independent.

A reminder that these questions are intended to be diagnostic. If you are unfamiliar with the notation, or the terminology, you may not have the prerequisites for this subject. If you are unfamiliar with multivariate distributions, you also may not have the prerequisites for this subject.

3) Coding questions§

3.1) Gradient Descent§

Complete the following implementation of gradient descent to estimate the parameters of a linear model y = \theta^T x, where x \in \mathbb{R}^m, y \in \mathbb{R}^n, and \theta \in \mathbb{R}^{m \times n}. Please use the following loss function:

For reference, our solution is 5 line(s) of code.

def run_linear_regression_gradient_descent(X, Y, initial_weights, step_size=1e-4, num_steps=10000): '''Use gradient descent to find weights for linear regression model. The model is Y = np.dot(X, weights). Args: X: A np.ndarray of shape (num_examples, input_dim). Y: A np.ndarray of shape (num_examples, output_dim). initial_weights: A np.ndarray of shape (input_dim, output_dim). step_size: A float step size for weight updates. num_steps: An int total number of gradient descent steps. Returns: weights: A np.ndarray of shape (input_dim, output_dim). ''' raise NotImplementedError("Implement me!")

3.2) Breadth-first search§

Complete the following implementation of breadth-first search. Note that the expected output is a list of actions. The search should not revisit any states.

For reference, our solution is 15 line(s) of code.

def breadth_first_search(initial_state, check_goal_fn, successor_fn, max_expansions=1000): '''Finds a plan from initial state to goal using BFS. Args: initial_state: Any state representation. check_goal_fn: A function that takes a state and returns a bool indicating whether the goal is reached. successor_fn: A function that takes a state and yields zero or more (action, next state). max_expansions: An int bounding the number of times that thhe successor_fn is called before giving up. Returns: plan: A list of actions or None. ''' raise NotImplementedError("Implement me!")