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

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?

### 4 留言

1. #### nnn

第三題 sum是+=increment，所以答案應該是[(2*-3)+(113563*-3)]*113564/2

2. #### Rex

你好，想請問一下第4題的(a)的遞迴式式怎麼列的?
在麻煩你講解一下了，謝謝你！

• 文章作者的留言

#### mt

定義$f(n)$為長度n，首為TG且不含連續T及不含連續G的字串數，則明顯可得長度n，首為GT且不含連續T及不含連續G的字串數也是$f(n)$種
若首字母為A或C，則後方長度$n-1$中，不含連續T且不含連續G，這種次串數有$2g(n-1)$種
若首字母為G，且第二個字母是A或C，則後方長度$n-2$中，不含連續T且不含連續G，這種次串數有$2g(n-2)$種
若首字母為G，且第二個字母是T，則後方長度$n-2$中，不含連續T且不含連續G，這種次串數有$f(n)$種
若首字母為T，且第二個字母是A或C，則後方長度$n-2$中，不含連續T且不含連續G，這種次串數有$2g(n-2)$種
若首字母為T，且第二個字母是G，則後方長度$n-2$中，不含連續T且不含連續G，這種次串數有$f(n)$種
可得第一式$g(n)=2g(n-1)+4g(n-2)+2f(n)$

對$f(n)$討論如下：
首字母為TG，若第三個字母為A或C，則後方長度$n-3$中，不含連續T且不含連續G，這種次串數有$2g(n-3)$種
首字母為TG，若第三個字母為T，第四個字母為A或C，則後方長度$n-4$中，不含連續T且不含連續G，這種次串數有$2g(n-4)$種
首字母為TG，若第三個字母為T，第四個字母為G，則後方長度$n-4$中，不含連續T且不含連續G，這種次串數有$f(n-2)$種
可得第二式$f(n)=2g(n-3)+2g(n-4)+f(n-2)$

將第一式整理如下：
$f(n)=\dfrac{1}{2}(g(n)-2g(n-1)-4g(n-2))$
並帶入第二式：
$g(n)-2g(n-1)-4g(n-2)=4g(n-3)+4g(n-4)+g(n-2)-2g(n-3)-4g(n-4) \\ \implies g(n)-2g(n-1)-5g(n-2)-2g(n-3)=0, \, n \geq 4.$