• Total marks: 110

• Due on 09/06 before class. Submit the writeup on paper in class and a backup copy on brightspace. Upload the code files on brightspace.

• Resources for review:
  • Recursion (Section 4.10) of Kernighan and Ritchie
  • A 30-page review of Linear Algebra by Zico Kolter
  • Review vectors here

Problem 1

(20 marks)

A natural number (1, 2, 3, 4, 5, 6, etc.) is called a prime number (or a prime) if it is greater than 1 and cannot be written as the product of two smaller natural numbers.

Write a C or Python function to calculate if a number is prime. Return 1 if it is prime and 0 if it is not a prime. If the number is not a prime number, then a factor exists. Return the factor as through a pointer.

C programmers: Download and edit the file test_prime.c. Complete the funciton and submit the file as a separate file to brightspace.

Python programmers: write functions similar to test_factorial.c including the test functions.

Complete the funciton and submit the file as a separate file to brightspace.

Problem 2

(20 marks)

Write a C or Python function named days() that determines the number of days from the turn of the century (01/01/2000) for any date within the century passed as a structure. The date structure should use the template

struct date {
    int month;
    int day;
    int year;
}

In writing the days() function, use the convention that all years have 360 days and each month consists of 30 days. The function should return the number of days for any date structure passed to it. Make sure to declare the returned variable a long integer to reserve sufficient room for dates such as 12/19/2099.

Problem 4

(50 marks)

Please review Linear Algebra concepts and notations from here and answer the following questions (all answers are in the pdf).

1. (2 marks) In matrix notation defined in the linked document, when I say a matrix is $n \times m$ (alternatively the matrix is in the set $\mathbb{R}^{n \times m}$, does the n refer to the number of rows or the number of columns .

2. (5 marks) Let the matrix $A \in \mathbb{R}^{4 \times 2}$ and $B \in \mathbb{R}^{2 \times 3}$ be defined as

   \[A := \begin{bmatrix} 1 & 2 \\ 3 & 5 \\ 7 & 11 \\ 13 & 17 \\ \end{bmatrix}, \\ B := \begin{bmatrix} 19 & 23 & 29 \\ 31 & 37 & 41 \\ \end{bmatrix} \\\]

   Is the matrix multiplication $AB$ valid? Make up an example of matrix $B$ when matrix multiplication $AB$ would not have been valid. Find out the matrix multiplication $C = AB$ by hand. Write down all the steps to show which numbers get multiplied by which numbers.

3. Given two matrices $A$ of size $m \times n$ and $B$ of size $p \times q$, when is the matrix multiplication $AB$ valid? When is the matrix multiplication $BA$ valid? When is the addition $A + B$ valid? (5 marks)

4. What is the transpose of a matrix? If a matrix $A$ has the shape $n \times m$, what is the shape of matrix $A^\top$ (3 marks).

5. Define dot product for two vectors? How to test when two given vectors are perpendicular? Assume you have two n-dimensional vectors $\vec{a} = [a_1, a_2, \dots, a_n]$ and $\vec{b} = [b_1, b_2, \dots, b_n]$. Denote dot product as, $\vec{a} \cdot \vec{b}$? (5 marks)

6. Denote the above vectors as column matrices. Define the following $n \times 1$ matrices with the vector components.

   \[\mathbf{a} = \begin{bmatrix} a_1 \\ a_2 \\ \vdots \\ a_n \end{bmatrix},\\ \mathbf{b} = \begin{bmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{bmatrix}\]

   Use matrix operation like matrix transpose and matrix multiplication to write vector dot product (5 marks).

7. Define cross product for two vectors? How to test when two vectors are parallel to other? (5 marks)

8. How to can you find the magnitude of a vector? What is a unit vector? (5 marks)

9. What is a square matrix (0 marks)?

10. What are the column vectors and row vectors of a matrix? How can you write matrix multiplication in terms of row vectors and column vectors of a matrix (5 marks)?

11. Suppose you are given a $n \times n$ square matrix called $U$. All it’s $n$ columns vectors are unit vectors and every pair of the unit vectors are perpendicular to each other. Find out the product $U^\top U$ . What is the name of given to such matrices whose column vectors are unit vectors and are perpendicular to each other? (10 marks).

    Hint: Assume the column vectors of the matrix $U$ be $\mathbf{u}_1, \dots, \mathbf{u}_n$. Then the $U$ matrix can be written as,

    \[U = \begin{bmatrix} | & | & & | \\ \mathbf{u}_1 & \mathbf{u}_2 & \dots & \mathbf{u}_n \\ | & | & & | \\ \end{bmatrix}\]

    The transpose of matrix $U$ is

    \[U^\top = \begin{bmatrix} \rule{2em}{0.4pt} \mathbf{u}_1^\top \rule{2em}{0.4pt} \\ \rule{2em}{0.4pt} \mathbf{u}_2^\top \rule{2em}{0.4pt} \\ \vdots \\ \rule{2em}{0.4pt} \mathbf{u}_n^\top \rule{2em}{0.4pt} \\ \end{bmatrix}\]

    Multiply them together to find the answer.