1. (10%) Consider the letters A, F, K, R, T, and X below. Which of them are isomorphic?

$$圖片請看原檔$$

A and R, F and T, K and X.

2. (20%) Let

$X = \{-5, \, -4, \, -3, \, -2, \, -1, \, 0, \, 1, \, 2, \, 3, \, 4, \, 5\}$
For $x, \, y \in X$, set $x \, R \, y$ if $x^2 < y^2$ or $x = y$
(a) Show that $R$ is a partial ordering on $X$
(b) Draw a Hasse Diagram of $R$

(a)
Reflexive: Since $\forall x \in X$, $x = x$ so $x \, R \, x$.
Anti-symmetric: When $x \neq y, \, x^2 < y^2$ and $y^2 < x^2$ won’t happen at the same time, but one of the condition must occur, so is either $x \, R \, y$ or $y \, R \, x$.
Transitive: Let $a, \, b, \, c \in X$ where $a \, R \, b$ and $b \, R \, c$, then we get $a^2 < b^2$ and $b^2 < c^2$ so $a^2 < c^2$ which means $a \, R \, c$.
So $R$ is a partial ordering relation on $X$.
(b)

3. (15%) Find the value of sum after the given program segment is executed (Here $i, \, j, \, k, \, increment,$ and $sum$ are integer variables)

.wp-block-code{border:0;padding:0}.wp-block-code>div{overflow:auto}.shcb-language{border:0;clip:rect(1px,1px,1px,1px);-webkit-clip-path:inset(50%);clip-path:inset(50%);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;word-wrap:normal;word-break:normal}.hljs{box-sizing:border-box}.hljs.shcb-code-table{display:table;width:100%}.hljs.shcb-code-table>.shcb-loc{color:inherit;display:table-row;width:100%}.hljs.shcb-code-table .shcb-loc>span{display:table-cell}.wp-block-code code.hljs:not(.shcb-wrap-lines){white-space:pre}.wp-block-code code.hljs.shcb-wrap-lines{white-space:pre-wrap}.hljs.shcb-line-numbers{border-spacing:0;counter-reset:line}.hljs.shcb-line-numbers>.shcb-loc{counter-increment:line}.hljs.shcb-line-numbers .shcb-loc>span{padding-left:.75em}.hljs.shcb-line-numbers .shcb-loc::before{border-right:1px solid #ddd;content:counter(line);display:table-cell;padding:0 .75em;text-align:right;-webkit-user-select:none;-moz-user-select:none;-ms-user-select:none;user-select:none;white-space:nowrap;width:1%}increments := 0
sum := 0

for i := 1 to 87 do
for j := 1 to i do
for k := 1 to j do
begin
increment := increment - 3
sum := sum + increment
end
next k
next j
next i
Code language: plaintext (plaintext)

4. DNA(Deoxyribonucleic acid) is a molecule that carries the genetic instructions for all known organism and many viruses. It consists of a chain of bases. In DNA chain, there are four types of bases: A, C, G, T. For example, a DNA chain of length 10 can be ACGTACGTAT.

(a) Let g(n) be the number of configurations of a DNA chain of length n, in which no two T are consecutive and no two G are consecutive. Write a recurrence for g(n).
(b) Solve the recurrence from part (a).

(a) $g(n) – 2g(n-1) – 5g(n-2) – 2g(n-3) = 0, \, n \geq 4. \\ g(1) = 4, \, g(2) = 14, \, g(3) = 50.$
(b) $g(n) = \dfrac{1}{34}((17 + 5 \sqrt{17})(\dfrac{3 + \sqrt{17}}{2})^n + (17 – 5 \sqrt{17})(\dfrac{3 – \sqrt{17}}{2})^n)$

5. (10%) Give any 7 distinct numbers, there must exist a sum or a difference of two numbers, where the sum or the difference is a multiple of 10. Please explain the reason.

PH: (1,9) (2,8) (3,7) (4,6) (5) (0)

6. (10%) We learned the notations of Big-O, Big-Theta and Big-Omega. However, when we estimate the efficiency of an algorithm, the most commonly used notation is Big-O. Why? Please write down your thinking.

(1) Because $f = O(g) \iff g = \Omega (f)$, so $\Omega$ can be replaced by $O$.
(2) 在估upper-bound時比較簡單（因而$O$比較好用），但是還要再估lower-bound才可得Big-Theta較為麻煩。

7. (15%) A student council consists of three freshmen, four sophomores, four juniors and five seniors. How many committees of eight members of the council contain at least one member from each class?