使 Stack, heap, libc 的 Address Space 隨機生成，讓攻擊者無法判斷位置在哪裡 查看 Linux 中 ASLR 的設定 0: 關閉 ASLR，每次執行位址固定不變 1: 部分啟用 ASLR，只對 Stack, heap, shared libararies 的 Address Space 進行隨機化，但 text 區域不會隨機化 2: 完全啟用 ASLR，text segment 的 Address Space 也會隨機化 kali# sysctl -a --pattern 'randomize' image

題目 給定兩字串 s 和 t，求出 s 轉成 t 的最少編輯次數。 image 解法 暫時不考慮 Copy & Twiddle，因為會需要中介字串 z 以及定義上會小小複雜，這裡用不到。 假設替換、刪除和插入的編輯成本皆為 1。 定義 D[i, j] 為字串 s[i: len(s)] 轉成字串 t[j: len(t)] 的最少編輯次數。 若 $s[i] = t[j]$，則不用編輯，D[i, j] = D[i + 1, j + 1]。

題目 image 演算法 定義 min 為在 Interval Graph 上的最小著色數 K 為目前時間點需要至少多少顏色 將活動依開始時間由小到大排序 將活動依結束時間由小到大排序 從最早開始的活動開始上色，直到塗完所有活動

題目 image Proof (1)Partion Problem (PP) $\in$ NP 給定一組 PP 的 Yes-instance $(A, S-A)$，則我們可以在多項式時間內檢查 (1) A 和 S-A 的元素總和相同 (2) A 和 S-A 互斥，即 $S \cap (S-A) = \emptyset$ 所以 $PP \in NP$ (2) Partion Problem $\in$ NP-Hard 目標 : $SUBSET\ SUM\ {\le}_p\ PARTITION$

題目 image 1. SIP 屬於 NP 給定一個 Certificate : 令 G = (V, E) 為 G2 的一個子圖，且我們知道 G1 = (V', E') 和 G 的對應方式。 驗證 : 我們需要去檢查 G1 是否和 G 同構。(1) 檢查對應方式是不是 Bijection (2) 驗證每個在 G1 的邊 (u, v) 是否也有一個對應在 G 的邊 (f(u), f(v))；不在 G 的邊也一定不會在 G2 中出現，而這需要花 $O(V^2)$ 時間。因此 SIP 可在多項式時間內驗證，故 SIP 屬於 NP。 2. SIP 屬於 NP-Hard 此問題可以將決策版 CLIQUE 問題轉成 SIP K-CLIQUE : 給定一圖 G 問是否存在一個大小為 K 的完全子圖。

題目 image 解法 定義 OPT(i) 為前 i 個活動可產生的最大權重。 定義 $a_i$ 為第 i 項活動，$w_i$ 為第 i 項活動的權重，$s_i$ 為第 i 項活動的開始時間，$f_i$ 為第 i 項活動的結束時間。 定義 $q_i$ 為排除掉和 $a_i$ 衝突的活動後的最大的 index j 使得 $s_i \ge f_j$，即結束時間最接近 $a_i$ 的活動編號。 將每個活動依照結束時間由小到大排序 計算 $q_i$ for all i

題目 image 解法一 : Erdős–Gallai Theorem 若一 n 點簡單圖的度數序列為 $d_1 \ge d_2 \ge ... \ge d_n \ge 0$$$\Longleftrightarrow \sum_{i=1}^{n} d_i 為偶數，且 \sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n min(d_i, k) , \ for\ every\ k\ in\ 1 \le k \le n$$ 如果直接套入定理算 k 從 1 跑到 n，時間複雜度會是 $O(n^2)$，因為右手邊的總和會一直重複計算到，所以實作時要記錄累計的總和來提升效率。另外這題需要先對給定度數序列進行排序，我們已知排序時間複雜度為 O(nlogn)，但這裡可以利用度數序列的特性來讓排序更快。因為合法度數的範圍是 0 ~ n-1，所以可以利用 Counting Sort 來讓排序只要 O(n)。最後分析 ErdosGallai() 的時間複雜度，Line 15-18 每回合最多只會將 pos 減 1，Line 22-25 每回合最多只會將 pos 加 1，當 pos = k 時，pos 不會改變。因此 ErdosGallai() 的時間複雜度為 O(n)。 故整體時間複雜度為 O(n)。

題目 image Lower Bound 所有 $m_i$ 加總後除以 M 即為最少需要的 Bin 數 例如 : 有 4 個容量為 7 的箱子，有 6 種物品，重量分別為 3, 1, 6, 4, 5, 2。 最少需要 (3 + 1 + 6 + 4 + 5 + 2) / 7 = 3 個 Bin First Fit Algorithm

原理 若要滿足 2-CNF-SAT 代表每個子句都必須為 True，而每個子句的格式為 $(A \vee B)$。又 $(A \vee B)$ 等價於 $(\neg A \Rightarrow B)$ 和 $(\neg B \Rightarrow A)$。意義上為「如果 A(B) 為假，則 B(A) 一定要是真」，如此才能滿足 $(A \vee B)$ 為真。 解法是將 Boolean formula 建構成一個 Implication Graph 來找解，建構方式請參考如下演算法。現在先來討論哪種情況不滿足 2-SAT， Case 1 : 存在邊 $(X_i, \hat X_i)$，代表如果 $X_i$ 為真，則 $\hat X_i$ 也要為真，推得 $X_i$ 為假，產生矛盾。故此種情況不可能 Satisfiable。 Case 2 : 存在邊 $(\hat X_i, X_i)$，代表如果 $\hat X_i$ 為真，則 $X_i$ 也要為真，但前提已假設 $X_i$ 為假，產生矛盾。故此種情況不可能 Satisfiable。 Case 3 : $X_i$ 和 $\hat X_i$ 在同一個強連通分量中。代表存在一條 Implication Path 可以從 $X_i$ 走回 $\hat X_i$，令該路徑為 $X_i \Rightarrow X_{j} \Rightarrow X_{k} \Rightarrow ... \Rightarrow \hat X_i$。如果 $X_i$ 設為 True，則中間經過的每個布林變數也要設為 True，最後設 $\hat X_i$ 為 True，推得 $X_i$ 為 False，產生矛盾。故此種情況不可能 Satisfiable。 演算法

11/01 更新 : 14 題沒 B，感謝 spike 12/04 更新 : 12 題沒 A，感謝 水源誠哥 A B A B B A A A

1 Recall the recursive program (discussed in the class) that computes the n-th Fibonacci number. Compute the exact number of additions used by the program. 令 $T(n)$ 為計算第 n 個費氏數所需的加法次數，則根據遞迴公式可得 $T(n)=T(n-1)+T(n-2)+1, T(1)=0,T(2)=0,T(3)=1$ $T(n)=T(n-1)+T(n-2)+1\leq2T(n-1)+1$ $$ \begin{split} T(n)&\leq2T(n-1)+1\ &=2[2T(n-2)+1]+1\

11/09 更新 : 14 改為 D，感謝水源誠哥 D A C D A C C A

ABC (不確定) DE B B ADE AD BDE B ABC ABDE

E E AE DE CD BE ABCE BD BDE CE

B A A E B B D ACDE A AD

ac e a bc acd ad abcd bcd c abce

AB B C BCDE E A ABC BDE D CE

A E D D D BCD AC B ACD CD

B A B A A A A B B B

D A A C A B B A C A