---
tags: 2023DS
---
# Homework 1 - Answer and Analysis
* **You don't worry about the midterm, which may require you to calculate time complexity. TA will give hints to help you to assess it.**
## Assessment
* Submit the homework and answer at least one question: 60%
* Each question: 10% * 4 = 40%
* 格式錯誤為額外扣分,名字位置扣2分，題號扣2分
## Problem 1
Determine the frequency counts for **all statements** in the following two program segments:
:::warning
* 這題題目有點爭議，跟老師討論後的結果是有寫出x++ 為多少或是有把全部的statement列出來的人都給對，但如果你沒有全部列出來又沒有明確寫出x++是多少或是標示不清處，均不給分，
* 至於將全部加總起來，我會斟酌各扣1分，因為題目並沒有說要計算total，
:::
### (a)

for (i = 1; i <= n; i++)         //(1)
    for (j = 1; j <= i; j++)     //(2)
        for (k = 1; k <= j; k++) //(3)
            x++;                 //(4)

* 5%
* (1) : $n+1$ times

* (2) : $\frac{(n+1)n}{2}$ + $n$ times

* (3) : $\frac{n(n+1)(n+2)}{6}$ + $\frac{(n+1)n}{2}$ times

* (4) : $\frac{n(n+1)(n+2)}{6}$ times

* or 只寫 $\frac{n(n+1)(n+2)}{6}$ times

(4)的求法:

$\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^j 1$

= $\sum_{i=1}^n \sum_{j=1}^i j$

= $\sum_{i=1}^n \frac{i(i + 1)}{2}$

= $\sum_{i=1}^n \frac{i^2 + i}{2}$

= $\frac{1}{2}\sum_{i=1}^ni^2+\frac{1}{2}\sum_{i=1}^ni$

= $\frac{1}{2}\frac{n(n+1)(2n+1)}{6}+\frac{1}{2}\frac{n(n+1)}{2}$

= $\frac{n^3+3n^2+2n}{6}$ or $\frac{n(n+1)(n+2)}{6}$ (5%)

* 2%
* answer the time complexity: $O(n^3)$

### (b)

i = 1;              //(1)
while (i <= n) {    //(2)
    x++;            //(3)
    i++;            //(4)
}

* 5%
* (1) : $1$ times

* (2) : $n + 1$ times

* (3) : $n$ times

* (4) : $n$ times

* or 只寫 $n$ times
* 2%
* answer the time complexity: $O(n)$
## Problem 2
Show that the following equatities are incorrect

**Review the definition of Big-O, Omega and Delta:**
* $f(n) = O(g(n))\iff \exists\ c, n_0 > 0 \to |f(n)| \le c|g(n)|, for\ all\ n > n_0$
* $f(n) = \Omega(g(n))\iff \exists\ c, n_0 > 0 \to |f(n)| \ge c|g(n)|, for\ all\ n > n_0$
* $f(n) = \Theta(g(n))\iff \exists\ c_1, c_2, n_0 > 0 \to c_1|g(n)| \le |f(n)| \le c_2|g(n)|, for\ all\ n > n_0$
---
For each question

* **Write the correct definition: 1.5% (very important)**
* **Answer: 1% (只寫答案沒有其他說明)**
* **Use error definition**: **0%** for this question
:::warning
* 有些人會被改錯是因為你沒清楚地寫出是對還是錯 ，有疑慮下次上課可以問
* 基本上，這題你有寫出定義，寫對或錯就給你對
:::
a) $10n^{2} + 9 = O(n)$

$10n^{2} + 9 \le c \cdot n$
$\to n(10n - c) + 9 \le 0$
We cannot find a constant $c$ and $n_0$ to let the inequation be established.
Ex: $n = \frac{c}{10}$

---
b) $n^{2}\log{n} = \Theta(n^2)$

$c_1n^2\le n^{2}\log{n} \le c_2n^2$
$\to c_1 \le \log{n} \le c_2$
Because $c_1$ and $c_2$ are just constants, and n is a positive variable so that always can find a $n_0$ let the $\log{n}$ leave the range $[c_1, c_2]$.
Ex: $n \ge 2^{c_2 + 1}$

---
c) $n^{2}/\log{n} = \Theta(n^2)$

$c_1n^2\le n^{2}/\log{n} \le c_2n^2$
$\to c_1 \le \frac{1}{\log{n}} \le c_2$
Because $c_1$ and $c_2$ are just constants, and n is a positive variable so that always can find a $n_0$ let the $\frac{1}{\log{n}}$ leave the range $[c_1, c_2]$.
Ex: $n \ge 2^{\frac{1}{c_1 - 1}}$

---
d) $n^{3}2^{n} + 6n^{2}3^{n} = O(n^{3}2^{n})$

$n^{3}2^{n} + 6n^{2}3^{n} \le c \cdot n^{3}2^{n}$
$\to 1 + 6\frac{3^n}{n2^n} \le c$
We cannot find a constant $c$ and $n_0$ to let the inequation be established.
Because $\frac{3^n}{n2^n} = \frac{1.5^n}{n}$ and it will increase when increasing $n$, it can find a $n_0$ so that let the fraction $\frac{3^n}{n2^n}$ greater than the constant $c$

## Problem 3
Analyze the computing time of function SelectionSort

void SelectionSort(int *a, const int n) {
    for (int i = 0; i < n; i++) {
        int j = i;
        for (int k = i + 1; k < n; k++)
            if (a[k] < a[j])
                j = k;
        swap(a[i], a[j]);
    }
}

We can parse the key line - ```line-7: j = k``` directly because the statement $j = k$ is in the nested loop and needs to be executed most times.

So, It just discusses the problem: Find the all combinations of the pair $(i, j)$ when $0 <= i < k < n$
* Find two different numbers in the range $[0, n)$
* $\to C^{n}_{2} = \frac{n(n - 1)}{2}$ times (**10%**)
* Time complexity: $O(n^2)$
## Problem 4
A complex-valued matrix X is represented by a pair of matrices $(A,B)$ where $A$ and $B$ contain real values. Write a program that computes the product of two complex-valued matrices $(A,B)$ and $(C,D)$, where $(A,B)*(C,D) = (A+iB) * (C + iD) = (AC - BD) + i(AD + BC)$. Determine the number of additions and multiplications if the matrices are all $n \cdot n$

### The times of addition/subtraction

\begin{gather}
\begin{bmatrix}
a_{11} & a_{12} & a_{13} & \dots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \dots & a_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & a_{n3} & \dots & a_{nn} \\
\end{bmatrix} +
\begin{bmatrix}
b_{11} & b_{12} & b_{13} & \dots & b_{1n} \\
b_{21} & b_{22} & b_{23} & \dots & b_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
b_{n1} & b_{n2} & b_{n3} & \dots & b_{nn} \\
\end{bmatrix} \\ =
\begin{bmatrix}
a_{11} + b_{11} & a_{12} + b_{12} & a_{13} + b_{13} & \dots & a_{1n} + b_{1n} \\
a_{21} + b_{21} & a_{22} + b_{22} & a_{23} + b_{23} & \dots & a_{2n} + b_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_{n1} + b_{n1} & a_{n2} + b_{n2} & a_{n3} + b_{n3} & \dots & a_{nn} + b_{nn} \\
\end{bmatrix}
\end{gather}

It needs to add two elements $n^2$ times
### The times of product

\begin{gather}
\begin{bmatrix}
a_{11} & a_{12} & a_{13} & \dots & a_{1n} \\
a_{21} & a_{22} & a_{23} & \dots & a_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
a_{n1} & a_{n2} & a_{n3} & \dots & a_{nn} \\
\end{bmatrix} \cdot
\begin{bmatrix}
b_{11} & b_{12} & b_{13} & \dots & b_{1n} \\
b_{21} & b_{22} & b_{23} & \dots & b_{2n} \\
\vdots & \vdots & \vdots & \ddots & \vdots\\
b_{n1} & b_{n2} & b_{n3} & \dots & b_{nn} \\
\end{bmatrix}
\end{gather}

It needs $n^2 \cdot n$ times of multiplications and $n^2 \cdot (n - 1)$ times of additions.
* The result is also a $n\cdot n$ matrix, and it has $n^2$ elements.
* For each element of the result, each of them needs
* $n$ times of multiplications
* and $n - 1$ times of additions.
### Let's summarize
$(AC - BD) + i(AD + BC)$
* The product with **imaginary unit** $i$ should be ignored)
* $AC$, $BD$, $AD$, $BC$: are...
* $n^3$ times of multiplications: total $4n^3$ times.
* $n^3 - n^2$ times of additions: total $4n^3 - 4n^2$ times

:::warning
有以下兩種答案，原本解答寫的是加負號，但把它當作是減法也給對
:::
* $AC + (-BD$), $AD + BC$: are $n^2$ times $\to 2n^2$ times
* $AD + BC$: are $n^2$ times $\to n^2$ times

Total $4n^3 - 2n^2$ or $4n^3 - 3n^2$ times of additions **(5%)**
$4n^3$ times of multiplications **(5%)**