Pre-requisite Review

• Total marks: 110

• Homework deadline on Gradescope (Go to gradescope.com > Log In > “School Credentials” > “Search for your school” > “University of Maine” > Login).

• Submission method: There are separate assignments in gradescope: Prereq autograded and Prereq Manually Graded. Problems 1-3 are Autograded, rest are

• Resources for review:

  • Recursion (Section 4.10) of Kernighan and Ritchie

  • A 30-page review of Linear Algebra by Zico Kolter

  • Linear algebra: Gilbert Strang lectures

  • 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_template.c

Rename the file to test_factorial.c. Complete the function and submit the file as a separate file to Gradescope autograder.

Problem 2¶

(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_template.c. Complete the function and submit the file as a separate file to gradescope.

Rename the file to test_prime.c. Complete the function and submit the file as a separate file to Gradescope autograder.

Problem 3¶

(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 function and submit the file as a separate file to gradescope.

Rename the file to test_date.c. Complete the function 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).

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} \\$$

   (1)

   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}$$

   (2)

   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}$$

    (3)

    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}$$

    (4)

    Multiply them together to find the answer.