COMP9020 – Foundations of Computer Science

FINAL Exam – Term 3 2022

From Question 1 to Question 4

With my own solution (might be incorrect)

Part 1

It seems that I can't prove this question perfectly.

It is confusing.

1.1

I can't prove it because I think it is incorrect. $lcm(m+n,p)$ should greater or equal $lcm(n,p)$.

The counter example is in Part 1.2

1.2

Assum:

• $m = 1$
• $n = 4$
• $p = 8$

Then:

• $lcm(m,p) = 8$
• $lcm(n,p) = 8$
• $lcm(m+n,p) = 40$

Therefore:

$lcm(m+n, p) \ne lcm(n,p)$

1.3

Part 2

2.1

Definition of \: $A\backslash B = A∩Bᶜ$:

De Morgan's, C over ∩: $(A∩B)^C = A^C \cap B^C$:

Distributivity of ∩ over ∪: $A∩(B∪C) = (A∩B)∪(A∩C)$:

Therefore, it is incorrect.

2.2

Assum:

$(X^*Y)^* = w_1w_2...w_i$

Every element $w_i = x_{i1}x_{i2}...x_{ik}y_i$

and it could also be that:

$x_{i1}x_{i2}...x_{ik}y_i = (x_i \cup \empty)^* \cup (\empty \cup y_i) \subseteq (X \cup Y)^*$

Therefore, we could find that every element $w_i$ in string $(X^*Y)^*$ could be restructed by $(X \cup Y)^*$.

Proved:

Part 3

Let F denote the set of all well-formed formulas. Define the relation $R ⊆ F×F$ as follows:

3.1

Because $\varphi \models \psi$, when $\varphi$ is true, the $\psi$ is true.

When $\varphi = true$, $\neg \varphi \lor \psi = true$.

When $\varphi = false$, $\neg \varphi \lor \psi = true$.

Because $\varphi \rightarrow \psi$ could be $true$, it means that $\varphi \rightarrow \psi$ is satisfiable.

Therefore, $(\varphi, \psi) \in R$.

3.2

If we want to prove that R is reflexive, we should prove that for every element $\varphi \in F$, $(\varphi, \varphi) \in R$.

It is easy to find that:

When $\varphi$ is $true$, $\varphi$ is $true$.

It means that:

According to the result of part (a), if $\varphi \models \varphi$ then $(\varphi, \varphi) \in R$.

Therefore, we could prove that R is reflexive.

3.3

Assum:

• $X \models Y$
• $Y \models Z$

According to the result of part (a), we could find that:

Because $X \models Y$, $Y models Z$, when $X = true$, we could find that $Y = true$ and $Z = true$.

Therefore, we could find that $X \models Z$.

According to the result of part (a), we could find that:

Because:

We could prove that R is transitive.

Part 4

4.1

• $T(n) = T(n/2) + log(n)$

  Use Main Theorem, we could find that:

  $$a = 1 \\ b = 2 \\ f(n) = log(n) \\ n^{log_ba} = n^{log_21} = n^0 = 1$$

  Because $f(n) = O(log(n)) = O(n^{log_21}log^1(n))$, we could prove that:

  $T(n) = O(n^{log_21}log^{1+1}(n)) = O(log^2(n))$.

• $T(n) = 4T(n/4) + 4n$

  Use Main Theorem, we could find that:

  $$a = 4 \\ b = 4 \\ f(n) = 4n \\ n^{log_ba} = n^{log_44} = n^1 = n$$

  Because $f(n) = 4n = O(n) = O(n^{log_ba}log^0(n))$, we could prove that:

  $T(n) = O(n^{log_ba}log^{0+1}(n)) = O(nlog(n))$.

• $T(n) = T(n - 2) + 2n$

  Every time the $n$ decrease by 2. Therefore, the recursion time is $n/2$.

  Every recursion we have to execute $2n$ times.

  Therefore, $T(n) = \frac{n}{2} \times 2n = O(n^2)$.

• $T(n) = T(n/3) + \sqrt{3n}$

  Use Main Theorem, we could find that:

  $$a = 1 \\ b = 3 \\ f(n) = \sqrt{3n} \\ n^{log_ba} = n^{log_31} = n^0 = 1$$

  Use Main Theorem Case 3, we could prove that:

  $T(n) = O(n^{0.5})$.

• $\sqrt[3]{n^2+2n-1}$

  We could find that:$\sqrt[3]{n^2+2n-1} = O(n^{2/3})$

• $\frac{100}{n}+\frac{n}{100}$

  We could find that: $\frac{100}{n}+\frac{n}{100}= O(n + 1/n) = O(n)$

This is the list of functions:

1. $O(log^2(n))$: $T(n) = T(n/2) + log(n)$
2. $O(n^{1/2})$: $T(n) = T(n/3) + \sqrt{3n}$
3. $O(n^{2/3})$: $\sqrt[3]{n^2+2n-1}$
4. $O(n)$: $\frac{100}{n}+\frac{n}{100}$
5. $O(nlogn)$: $T(n) = 4T(n/4) + 4n$
6. $O(n^2)$: $T(n) = T(n - 2) + 2n$

4.2

Correct:

• f(n) ∈ O(n²)
• f is injective
• f(n) ≤ f(n+2) for all n