You cannot submit for this problem because the homework's deadline is due.

Ex3. Programming Algebra

Related Topics: loops, arrays, math.

Jin is taking a Machine Learning course, and is asked to develop a model to recommend courses for a student based on the dataset of students’ ratings of JI courses.

One of his tasks is to write a function that takes a \(n\times n\) weight matrix \(W\) (a 2D square array of int) and the size of the weight matrix \(n\) as input, and returns the trace of the Laplacian of the weight matrix.

int traceLaplacian(int weight[][50], int size){
    // TODO: Implement this function.
}

The formulas are given as follows.

• The degree matrix \(D\) is a diagonal matrix, whose \(i^{th}\) diagonal element is the sum of the \(i^{th}\) row of the weight matrix \(W\):

\[D_{i,i} = \sum_{j=1}^n W_{i,j},\ D_{i,j}=0 \text{ if } i \neq j\]

• The Laplacian \(\mathcal{L}\) of the weight matrix \(W\):

\[\mathcal{L} = D - W. \text{ That is, } \mathcal{L}_{i,j} = D_{i,j} - W_{i,j}\]

• The trace of the Laplacian \(\mathcal{L}\) is the sum of the diagonal of \(\mathcal{L}\):

\[tr(\mathcal{L}) = \sum_{i=1}^n \mathcal{L}_{i,i}\]

If an empty weight matrix is passed in (\(n=0\)), the Laplacian should be empty and its trace should be 0. You don't need to worry about the case where \(n>50\) and ignore integer overflow. Please help Jin implement this function.

Example

Example input:

The first line contains a single int, which is the size \(n\) of the matrix.

The following lines encodes the matrix, each row separated by a \n and each column separated by space.

3
1 2 3
3 2 4
2 1 0

• The weight matrix \(W\) (\(n=3\)) is then:

\[W = \begin{bmatrix}1 & 2 & 3 \\ 3 & 2 & 4 \\ 2 & 1 & 0\end{bmatrix}\].

• The Degree matrix \(D\) is then:

\[D = \begin{bmatrix}1 + 2 + 3 & 0 & 0 \\ 0 & 3 + 2 + 4 & 0 \\ 0 & 0 & 2 + 1 + 0\end{bmatrix} = \begin{bmatrix}6 & 0 & 0 \\ 0 & 9 & 0 \\ 0 & 0 & 3\end{bmatrix}\].

• The Laplacian \(\mathcal{L}\) is then:

\[L = \begin{bmatrix}6 & 0 & 0 \\ 0 & 9 & 0 \\ 0 & 0 & 3\end{bmatrix} - \begin{bmatrix}1 & 2 & 3 \\ 3 & 2 & 4 \\ 2 & 1 & 0\end{bmatrix} = \begin{bmatrix}5 & -2 & -3 \\ -3 & 7 & -4 \\ -2 & -1 & 3\end{bmatrix}\].

• The trace is then:

\[tr(\mathcal{L}) = 5+7+3 = 15\]

Example output:

15

Limits

1s, 128MiB