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)

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?