- Total marks: 110
-
Homework deadline 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)
The factorial of a non-negative integer n , denoted by $n!$, is the product of all positive integers less than or equal to n . The factorial of n also equals the product of n with the next smaller factorial:
$n ! = n × ( n − 1 ) × ( n − 2 ) × ( n − 3 ) × ⋯ × 3 × 2 × 1 = n × ( n − 1 ) !$
For example, $5 ! = 5 × 4 ! = 5 × 4 × 3 × 2 × 1 = 120.$ The value of 0! is 1, according to the convention for an empty product.
Write a recursive C function to compute factorial of a natural number n. It should pass the test_factorial function 10 times. test_factorial function is given.
C programmers: download and edit the file test_factorial.c .
Rename the file to test_factorial.c. Complete the funciton and submit the file as a separate file to Gradescope
autograder.
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 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.
Rename the file to test_prime.c. Complete the funciton and submit the file as a separate file to Gradescope
autograder.
Problem 2
(20 marks)
2.a. Write a C data structure named struct date that capture year, month and days of a date.
2.b. Also write a function greg_is_leap_year that determines whether an year is a leap year.
2.c. Also write a function date_greg_days that count the total number of days since 0001-01-01 AD.
C programmers: Download and edit the file test_date_template.c. Complete the funciton and submit the file as a separate file to brightspace.
Rename the file to test_date.c. Complete the funciton and submit the file as a separate file to Gradescope
autograder.
Problem 4
(50 marks)
Please review Linear Algebra concepts and notations from here and answer the following questions (all answers are in the pdf).
-
(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 .
-
(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.
-
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)
-
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).
-
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)
-
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).
-
Define cross product for two vectors? How to test when two vectors are parallel to other? (5 marks)
-
How to can you find the magnitude of a vector? What is a unit vector? (5 marks)
-
What is a square matrix (0 marks)?
-
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)?
-
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.