In general, hash table (Suppose that the size of the hash table is much adequately larger than the maximum number of possible entries. Therefore, very few data collision occurs.) is the most commonly used one for constructing a symbol table of a compiler.
Memoization是一種優化技術,透過將函式執行後的結果暫存起來(快取)，當下次再次以相同參數呼叫時,就能直接從快取中提取結果,而無需重新計算,藉此提升程式執行速度。

---

---

---

Multilevel paging: 假設每個 page table 剛好佔一個 page

「每個 page table 剛好佔一個 page」的設計，使得記憶體配置、位址切割、硬體查表與效能實作都能保持規則、對齊、且高效。

---

The comparison-based sorting algorithm on n data requires \(Ω(nlogn)\) time

\(f(n)\)為polynomial-bounded\(\iff\) \(logf(n)=O(logn)\)

\(log(n!)=Θ(nlogn)\)

\(H(n)=1+1/2+1/3+1/4+...+1/n,∀ n \in \mathbb{Z}^{+} , H(n)=Θ(logn)\)

---

gcd is associative on integer:gcd(gcd(a,b),c)=gcd(a,gcd(b,c)).set difference(-),division(/),implication(->),cartesian product(x) is not associative.

Methods of Proof: \(\text{direct method, contrapositive method}(P \implies Q \equiv \neg Q \implies \neg P \equiv \neg P \lor Q) \text{and contradiction method(反證法)}\)

\(P \implies Q\), \(Q\) is a Necessary Condition for \(P\). \(P\) is a Sufficient Condition for \(Q\).

Open interval: \( \{ x \mid a < x < b \} \), 以\(\left( a,b \right)\)表示之, a ○───────○ b

Closed interval: \( \{ x \mid a \le x \le b \} \), 以\(\left[ a,b \right]\)表示之, a ●───────● b

Cantor's Theorem:For two arbitrary infinitely countable sets A and B, both \(2^A\) and \(2^B\) are uncountable.

Truth Table

(a)onto (b)one-to-one (c)one-to-one且onto

(a)\(onto: \forall \text{y} \in \text{Y}, ∃ \text{x} \in \text{X } \text{s.t.} \text{ f(x)=y}\) (b)\(1-1: f(x_1)=f(x_2) \implies x_1=x_2\)

n件相異物不允許重複取r件排列

n件相異物允許重複取r件排列

n件相異物不允許重複取r件組合

n件相異物允許重複取r件組合

m個相異物放至n個相異箱子,允許空箱

m個相異物放至n個相異箱子,一個箱子至多放一物

m個相異物放至n個相異箱子,不允許空箱(排容)

m個相異物放至n個相同箱子,不允許空箱

m個相異物放至n個相同箱子,允許空箱

---

Different types of distances used in ML

Minkowski distance:

Euclidean distance: (Minkowski distance → p is 2)

Manhattan distance: (Minkowski distance->p is 1)

Chebyshev distance: (Minkowski distance->p is ∞)

Hamming distance:

---

perpendicular (adj.) : at an angle of 90° to a horizontal line or surface;垂直的

---

scalability interoperability sustainability

---

Unmounted file system: 該檔案系統存在於裝置上,但目前沒有被接到系統的目錄樹中,因此作業系統與使用者都無法透過路徑存取它.

Mounted: 檔案系統已經被接到作業系統的目錄樹中,可以透過路徑存取
e.g. CMD: MOUNTVOL
C:/,D:/

entitlement: 系統明確授予某個程式或使用者的「權限 / 能力」

Access Control

---

---

---

The halting problem(a problem to determine whether or not any arbitrary program can stop) is undecidable
The halting problem is undecidable and therefore strictly harder than any NP-hard problem in terms of computability.

若\(\text{A}≤_p\text{B}\), 則\(\text{B}\)為polynomial-time solvable \(\implies \) \(\text{A}\)為polynomial-time solvable

若\(∃\)一個\(\text{NP-complete}\)的問題為polynomial-time solvable, 則\(\text{P}=\text{NP}\)

任意P皆可\(≤_p\)P, NP, NP-complete, NP-hard

NP\(≤_p\)NP-C

NP\(≤_p\)NP-Hard

NP-C\(≤_p\)NP-Hard

P\(≤_p\)NP

P\(≤_p\)NP-C

P\(≤_p\)NP-Hard

(a)若\(\text{P}≠\text{NP}\) (b)若\(\text{P}=\text{NP}\)

Any problem in P can be reduced to SAT in polynomial time.

If SAT has a polynomial time algorithm, then P =NP.

SAT is NP-complete.

---

C/C++ operator precedence

            #include <stdio.h>

            int main() {
                char s[] = "01234";
                char *p = s;

                printf("%c\n", *p++);
                printf("%c\n", *++p);
                printf("%c\n", *(++p));
                printf("%c\n", *(p++));
                printf("%c\n", (*p)++);

                return 0;
            }
            output:
            0
            2
            3
            3
            4