COMP9020 Quiz 5

Test started Mar 13, 2024 6:00 PMtoMar 27, 2024 6:00 PM

1.1

Question

Suppose $f:S→S$ and $g:S→S$ are bijections.

Which of the following are true for all such functions?

Select all that apply

$(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (f^{-1})∘(g^{-1})$
$(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
$(f;g)^←$ always exists and $(f;g)^← = (f^←);(g^←)$
$(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$
None of the above

Answer

因为是双射，所以反函数一直存在，逆关系一直存在。

令： $(b,c) \in f, (a,b) \in g$

则有：

(a,c) \in f \circ g \\ (b,a) \in g^{-1} \\ (c,b) \in f^{-1} \\ (c,a) \in (f \circ g)^{-1} \\ (c,a) \in g^{-1} \circ f^{-1}

因此，答案为：

$(f∘g)^{-1}$ always exists and $(f∘g)^{-1} = (g^{-1})∘(f^{-1})$
$(f;g)^←$ always exists and $(f;g)^← = (g^←);(f^←)$

1.2

Question

A = \begin{pmatrix} 3 & 1 \\ 4 & 1 \end{pmatrix}

Which of the following matrices is $AA - 2A^T$ ?

Answer

AA = \begin{pmatrix} 3*3 + 1*4 & 3*1 + 1*1 \\ 4*3 + 1*4 & 4*1 + 1*1 \end{pmatrix} = \begin{pmatrix} 13 & 4 \\ 16 & 5 \end{pmatrix}

2A^T = \begin{pmatrix} 6 & 8 \\ 2 & 2 \end{pmatrix}

因此，答案为：

\begin{pmatrix} 7 & -4 \\ 14 & 3 \end{pmatrix}

1.3

Question

Suppose $T(n)$ is defined recursively as:

$T(0) = 1$
$T(n) = 3T(n/3) + O(n)$

True or false: $T(n) ∈ O(n)$

Answer

这里使用主定理。

首先将该式子化成一个简单些的式子：

T(n) = 3T(n/3) + cn

之后，我们可以假设 $n = 3^k$ ，以此简化操作：

\begin{align*} T(n) &= 3(3T(n/9)+cn/3)+cn \\ &= 9T(n/9) + 2cn \\ &= 9(3T(n/27)+cn/9)+2cn \\ &= 27T(n/27)+3cn \\ &= ... \\ &=3^kT(1)+kcn \\ &=n + cnlog_n \\ &\in O(nlogn) \end{align*}

因此，答案为：False

1.4

Question

Suppose $f,g:{a,b}^*→{a,b}^*$ are defined recursively as follows:

$f(λ)=a$
$g(λ)=b$
$f(aw) = f(w)g(w)$
$f(bw) = g(w)f(w)$
$g(aw)=g(bw)=f(w)$

What is f(bba)?

Answer

\begin{align*} f(bba) &= g(ba)f(ba) \\ &= f(a)g(a)f(a) \end{align*}

\begin{align*} f(a) &= f(aλ) \\ &= f(λ)g(λ) \\ &= ab \end{align*}

\begin{align*} g(a) &= g(aλ) \\ &= f(λ) \\ &= a \end{align*}

f(bba) = f(a)g(a)f(a) = abaab

因此，答案为：abaab

1.5

Consider the following code snippet:


myFunc(n):
    if n==0:
        return 1
    else:
        return myFunc(n-1) + myFunc(n-1)

Which of the following hold with regard to the running time T(n) of this code

Select all that apply

$T(n) ∈ O(n^2)$
$T(n) ∈ O(n)$
$T(n) ∈ O(log n)$
$T(n) ∈ O(2^n)$
None of these options

Answer

假设：myFunc(n) 的用时是 $T(n)$ ，则 myFunc(n-1) 的用时是 T(n-1) 。

因为return中调用了两次，所以时间也要计算两倍！具体可对比1.6。

\begin{align*} T(n) &= 2T(n-1) + O(1) \\ &= 4T(n-2) + 3 \cdot O(1)\\ &= ... \\ &= 2^nT(n-n) + \frac{(1+n)n}{2} \cdot O(1) \\ &= 2^n + \frac{n^2+n}{2} \cdot O(1)\\ &\in O(2^n) \end{align*}

因此，答案为：

$T(n) ∈ O(2^n)$

1.6

Consider the following code snippet:


myFunc(n):
    if n==0:
        return 1
    else:
        return 2 * myFunc(n-1)

Which of the following hold with regard to the running time T(n) of this code

Select all that apply

$T(n) ∈ O(n^2)$
$T(n) ∈ O(n)$
$T(n) ∈ O(log n)$
$T(n) ∈ O(2^n)$
None of these options

Answer

假设：myFunc(n) 的用时是 $T(n)$ ，则 myFunc(n-1) 的用时是 T(n-1) 。

\begin{align*} T(n) &= T(n-1) + O(1) \\ &= T(n-2) + 2 \cdot O(1) \\ &= ... \\ &= T(0) + n \cdot O(1) \\ &= n \cdot O(1) \\ &\in O(n) \end{align*}

因此，答案为：

$T(n) ∈ O(n)$

1.7

Question

Recall the definition of a valid expression for the proof checker:

∅ and U are valid expressions
Any single letter A-Z or a-z is a valid expression
If E is a valid expression, then:
- (E) is a valid expression
- Eᶜ is a valid expression
If E₁ and E₂ are valid expressions, then:
- (E₁ ∩ E₂) is a valid expression
- (E₁ ∪ E₂) is a valid expression
- (E₁ \ E₂) is a valid expression
- (E₁ ⊕ E₂) is a valid expression

Based on the above definition, which of the following are valid expressions?

Select all that apply:

$Aᶜᶜᶜ$
$(((U \backslash ∅) \backslash U) \backslash ∅)$
$((A ∩ B) ∪ (C ∩ (D)))$
$((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
$((A1 ⊕ A2)ᶜ)ᶜ$
$((A ∩ B))$

Answer

选项1

根据规则，一个单字母是有效的表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，对一个单字母连续进行三次补集操作是有效的。
选项2

根据规则，∅ 和 𝓤 是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ \ E₂) 也是有效表达式。因此，从 𝓤 中减去 ∅，然后再进行两次相似的操作是有效的。
选项3

根据规则，单个字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 和 (E₁ ∪ E₂) 也是有效表达式。因此，这个表达式有效。
选项4

单字母是有效表达式，(E₁ ∪ E₂) 和 (E₁ ∩ E₂) 也是有效表达式。如果 E 是有效表达式，则 Eᶜ 也是有效表达式。因此，这个表达式有效。
选项5

A1和A2不是有效表达式，因此它们的组合也不应该是。
选项6

根据规则，单字母是有效表达式。如果 E₁ 和 E₂ 是有效表达式，则 (E₁ ∩ E₂) 也是有效表达式。果 E 是有效表达式，则 (E) 也是有效表达式。因此，这个表达式有效。

因此，答案为：

$Aᶜᶜᶜ$
$(((U \backslash ∅) \backslash U) \backslash ∅)$
$((A ∩ B) ∪ (C ∩ (D)))$
$((A ∪ a) ∩ (B ∪ b) ∩ (C ∪ c))ᶜ$
$((A ∩ B))$

2.1

Question

Suppose T(n) is defined recursively as:

$T(0) = 1$
$T(n) = 3T(n-3) + O(n)$

True or false: $T(n) ∈ O(2^n)$

Answer

这里使用主定理。

我们可以假设 $n = 3i$ ，首先将该式子化成一个简单些的式子：

\begin{align*} T(n) &= 3T(n-3) + c_1 \cdot n \\ T(n-3) &= 3T(n-6) + c_1 \cdot (n-3) \\ & ... \\ T(3) &= 3T(0) + c_1 \cdot 3 \end{align*}

我们看到每次递归成本减少 $n$ 的三分之一，但是成本的系数会翻三倍。

\begin{align*} T(n) &= 3^iT(0) + c_1 \cdot (n+(n-3) + (n-6) + ... +3 + 0) \\ &= 3^{\frac{n}{3}} + c_1 \cdot (\frac{n \cdot n}{3} - 3 \cdot (1 + \frac{n}{3}) \cdot \frac{n}{3 \cdot 2}) \\ &\in O(3^{\frac{n}{3}}) \end{align*}

$3^{\frac{n}{3}}$ 是一个指数函数，但是它要比 $2^n$ 慢很多。

因此，答案为：False

2.2

Question

Consider the following code fragment that works on an array:


myFunc(A, lo, hi):
    if lo + 1 >= hi:
        return
    
    j = (lo + hi) / 2
    if A[lo] < A[hi]:            
        myFunc(A, lo, j)
        myFunc(A, j, hi)
    else:
        myFunc(A, j, hi)
        myFunc(A, lo, j)
 
    for i ∈ [lo, hi):
        print(A[i])

In terms of n = hi - lo, which of the following hold for the running time T(n) of this code?

$T(n) ∈ O(n log n)$
$T(n) ∈ O(2^n)$
$T(n) ∈ O(1)$
$T(n) ∈ O(n²)$
$T(n) ∈ O(n)$
$T(n) ∈ O(log n)$

Answer

在递归部分，每次都会把区间分为两部分进行两次递归调用，所以递归树的每一层都有两倍于上一层的调用次数，这种行为在二叉树中是常见的。递归的深度是 O(log n)，因为每次调用都将问题的规模减半。

递归调用中的分支因素是2（因为最坏情况下，两次递归都会执行），但在每层递归中，对区间的打印操作是线性的。这意味着，即使递归深度是 O(log n)，但是每一层递归都要执行 O(n) 的打印操作。所以我们需要将这两者结合起来，得到整体的复杂度。

所以整体复杂度是每层 O(n) 的打印操作乘以 O(log n) 层的递归深度，即 T(n) ∈ O(n log n)。

所以正确的选项是：

$T(n) ∈ O(n log n)$

2.3

Question

Consider a subset, EXP, of valid expressions (see Question 1.7), defined recursively as follows:

∅ and U are elements of EXP
X,Y,Z ∈ EXP
If E ∈ EXP, then:
- (E) ∈ EXP
- Eᶜ ∈ EXP
If E₁, E₂ ∈ EXP, then:
- (E₁ ∩ E₂) ∈ EXP
- (E₁ ∪ E₂) ∈ EXP

Consider dual: EXP → EXP defined recursively as follows:

dual(∅) = U
dual(U) = ∅
dual(X) = X, dual(Y) = Y, dual(Z) = Z
If E ∈ EXP, then
- dual( (E) ) = ( dual(E) )
- dual( Eᶜ ) = dual(E) ᶜ
If E₁, E₂ ∈ EXP, then
- dual( (E₁ ∩ E₂) ) = ( dual(E₁) ∪ dual(E₂) )
- dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )

What is $dual(((X ∩ Yᶜ) ∪ U))$ ?

$((Xᶜ ∩ Y) ∪ ∅)$
$∅$
$((X ∪ Yᶜ) ∩ ∅)$
$((Xᶜ ∪ Y) ∩ ∅)$
None of the above

Answer

首先，根据dual( (E) ) = ( dual(E) )，我们将内部最外层的括号提取到外部最外层：

dual(((X ∩ Yᶜ) \cup U)) = (dual((X \cap Y^C) \cup U))

这样，我们提取括号内的dual，相当于变相去除了一层括号。

根据dual( (E₁ ∪ E₂) ) = ( dual(E₁) ∩ dual(E₂) )，我们把两部分分开：

dual((X \cap Y^C) \cup U) = dual((X \cap Y^C)) \cap dual(U)

对于 $dual((X \cap Y^C))$ ，可以单拎出来继续拆分：

\begin{align*} dual((X \cap Y^C)) &= (dual(X) \cap Y^C)) \\ &= (dual(X) \cup dual(Y^C)) \\ &= (dual(X) \cup dual(Y)^C) \\ &= (X \cup Y^C) \end{align*}

且：dual(U) = ∅

因此答案为：

$((X \cup Y^C) \cap \empty)$

目录

1.1

Question

Answer

1.2

Question

Answer

1.3

Question

Answer

1.4

Question

Answer

1.5

Answer

1.6

Answer

1.7

Question

Answer

2.1

Question

Answer

2.2

Question

Answer

2.3

Question

Answer