\documentclass{article}
\usepackage[english]{babel}
\usepackage[utf8]{inputenc}
\usepackage{fancyhdr}
\usepackage[top=2cm, bottom=4.5cm, left=2.5cm, right=2.5cm]{geometry}
\usepackage{graphicx}
\usepackage{amsmath, amsfonts, amssymb}
\usepackage{hyperref}
\usepackage{algorithm}
\usepackage{algpseudocodex}

\usepackage{ulem}
\usepackage{xcolor}
\definecolor{linkcolor}{RGB}{0,0,255}
\hypersetup{colorlinks=true,
  linkcolor=linkcolor,
  urlcolor=linkcolor}
\renewcommand\UrlFont{\color{linkcolor}\uline}

\usepackage{enumerate}
\usepackage{parskip}

% Edit these as appropriate
\newcommand\course{CS 1420}
\newcommand\hwnumber{1}                      % <-- homework number
\newcommand\duedate{Thursday, Jan 29, 2026 at 12:00pm \textbf{(Noon)}}

\newcommand{\PP}{\mathbb{P}}
\newcommand{\RR}{\mathbb{R}}


\newcommand{\prob}[1]{P\left(#1\right)} 
\newcommand{\given}[0]{\,\middle|\,}


\begin{document}
   \begin{center}
      \huge\textbf{Homework \hwnumber}
   \end{center}

   \begin{center}
        \large{Due: \duedate}
   \end{center}
   

\section*{Written Assignment}

\subsection*{Introduction}
The purpose of this assignment is to fortify your background in statistics, linear algebra, runtime complexity, socially responsible computing, and programming with NumPy. A strong grasp of these subjects is essential for your success in the course.

You may be able to find answers to these problems by searching for the problem text or consulting a large language model. Please search instead for the concepts being applied; the goal is not to solve these specific problems but to review principles that will be fundamental to the course.

\subsection*{Problem 0: Collaboration Policy}

Every student enrolled in CSCI 1420 is expected to know and abide by the course collaboration policy.
Your assignments will not be graded if you do not meet this expectation.

Please review the course collaboration policy available at \href{https://cs.brown.edu/courses/csci1420/assets/docs/collaboration.pdf}{this link} and include the following signed statement as your answer to Problem 0:

\textit{By signing with my Banner ID below, I agree to abide by the CSCI1420 Collaboration Policy as published on the course website. I also agree to not include my real name on assignments in the course and instead will use my Banner ID on any applicable submissions to preserve anonymity in grading.}

\textit{Signed: *Your Banner ID Here*}

\subsection*{Problem 1: Review of Probability and Statistics}
(12 points)

\begin{enumerate}[a.]
    \item Recall Bayes' Theorem, which states that
    \begin{align*}
        \prob{B \given A} = \frac{\prob{A \given B} \cdot \prob{B}}{\prob{A}} = \frac{\prob{A \cap B}}{\prob{A}}. 
    \end{align*}
    for a probability distribution $P$ concerning events $A$ and $B$.

    Brown students love restaurants. Suppose we have a distribution $P$ that describes the characteristics of restaurants visited by Brown students, where
    \begin{itemize}
        \item $P(\text{restaurant serves Italian food}) = P(\text{restaurant serves Mexican food}) = \frac{1}{2}$, and
        \item $P(\text{restaurant is expensive}) = \frac{1}{7}$.
    \end{itemize}
    Assume that
    \begin{itemize}
        \item all restaurants serve either Italian or Mexican food (but not both),
        \item each Brown student visits exactly one restaurant each day, and
        \item encounters with Brown students are independent events unless otherwise specified.
    \end{itemize}

    \begin{enumerate}[i.]
    
        \item Steve bumps into two random Brown students and asks them which restaurants they visited yesterday. What is the probability that both of the restaurants they visited serve Italian food?

% TODO: add your solution here!
%
%
%
%
%
%
        
        \item Gordan bumps into two random Brown students and asks them which restaurants they visited yesterday. One is a computer science concentrator, and the other is a history concentrator. Suppose the history concentrator visited an Italian restaurant. What is the probability that both of the restaurants they visited serve Italian food?

% TODO: add your solution here!
%
%
%
%
%
%

        
        \item George bumps into two random Brown students and asks them which restaurants they visited yesterday. At least one of the students visited a Mexican restaurant. What is the probability that both of the restaurants they visited serve Mexican food?

% TODO: add your solution here!
%
%
%
%
%
%


        \item Jaideep bumps into two random Brown students and asks them which restaurants they visited yesterday. At least one of the students visited an expensive Italian restaurant. What is the probability that both of the restaurants they visited serve Italian food?

% TODO: add your solution here!
%
%
%
%
%
%


    \end{enumerate}
    \textit{Hint: None of the four parts have the same answer.}


    \item Suppose $Z_1, \ldots, Z_k$ are independent standard normal random variables. This means that $\mathbb{E}[Z_i] = 0$ and $\operatorname{Var}(Z_i) = 1$. Let
    \begin{align*}
        Q &= \sum_{i = 1}^k Z_i^2.
    \end{align*}
    
    Derive an expression for $\mathbb{E}[Q]$ in terms of $k$.

    \textit{Hint: Apply the linearity of expectation.}

    \textit{Remark: $Q$ as defined above follows the \href{https://en.wikipedia.org/wiki/Chi-squared_distribution}{Chi-Squared Distribution}.}

% TODO: add your solution here!
%
%
%
%
%
%
    
\end{enumerate}


\subsection*{Problem 2: Review of Linear Algebra}
(12 points)

\begin{enumerate}[a.]
    \item Consider a matrix $A \in \mathbb{R}^{n \times n}$. Let $\text{rank}(A) < n$. Prove that $A$ has an eigenvalue equal to 0. You may not use the \href{https://mathworld.wolfram.com/InvertibleMatrixTheorem.html}{Invertible Matrix Theorem} when solving this problem. 
    
    \textit{Hint: Recall that the rank of a matrix is equal to the number of linearly independent columns of the matrix.}

% TODO: add your solution here!
%
%
%
%
%
%
    
    
    \item Let $B \in \mathbb{R}^{n \times n}$ be a symmetric matrix satisfying $\mathbf{x}^TB\mathbf{x} > 0$ for all $\mathbf{x} \in \mathbb{R}^n$ such that $\mathbf{x} \ne \mathbf{0}$. Remember that the eigenvalues of a symmetric matrix are real. Prove that all of the eigenvalues of $B$ are strictly greater than 0. Do not use any theorems for positive definite matrices. 

% TODO: add your solution here!
%
%
%
%
%
%
    
    \item Let $C \in \mathbb{R}^{n \times n}$ be a symmetric matrix. Assume that $C$ has $n$ unique eigenvalues. Prove that all of the eigenvectors of $C$ are orthogonal. 
    
    \textit{Hint: Begin your proof by considering the equations}
    \begin{align*}
        C\mathbf{v}_1 = \lambda_1 \mathbf{v}_1 \\
        C\mathbf{v}_2 = \lambda_2 \mathbf{v}_2
    \end{align*}
    \textit{where ($\lambda_1$, $\mathbf{v}_1$) and ($\lambda_2$, $\mathbf{v}_2$) are two different eigenpairs of $C$. Then, multiply the second equation by $\mathbf{v}_1^T$.}


% TODO: add your solution here!
%
%
%
%
%
%

    
\end{enumerate}

\subsection*{Problem 3: Runtime Complexity}
(14 points)

The Fibonacci sequence can be defined by the recurrence relation $F(n)=F(n-1) + F(n-2)$ for $n \geq 2$, with $F(0)=0$ and $F(1)=1$.
We can make use of the fact (likely first noted by \href{http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF}{Edsger Dijkstra}) that
\begin{gather*}
\begin{pmatrix} 1&1 \\ 1&0 \end{pmatrix}^n = \begin{pmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{pmatrix}
\end{gather*}
for any positive integer $n$.  So, to compute $F(n)$, we can compute $\begin{pmatrix} 1&1 \\ 1&0 \end{pmatrix}^{n-1}$ and return the upper left number in the matrix.

Describe an algorithm to compute $F(n)$ for arbitrary $n$ that uses \textit{\emph{fewer than}} $O(n)$ additions and multiplications (don't worry about the size of the integers), and prove that it satisfies this complexity bound.  That is, prove a sublinear complexity bound in terms of $n$ on the number of additions and multiplications this algorithm performs.  Feel free to search for such an algorithm, but please generate the proof of the complexity bound yourself.


% TODO: add your solution here!
%
%
%
%
%
%



\subsection*{Problem 4: Socially Responsible Computing}

(7 points)

While planning the construction of the Fukushima nuclear power plant, data scientists were interested in determining the highest earthquake magnitude the plant should be able to withstand. To achieve this, they used continuous regression models using data of earthquake magnitudes recorded over the years. The graphs below plot two models, where the $y$-axis represents annual frequency and the $x$-axis represents earthquake magnitude. The magnitude ranges $4.5$ up to the rare $9.5$.
The diamonds denote the observed frequencies of earthquakes of 
different magnitudes, and the solid line represents the predictions 
of the frequencies by each model.
\\
\begin{center}
    \includegraphics[width=0.4\textwidth]{4_1.png}
    \; \; \; \; 
    \includegraphics[width=0.4\textwidth]{4_2.png}
\end{center}
\textit{Source: Silver, N. (2012). The Signal and the Noise: Why So Many Predictions Fail--but Some Don't. New York, NY: Penguin Press.}
\\ \\ \\
Scientists referred to one of the two graphs above to inform the plant’s engineering and determined that the plant should withstand an earthquake of up to 8.6. In March 2011, the Fukushima nuclear power plant was hit with a 9.1 earthquake---one the most severe nuclear accidents since Chernobyl. 

\begin{enumerate}[a.]
\item The scientists' determination for the plant’s design to withstand an earthquake of 8.6 magnitude led to a detrimental consequence. Looking at the two graphs, what does each model predict about the probability of an earthquake of magnitude $8.6$?

% TODO: add your solution here!
%
%
%
%
%
%

\item Which graph did the scientists use in making their decision for the plant’s design? What went wrong in the modeling, and why should they have referred to the other graph instead?
\\ \\
\textit{Hint: Think of things that often go wrong with choosing and fitting a model to some given data, and make note of the difference in the two graphs.}

% TODO: add your solution here!
%
%
%
%
%
%
\end{enumerate}

\newpage 

\section*{Programming Assignment}

\subsection*{Introduction}
The purpose of this portion is to get familiar with NumPy, which we will use
heavily throughout the semester. 

NumPy is a powerful numerical computing library for Python that provides
very efficient, heavily optimized functionalities for large, multi-dimensional
arrays and matrices (see \texttt{np.ndarray}), as well as many standard manipulations and linear algebra algorithms (see \texttt{np.linalg}).

It is strongly preferred over ``pure Python'' implementations (eg. with for-loops)
for several reasons. In particular, NumPy leverages several highly optimized
low-level libraries (see \texttt{BLAS} and \texttt{LAPACK}) written in languages like C
and Fortran to minimize all overhead involved in the operations and computations,
since Python is an interpeted language whereas C and Fortran are compiled.
Additionally, NumPy arrays will always be much more memory-efficient than 
Python \texttt{list}'s.


\subsection*{Set up}
Python 3.12 and NumPy are necessary for the completion of programming assignments for this course.
Python and NumPy can be installed on your own machine via the directions found at \href{https://github.com/Brown-Machine-Learning-Spring-2026/environment-setup-guide}{this link}.
For your convenience, we also have a course-wide virtual environment set up on the department machines at \verb|/course/cs1420/cs142_env|. The environment can be activated from your own folder by running the following command: \verb|source /course/cs1420/cs142_env/bin/activate|.

\subsection*{Stencil Code}

You can find the stencil code for this assignment on GitHub classroom at \href{https://classroom.github.com/a/-Awhi-id}{this link}. For more details, please see the \href{https://docs.google.com/document/d/1RbsJ_IKfzuAyL7yDma4Z7bCVTwiNJfPAHbBAd2WeIEE/edit?usp=sharing}{download/submission guide}.

We have provided the following stencil code:
\begin{itemize}
    \item \verb|warmup.py| contains 8 functions for you to implement: \verb|part_a| through \verb|part_g|. You will implement these functions in the \textbf{Warm Up: Introduction to NumPy} portion of this programming assignment.
    \item \verb|eigenvalues.py| contains two functions for you to implement:
    \verb|qr| and \verb|compute_eigenvalues|. You will implement these functions in the \textbf{Computing Eigenvalues via QR Decomposition} portion of this programming assignment. 
\end{itemize} 


You should only need to modify code marked with \texttt{\#TODO}
in \texttt{warmup.py} and \texttt{eigenvalues.py} to complete
this assignment. If you make any other edits to the provided
stencil code, please make sure to revert them or leave them
commented out in the final handin for autograder compatibility.

To test your implementations in \texttt{eigenvalues.py}, you can run \texttt{python test\_eigenvalues.py} in a terminal. Make sure you activate the virtual environment first when working over ssh or on a department machine:
\begin{center}
    \texttt{source /course/cs1420/cs142\_env/bin/activate}
\end{center}


\newpage

\subsection*{Warm Up: Introduction to NumPy}

If you have never used NumPy before, please read through the ``Getting started'' portion of the \href{https://numpy.org/doc/stable/user/}{NumPy user guide} before attempting this exercise.
We have also made a \href{https://colab.research.google.com/drive/1hVlJHxNCvdZMwpqpxZ7AK6C6TzizUoyf?usp=sharing}{Python and NumPy review notebook} that might be helpful.
For each of the following parts, please implement its associated function in \verb|warmup.py|.

NumPy is often abbreviated as ``np'' (i.e., \verb|import numpy as np|). You may find the following functions particularly helpful: \verb|np.arange|, \verb|np.zeros|, \verb|np.ones|, \verb|np.eye|, \verb|np.sum|, \verb|np.hstack|, \verb|np.vstack|, \verb|np.transpose|, \verb|np.matmul|, \verb|np.inner|, \verb|np.where|, and \verb|np.dot|. 

You may not use \verb|np.array()| (eg. to create the desired Numpy \texttt{ndarray}'s from Python \texttt{list}'s).

\begin{enumerate}[a.]
    \item Create a $1$-dimensional matrix containing the values 2 through 6 inclusive. Return the new matrix in function \verb|part_a|. 
    \item Create a $4 \times 4$ matrix where all entries are $1$. Return the new matrix in function \verb|part_b|. 
    \item Create a $6 \times 6$ identity matrix. Return the new matrix in function \verb|part_c|. 
    \item Given matrix $A$, compute the sum of the values of its columns. Return the answer in function \verb|part_d|. 
    \item Given matrices $A$ and $B$, compute $C$, where $C = A^T B$. Return the matrix $C$ in function \verb|part_e|. 
    \item Using either \verb|np.vstack| or \verb|np.hstack|, create a $4 \times 2$ matrix where all the values in the first column are zeros and all the values in the second column are ones. Return the new matrix in function \verb|part_f|. 
    \item Given a matrix of floats $A$, create a new matrix of the same shape where all values greater than $3.0$ are set to $1$ and all other values are set to $0$. Return the new matrix in function \verb|part_g|. 
\end{enumerate}

\newpage

\subsection*{Computing Eigenvalues via QR Decomposition}

Your task is to finish implementing both the Householder QR decomposition 
algorithm (lines 2 through 9 in Algorithm \ref{alg:qr-decomp}) and the QR 
eigenvalue computation algorithm (Algorithm \ref{alg:qr-algo}).
In the stencil, these are contained respectively in \verb|qr| 
and \verb|compute_eigenvalues| in the \verb|eigenvalues.py|. The lines 
in Algorithm \ref{alg:qr-decomp} which you must implement are colored violet.
Please note that this problem is intended to serve as a NumPy exercise; therefore,
\textit{understanding the theory behind the algorithms is not a requirement.} 

\subsubsection*{QR Decomposition}

Let $A \in \mathbb{R}^{n \times n}$. The \textit{QR decomposition} of $A$ is a
matrix product $QR$, where $Q \in \mathbb{R}^{n \times n}$ is an orthogonal matrix 
($Q^T = Q^{-1}$) and $R \in \mathbb{R}^{n \times n}$ is upper triangular. This 
factorization is called the QR decomposition. 

Below, we present the Householder QR decomposition algorithm. \textit{Again, you 
do not need to understand the mathematics behind this algorithm.} The purpose of implementing this algorithm is to gain familiarity with transforming mathematical and algorithmic notation into respective NumPy operations. This includes learning how to multiply matrices, compute norms, and manipulate NumPy arrays using NumPy's functionalities instead of Python for-loops. 

Some notes regarding the notation presented in Algorithm \ref{alg:qr-decomp}:
\begin{enumerate}

    \item We let $y_i$ denote the $i$-th entry of some vector $\mathbf{y}$, and $\mathbf{y}_{a:b}$ will denote the subvector $\mathbf{y}$ with first element $y_a$ and last element $y_{b - 1}$. Note that the vector $\mathbf{y}_{a:b}$ should contain $b - a$ entries.
    
    \item Similarly, $x_{i, j}$ will denote the entry in the $i$-th row and $j$-th column of some matrix $X$. Let $X_{a:b, c:d}$ denote the submatrix of $X$ with upper left corner $x_{a, c}$ and lower right corner $x_{b - 1, d - 1}$. Note that $X_{a:b, c:d}$ should have dimension $(c - a) \times (d - b)$. You can find some examples of this notation on our \href{https://cs.brown.edu/courses/csci1420/assets/docs/Numpy.pdf}{NumPy guide}.
    
    \item Also, $X_{a:b, j}$ will denote the $j$-th column of submatrix $X_{a:b, 0:n}$. Note that $X_{a:b, j}$ is a vector with $b - a$ entries.
    
    \item Let $I^{n \times n}$ denote the $n \times n$ identity matrix.  Let $0^{n \times n}$ denote an $n \times n$ matrix where all entries are $0$. 
    
    \item $\|\cdot\|_2$ denotes the \href{https://mathworld.wolfram.com/L2-Norm.html}{L2 norm}. $\operatorname{sign}(x)$ evaluates to $1$ if $x \geq 0$ and $0$ otherwise. 
    
\end{enumerate}

\begin{algorithm}[H]
\caption{Householder QR Decomposition Algorithm}\label{alg:qr-decomp}
\begin{algorithmic}[1]
    \Function{QR}{$A$}
    \State \textcolor{violet}{$R \gets \text{copy}(A)$}
    \State \textcolor{violet}{$V \gets 0^{n \times n}$}
    \State \textcolor{violet}{$I \gets I^{n \times n}$}
    \For{$k = 0 \text{ \textbf{to} } n - 1$}
        \State \textcolor{violet}{$\mathbf{x} \gets R_{k:n, k}$}
        \State \textcolor{violet}{$V_{k:n, k} \gets \operatorname{sign}(x_0) \| \mathbf{x} \|_2 I_{0:n-k, 0} + \mathbf{x}$}
        \State \textcolor{violet}{$V_{k:n, k} \gets V_{k:n, k} / \| V_{k:n, k} \|_2$}
        \State \textcolor{violet}{$R_{k:n, k:n} \gets R_{k:n, k:n} - 2 V_{k:n, k} (V_{k:n, k}^T R_{k:n, k:n})$}
    \EndFor
    \State $Q \gets 0^{n \times n}$
    \For{$j = 0 \text{ \textbf{to} } n - 1$}
        \State $\mathbf{x} \gets I_{0:n, j}$
        \For{$k$ = $n - 1 \text{ \textbf{downto} } 0$}
            \State $\mathbf{x}_{k:n} \gets \mathbf{x}_{k:n} - 2 V_{k:n, k} (V_{k:n, k}^T \mathbf{x}_{k:n})$
        \EndFor
        \State $Q_{0:n, j} \gets \mathbf{x}$
    \EndFor
    \State \Return $Q, R$
    \EndFunction
\end{algorithmic}
\end{algorithm}

\newpage

Some notes regarding the implementation of Algorithm \ref{alg:qr-decomp}:
\begin{enumerate}
    \item The $\operatorname{sign}(\cdot)$ function has been implemented for you in the stencil code. Do not use \verb|np.sign|. 

    \item The NumPy equivalent for $X_{a:b, c:d}$ is \verb|X[a:b, c:d]| (see Python's \textit{slice notation}). Similarly, the NumPy equivalent for $X_{a:b, c}$ is \verb|X[a:b, c]|. If you wish to index the entire $j$-th column of $X$, use \verb|X[:, j]|.
    
    \item The vector $V_{k:n, k}$ in line 9 should be treated strictly as a column vector. Note that calling \verb|V[k:n, k]| will return a 1-dimensional NumPy array. To transform $V_{k:n, k}$ into a column vector, you can call \verb|V[k:n, k].reshape(-1, 1)|. Generally, if \verb|x| satisfies \verb|x.shape = (a,)|, then you can reshape \verb|x| into an $a \times 1$ NumPy array by calling \verb|x.reshape(-1, 1).shape = (a, 1)|. 

    \item You should not use $\verb|V[k:n, k] /= np.linalg.norm(V[k:n, k])|$. You should instead use  \\ $\verb|V[k:n, k] = V[k:n, k] / np.linalg.norm(V[k:n, k])|$. 
\end{enumerate}



\subsubsection*{Computing Eigenvalues with QR Decomposition}

We can leverage the QR decomposition to approximately compute the eigenvalues for a matrix $A \in \mathbb{R}^{n \times n}$. First, we let $A_\text{temp} = A$. Then, we iteratively update $A_\text{temp}$ a total of $m$ times, where the $k$-th iteration constitutes the following updates: 
\begin{align*}
    QR &= A_\text{temp}, \\
    A_\text{temp} &= RQ.
\end{align*}
Under certain conditions, $A_\text{temp}$ will converge to an upper triangular matrix. Then, the eigenvalues of $A$ are the diagonal elements of $A_\text{temp}$. The complete algorithm is presented below as Algorithm \ref{alg:qr-algo}. Please use the $\verb|qr|$ function you implemented following Algorithm \ref{alg:qr-decomp} for the QR decomposition step. Do not use NumPy's $\verb|qr|$ function.
\begin{algorithm}[H]
\caption{Algorithm for Eigenvalue Computation}\label{alg:qr-algo}
\begin{algorithmic}[1]
\Function{ComputeEigenvalues}{$A$, $m$}
\State $A_\text{temp} \gets A$
\For{$i = 0 \text{ \textbf{to} } m - 1$}
    \State Factor $A_\text{temp}$ into $Q R = A_\text{temp}$
    \State $A_\text{temp} \gets R Q$
\EndFor
\State \Return $\operatorname{diag}(A_\text{temp})$
\EndFunction
\end{algorithmic}
\end{algorithm}

\newpage

\section*{Grading Breakdown}

The grading breakdown for the assignment is as follows:
\begin{center}
\begin{tabular}{| l | r |}
	\hline
	Problem 1 & 18\% \\
	Problem 2 & 18\% \\
	Problem 3 & 22\% \\
	Problem 4 & 11\% \\
	Programming & 31\% \\
	\hline
	Total & 100\% \\
	\hline
\end{tabular}
\end{center}

Problem 0 is ungraded but must be submitted for your assignments this semester to be graded.

\section*{Handing In}
You will turn in your final handin via Gradescope, which you should have been automatically added to through Canvas. If you have questions about using Gradescope or have not been added, please ask on Edstem. For this assignment, you should have written answers for Questions 1, 2, 3, and 4. Please submit the written portion to ``Homework 1'' on Gradescope.

For the programming, you should submit your code (\texttt{warmup.py} and \texttt{eigenvalues.py}) to ``Homework 1 Code'' on Gradescope.

\section*{Anonymous Grading}

You need to be graded anonymously, so please do not write your name anywhere on your handin. 

\section*{Academic Integrity}
The \href{https://cs.brown.edu/courses/csci1420/assets/docs/collaboration.pdf}{CSCI 1420 Collaboration Policy} applies to this assignment.
As outlined in the \href{https://college.brown.edu/design-your-education/academic-policies/academic-code}{Brown Academic Code} and the \href{https://graduateschool.brown.edu/academics-research/rules-regulations/academic-code}{Brown Academic Code, Graduate Student Edition}, attempting to pass off another's work or AI-generated work as your own can result in failing the assignment, failing this course, or even dismissal or expulsion from Brown.  More than that, you will be missing out on the goal of your education, which is the cultivation of your own mind, thoughts, and abilities.  Please review this course's collaboration policy and if you have any questions, please contact the instructor.
\end{document}
