CPSC 340 Assignment 0

CPSC 340 Assignment 0 
Rationale for Assignment 0 : CPSC 340 is tough because it combines knowledge and skills across several
disciplines. To succeed in the course, you will need:
• Basic Python programming, including NumPy and plotting with matplotlib.
• Math to the level of the course prerequisites: linear algebra, multivariable calculus, some probability.
• Statistics, algorithms and data structures to the level of the course prerequisites.
• Some basic LaTeX and git skills so that you can typeset equations and submit your assignments.
The purpose of this assignment is to make sure you are prepared for this course. I anticipate that each of
you will have different strengths and weaknesses, so don’t be worried if you struggle with some aspects of
the assignment. But if you find this assignment to be very difficult overall, that is an early warning sign
that you may not be prepared to take CPSC 340 at this time. Future assignments will be longer and more
difficult than this one.
Instructions
Rubric: {mechanics:3}
IMPORTANT!!!!! Before proceeding, please carefully read the general homework instructions
at https://github.ugrad.cs.ubc.ca/CPSC340-2017W-T2/home/blob/master/homework_instructions.
md. You need to be signed in to github.ugrad.cs.ubc.ca (using your CS ugrad id) in order to view this file.
We use blue to highlight the deliverables that you must answer/do/submit with the assignment.
1 Linear Algebra Review
For these questions you may find it helpful to review these notes on linear algebra:
http://www.cs.ubc.ca/~schmidtm/Documents/2009_Notes_LinearAlgebra.pdf
1.1 Basic Operations
Rubric: {reasoning:7}
Use the definitions below,
α = 2, x =


0
1
2

 , y =


3
4
5

 , z =


1
2
−1

 , A =


3 2 2
1 3 1
1 1 3

 ,
and use xi to denote element i of vector x. Evaluate the following expresions (you do not need to show your
work).
1
1. Pn
i=1 xiyi (inner product).
2. Pn
i=1 xizi (inner product between orthogonal vectors).
3. α(x + y) (vector addition and scalar multiplication).
4. kxk (Euclidean norm of x).
5. x
T
(vector tranpose).
6. AT
(matrix transpose).
7. Ax (matrix-vector multiplication).
1.2 Matrix Algebra Rules
Rubric: {reasoning:9}
Assume that {x, y, z} are n × 1 column vectors and {A, B, C} are n × n real-valued matrices. State whether
each of the below is true in general (you do not need to show your work).
1. x
T y =
Pn
i=1 xiyi
.
2. x
T x = kxk
2
.
3. x
T
(y + z) = z
T x + x
T y.
4. x
T
(y
T
z) = (x
T y)
T
z.
5. AB = BA.
6. A(B + C) = AB + AC.
7. (AB)
T = AT BT
.
8. x
T Ay = y
T AT x.
9. det A 6= 0 ⇐⇒ A is invertible.
1.3 Special Matrices
Rubric: {reasoning:3}
In one sentence, write down the defining properties of the following special types of matrices:
1. Symmetric matrix.
2. Identity matrix.
3. Orthogonal matrix.
2 Probability Review
For these questions you may find it helpful to review these notes on probability:
http://www.cs.ubc.ca/~schmidtm/Courses/340-F15/notes_probability.pdf And here are some slides
giving visual representations of the ideas as well as some simple examples:
http://www.cs.ubc.ca/~schmidtm/Courses/340-F17/probability.pdf
2
2.1 Rules of probability
Rubric: {reasoning:6}
Answer the following questions. You do not need to show your work.
1. You flip 4 fair coins. What is the probability of observing exactly 3 heads?
2. You are offered the opportunity to play the following game: your opponent rolls 2 regular 6-sided dice.
If the difference between the two rolls is at least 3, you win $12. Otherwise, you get nothing. What is
a fair price for a ticket to play this game once? In other words, what is the expected value of playing
the game?
3. Consider two events A and B such that Pr(A, B) = 0. If Pr(A) = 0.4 and Pr(A ∪ B) = 0.95, what is
Pr(B)? Note: p(A, B) means “probability of A and B” while p(A ∪ B) means “probability of A or B”.
It may be helpful to draw a Venn diagram.
2.2 Bayes Rule and Conditional Probability
Rubric: {reasoning:10}
Answer the following questions. You do not need to show your work.
Suppose a drug test produces a positive result with probability 0.95 for drug users, P(T = 1|D = 1) = 0.95.
It also produces a negative result with probability 0.99 for non-drug users, P(T = 0|D = 0) = 0.99. The
probability that a random person uses the drug is 0.0001, so P(D = 1) = 0.0001.
1. What is the probability that a random person would test positive, P(T = 1)?
2. In the above, do most of these positive tests come from true positives or from false positives?
3. What is the probability that a random person who tests positive is a user, P(D = 1|T = 1)?
4. Are your answers from part 2 and part 3 consistent with each other?
5. What is one factor you could change to make this a more useful test?
3 Calculus Review
3.1 One-variable derivatives
Rubric: {reasoning:8}
Answer the following questions. You do not need to show your work.
1. Find the minimum value of the function f(x) = 3x
2 − 2x + 5 for x ∈ R.
2. Find the maximum value of the function f(x) = x(1 − x) for x in the interval [0, 1].
3. Find the minimum value of the function f(x) = x(1 − x) for x in the interval [0, 1].
4. Let p(x) = 1
1+exp(−x)
for x ∈ R. Compute the derivative of the function f(x) = − log(p(x)) and
simplify it by using the function p(x).
Remember that in this course we will log(x) to mean the “natural” logarithm of x, so that log(exp(1)) = 1.
Also, obseve that p(x) = 1 − p(−x) for the final part.
3
3.2 Multi-variable derivatives
Rubric: {reasoning:5}
Compute the gradient ∇f(x) of each of the following functions. You do not need to show your work.
1. f(x) = x
2
1 + exp(x2) where x ∈ R
2
.
2. f(x) = exp(x1 + x2x3) where x ∈ R
3
.
3. f(x) = a
T x where x ∈ R
2 and a ∈ R
2
.
4. f(x) = x
>Ax where A =

2 −1
−1 1 
and x ∈ R
2
.
5. f(x) = 1
2
kxk
2 where x ∈ R
d
.
Hint: it is helpful to write out the linear algebra expressions in terms of summations.
3.3 Derivatives of code
Rubric: {code:4}
Note: for info on installing and using Python, see https://github.ugrad.cs.ubc.ca/CPSC340-2017W-T2/
home/blob/master/python_info.md.
Your repository contains a file named grads.py which defines several Python functions that take in an input
variable x, which we assume to be a 1-d array (in math terms, a vector). It also includes (blank) functions
that return the corresponding gradients. For each function, write code that computes the gradient of the
function in Python. You can do this directly in grads.py; no need to make a fresh copy of the file. However,
per the homework instructions, you should add a link to your README file so that the TA can access it
easily.
Hint: it’s probably easiest to first understand on paper what the code is doing, then compute the gradient,
and then translate this gradient back into code.
Note: do not worry about the distinction between row vectors and column vectors here. For example, if the
correct answer is a vector of length 5, we’ll accept numpy arrays of shape (5,) (a 1-d array) or (5,1) (a
column vector) or (1,5) (a row vector). In future assignments we will start to be more careful about this.
Warning: Python uses whitespace instead of curly braces to delimit blocks of code. Some people use tabs
and other people use spaces. My text editor (Atom) inserts 4 spaces (rather than tabs) when I press the Tab
key, so the file grads.py is indented in this manner. If your text editor inserts tabs, Python will complain
and you might get mysterious errors... this is one of the most annoying aspects of Python, especially when
starting out. So, please be aware of this issue! And if in doubt you can just manually indent with 4 spaces, or
convert everything to tabs. For more information see https://www.youtube.com/watch?v=SsoOG6ZeyUI.
4 Algorithms and Data Structures Review
4.1 Trees
Rubric: {reasoning:2}
Answer the following questions. You do not need to show your work.
1. What is the maximum number of leaves you could have in a binary tree of depth l?
4
2. What is the maximum number of nodes (including leaves) you could have in a binary tree of depth l?
Note: we’ll use the convention that the leaves are not included in the depth, so for l = 1 the answers would
be 2 and 3 respectively.
4.2 Common Runtimes
Rubric: {reasoning:4}
Answer the following questions using big-O notation You do not need to show your work.
1. What is the cost of running the mergesort algorithm to sort a list of n numbers?
2. What is the cost of finding the third-largest element of an unsorted list of n numbers?
3. What is the cost of finding the smallest element greater than 0 in a sorted list with n numbers.
4. What is the cost of computing the matrix-vector product Ax when A is n × d and x is d × 1.
4.3 Running times of code
Rubric: {reasoning:4}
Your repository contains a file named bigO.py, which defines several functions that take an integer argument
N. For each function, state the running time as a function of N, using big-O notation. Please include your
answers in your report. Do not write your answers inside bigO.py.
ARE YOU SURE YOU’RE FOLLOWING ALL THE HOMEWORK SUBMISSION INSTRUCTIONS?
5