考試

109成大電機離散[參考解答]

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)

mt01

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

參考解答:$-3 \times \binom{89}{3} = -340692$


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)
再用Pigeon Hole Principle(PHP)解釋即可。


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?

參考解答: $\binom{16}{8} – [\binom{13}{8} + 2 \binom{12}{8} + \binom{11}{8}] + [2 \binom{9}{8} + 2 \binom{8}{8}]$


試題(pdf):連結

有任何問題,或想要完整解釋的,歡迎在下方留言唷!

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.$

發佈留言