글

Full binary tree with $L$ leaves has $2L - 1$ total nodes.

Definition of Full Binary Tree      A Binary Tree is full if and only if every node has 0 or 2 children.

Proof by Induction Inductive Hypothesis The full binary tree with $L$ leaves has $N = 2L - 1$ total nodes. Base Case We can easily think of two base cases. Note that the shape of the tree at each base case is unique (Draw by yourself).
If L = 1, then N = 1. If L = 2, then N = 3. Inductive Step We want to show that the full binary tree with $L + 1$ leaves has $2(L + 1) - 1$ total leaves $\forall n \gt 2, n \in \mathbb{N}$.

Suppose that $\exists n \gt 2, n \in \mathbb{N}$ the full binary tree with $L$ leaves has $2L - 1$ total leaves.

$T$ : the full binary tree with $L$ leaves.
$v$ : a leaf node of $T$

If we want to append a new node in $T$, two nodes must be inserted on the left and right side of some leaf node of $T$. Which implies that every node insertion increases $N$ by $2$ and $L$ by $1$.

$2L - 1 + 2 = 2(L + 1) - 1$
Hence, the inductive hypothesis is proved.

Iterative DFS on the graph with post-visit ordering.

Recently, I'm studying about SCC(Strongly Connected Component) related subjects. Kosaraju's algorithm and Tarjan's algorithm are two representative algorithm to calculate SCC of graph.

Kosaraju's algorithm requires post-visit order list of DFS.
With recursive DFS, it's straightforward. But conventional iterative DFS algorithm can't calculate post-visit order.
Since that it doesn't store any information about vertices that previously visited.
Although I've googled several hrs to find nice implementation, I failed it.

So, I implemented with additional depth stack and parent array. If you have idea for any furture simplification or optimization, please mail me! #include <iostream> #include <vector> #include <algorithm> #include <stack> using namespace std; int main() { int N; // Number of vertices int M; // Number of edges vector<vector<int>> graph; // Adjacency list of graph stack<int> dfs; /…

Basic properties of ring homomorphisms

$R,\ S$ : ring.
$\phi$ : $R \rightarrow S$ be ring homomorphism.
Let $A$ be subring of $R$ and $B$ be ideal of $S$.

1. For any $r \in R$ and any positive integer $n$, $\phi(nr) = n\phi(r)$ and $\phi(r^{n}) = (\phi(r))^{n}$

By operation-preserving property of ring homomorphism, following equations must be satisfied.
$\phi(r + \dots + r) = \phi(r) + \dots + \phi(r)$
$\phi(r \cdot r \dots r) = \phi(r) \cdot \phi(r) \dots \phi(r)$

2. $\phi(A) = \{\phi(a) \mid a \in A\}$ is subring of $S$.

Since that $A$ is subring of R, $a - b \in A$ and $ab \in A,\ \forall a,\ b \in A$.
Hence, $\phi(a - b) = \phi(a) - \phi(b) \in \phi(A)$ and $\phi(ab) = \phi(a)\phi(b) \in \phi(A),\ \forall a,\ b \in A)$.

$\therefore \text{By subring test, } \phi(A) \text{ is subring of }S.$

3. If $A$ is an ideal and $\phi$ is onto $S$, then $\phi(A)$ is an ideal.

$\phi$ is onto $S$ implies that $\phi(r) = s ,\ \exists r \in R,\ \forall s \in S$ or equivalently, $\phi(A) = S$.
$A$ is ideal of $R$ implies $ar,\ ra \in A,\ \f… Reducibility over$Q$implies reducibility over$ZQ$: ring of rational number (which is field)$Z$: ring of integer (which is integral domain, not a field) content of polynomial : greatest common divisor of the coefficients of polynomial (must be nonzero polynomial) Suppose$f(x) \in Z[x]$and$f(x) = g(x)h(x)$, where$g(x),\ h(x) \in Q[x]$and$1 \leq deg\ g(x),\ h(x) < deg\ f(x)$. Also, we can assume that$f(x)$is primitive polynomial. Since that dividing both sides with the content of$f(x)$, say$c_{f(x)}$, derives $$\frac{f(x)}{c_{f(x)}} = \frac{g(x)h(x)}{c_f(x)}$$ Which makes polynomial in left side primitive, but does not affect degree of$g(x)$nor$h(x)$. Hence,$f(x)$can be primitive in any situation. Let$a$be the LCM(Least Common Divisor) of the denominators of the coefficients of$g(x)$, and$b$be the LCM of the denominators of the coefficients of$h(x)$. Then,$abf(x) = ag(x) \cdot bh(x)\ (ag(x),\ bh(x) \in Z[x])$. Let$c_{1}$be the content of$ag(x)$, and$c_{2}$be the content of$bh(x)$. Then, we can writ… Reducibility test for degrees 2 and 3$F$: field Reducibility test for degrees 2 and 3 is as follows, $$f(x) \in F[x] \text{ and } deg\ f(x) = 2\text{ or }3$$$$\implies$$$$f(x)\text{ is reducible over }F\text{ iff }f(x)\text{ has a zero in }F$$ Suppose that$f(x) = g(x)h(x)$, where$g(x),\ h(x) \in F[x]$. Since that, polynomials of zero degree are the only unit over integral domain, forms containing zero polynomial are not our concern. Hence,$1 \leq g(x),\  h(x) < deg\ f(x)$Since, in integral domain, deg$f(x) = deg\ g(x) + deg\ h(x)$and$deg\ f(x)$is$2$or$3$, at least one of g(x) and h(x) has degree 1. Say$g(x) = ax + b$. Then, clearly,$-a^{-1}b$is a zero of$g(x)$and therefore a zero of$f(x)$. Conversely, suppose that$f(a) = 0, a \in F$. Then by the Factor Theorem, we know that$x - a$is a factor of$f(x)$and, therefore$f(x)$is reducible over$F$. 고등학생의 아우성 로그의 미적분 가지고 힘들어 할 정도면 문과인가보다. “로그, 로그!” Reference  곱셈을 덧셈으로 바꿔 천문학적 숫자 계산 손쉽게 On the form of ring homomorphism from$Z_{n}$to itself.$\phi$:$Z_{n} \rightarrow Z_{n}$,$x \mapsto ax$, where$a^{2} = a$is ring homomorphism. Let$\phi(1) = a$. Then$a = \phi(1) = \phi(1)\phi(1) = a^{2}$. Let$x \in Z_{n}$. Then$\phi(x) = \phi(1 + \dots + 1) = \phi(1)x = ax\$.

Hence, our original conjecture is true.